From: Robert Klemme <shortcutter@...>
Date: 2010-02-14T07:43:21+09:00
Subject: Re: Generating all possible combinations of a 5 digit pattern.

On 02/13/2010 09:09 PM, Seebs wrote:
> On 2010-02-13, Zach Bartels <no@spam.com> wrote:
>> that is very interesting and I hadn't even considered using bits. Know
>> any good links where I could read more about bits / using bit
>> operations ?
> 
> I learned it before "links" existed, so I don't know.
> 
>> I think what I don't understand the most, is the 2nd line 
> 
>> (val & (2 << pos)) ? 'N' : 'C
> 
> Okay.
> 
>>  (inbetween the  DEF and END)   Where is it defining the maximum
>> number of letters to use in the generated combination, for example? Or
>> perhaps the example didn't really cover all that and I'm mistaken.
> 
> This part doesn't cover that.
> 
>>> 	letter(16, 0) => 'C'
>>> 	letter(16, 1) => 'C'
>>> 	letter(16, 2) => 'C'
>>> 	letter(16, 3) => 'C'
>>> 	letter(16, 4) => 'N'
> 
> This is where you decide how many letters to use -- if you wanted to use six
> letters, you'd just add letter(x, 5).
> 
> Now, onto the core bit:
> (which, by the way, has an OBVIOUS flaw in it.  I missed it 'cuz I'm a C
> programmer.  And also a stupid typo)
> 
> 	(val & (2 << pos)) ? 'N' : 'C
> 
> You probably know about || (or) and && (and).  "a || b" is true if either a
> is true or b is true.  "a && b" is true if both a is true and b is true.
> 
> Now, imagine that you were to view a number as bits.  The first bit has the
> value 1, the second 2, the third 4, the fourth 8, and so on.  A number is the
> sum of the bits that are set in it; 16 is 0b1000, 15 is 0b0111, and so on.
> 
> There are a few handy operations to perform on bits.  Four common logical
> operations are used on bits.  One is complement, written ~ in C.  (I don't
> even know off the top of my head whether Ruby has a complement operator, but
> I include it for completeness).  Complement is also called "bitwise not",
> because just as "!true == false" and "!false == true", ~0 = 1 and ~1 = 0.
> 
> So if you had a four bit number x, and it were 16 (0b1000), ~x would be
> 0b0111, or 15.  (Actually, in many cases, the top bit has special meaning.
> I'm ignoring that for now.)
> 
> The way bitwise operations are performed is by performing them separately
> on each bit, but & and | are just like && and || otherwise.  1 & 1 is 1,
> 1 & 0, 0 & 1, and 0 & 0 are all 0.  Similarly, 1&anything is 1, 0&0 is 0.
> 
> So.
> 
> Let's say you want to find out whether a number has the fourth bit set in it.
> You can use "x & 16".  Since 16 is 0b1000, every bit other than the 16s bit
> in the result is DEFINITELY zero.  The 16s bit will be 1 if x had the 16s
> bit set, and otherwise 0, so your result will be either 16 (if x had the
> 16s bit set) or 0 (if x didn't have it set), *no matter what other bits were
> set*.
> 
> Now, in C, you could just use "x & 16" as a conditional, because 0 is false
> in C.  But in Ruby, it's not, so I should have written
> 
> 	((val & (2 << pos)) != 0) ? ...
> 
> Now, you might be wondering about <<.  <<, called "left shift", means "shift
> all the bits left some number of times".  0b0100 << 1 => 0b1000.  0b0001 << 2
> = 0b0100.  There's a corresponding right shift, which moves them the other
> way.
> 
> That means that 1 << x is the same as "the xth bit".  By contrast, "2 << x"
> is a stupid typo.  :)
> 
> So if you write
> 	val & (1 << pos)
> you get a non-zero value if val has the pos'th bit set, and otherwise zero.
> And that means that
> 	(val & (1 << pos)) != 0
> is true if val has the pos'th bit set, and otherwise false.
> And that means that
> 	((val & (1 << pos)) != 0) ? 'N' : 'C'
> is 'N' if val has the pos'th bit set, and otherwise 'C'.

I'm sorry, but this is overly complicated.  If I want to know whether 
the fourth bit is set I would use Fixnum#[]:

irb(main):002:0> 20.times {|i| printf "%3d %06b %d\n", i, i, i[4]}
   0 000000 0
   1 000001 0
   2 000010 0
   3 000011 0
   4 000100 0
   5 000101 0
   6 000110 0
   7 000111 0
   8 001000 0
   9 001001 0
  10 001010 0
  11 001011 0
  12 001100 0
  13 001101 0
  14 001110 0
  15 001111 0
  16 010000 1
  17 010001 1
  18 010010 1
  19 010011 1
=> 20
irb(main):003:0>

There is also Bignum#[] with identical semantics, so you don't need to 
worry that exceeding Fixnum's range creates problems:

irb(main):007:0> (1 << 40).class
=> Bignum
irb(main):008:0> (1 << 40)[0]
=> 0
irb(main):009:0> (1 << 40)[40]
=> 1
irb(main):010:0> (1 << 40)[41]
=> 0
irb(main):011:0>

If there are more than two alternatives things get more complicated.  We 
can use something like this to get the index value for each position 
(example assumes 3 different values):

irb(main):014:0> 20.times {|i| a=i;x=[]
irb(main):015:1> until a == 0
irb(main):016:2> a, b = a.divmod 3; x.unshift b
irb(main):017:2> end
irb(main):018:1> printf "%3d %p\n", i,x}
   0 []
   1 [1]
   2 [2]
   3 [1, 0]
   4 [1, 1]
   5 [1, 2]
   6 [2, 0]
   7 [2, 1]
   8 [2, 2]
   9 [1, 0, 0]
  10 [1, 0, 1]
  11 [1, 0, 2]
  12 [1, 1, 0]
  13 [1, 1, 1]
  14 [1, 1, 2]
  15 [1, 2, 0]
  16 [1, 2, 1]
  17 [1, 2, 2]
  18 [2, 0, 0]
  19 [2, 0, 1]
=> 20
irb(main):019:0>

Now combine that with storage of the values:

irb(main):019:0> val=%w{C N x}
=> ["C", "N", "x"]
irb(main):020:0> 20.times {|i| a=i;x=[]; until a==0;a,b=a.divmod 
3;x.unshift val[b]; end;printf "%3d %p\n", i,x.join}
   0 ""
   1 "N"
   2 "x"
   3 "NC"
   4 "NN"
   5 "Nx"
   6 "xC"
   7 "xN"
   8 "xx"
   9 "NCC"
  10 "NCN"
  11 "NCx"
  12 "NNC"
  13 "NNN"
  14 "NNx"
  15 "NxC"
  16 "NxN"
  17 "Nxx"
  18 "xCC"
  19 "xCN"
=> 20
irb(main):021:0>

A bit of adjusting needs to be done of course in order to fill leading 
"zeros".

Kind regards

	robert


-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/