From: Seebs Date: 2010-02-14T05:15:06+09:00 Subject: Re: Generating all possible combinations of a 5 digit pattern. On 2010-02-13, Zach Bartels 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 / usenet-nospam@seebs.net http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!