From: Zach Bartels Date: 2010-02-14T05:40:05+09:00 Subject: Re: Generating all possible combinations of a 5 digit pattern. Thanks again, for that. I think I understand a lot better now. Also, I did kind of have a "duh" moment when I was staring at the bottom section of code you confirmed as responsible for how many letters to use. Thanks again for your time. I will read over everything a couple of times and play around (I just found out I don't currently have an interpreter installed, haha) when I get the chance. And hopefully I will understand it at that point! :p -Zach On 13 Feb 2010 20:09:40 GMT, Seebs wrote: >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