Re: Generating all possible combinations of a 5 digit pattern.

On 2010-02-13, Zach Bartels <[e-mail]> 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'.

-s
-- 
Copyright 2010, all wrongs reversed.  Peter Seebach / [e-mail]
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!