[courses] [C] Finally get lesson 10 exc #2 (without understanding your bit-shift)

[Laurel Fan]

On Tue, Nov 12, 2002 at 06:11:19PM -0500, Morgon Kanter wrote:
> /* Count all 1s in the integer, please explain what I even did! */
>     for(i = 0;i < BITS;i++) {
>       if( ((x & (1 << i)) >> i)) count++; 

Explanation:

(I'll use 8 bit integers for simplicity)

Looking at all those parens and operators at once can be pretty
overwhelming, so let's try this one step at a time:

Start from the inside of the parens:

  1 << i

1 in binary looks like: 00000001

<< is shift left, which means you shift 1 i bits to the left.

So, for example:

  1 << 0 = 00000001
  1 << 1 = 00000010
  1 << 2 = 00000100
  1 << 3 = 00001000
  1 << 4 = 00010000
  ... etc

If you look at this pattern, one thing you'll notice is that (1 << i)
in binary has a 1 in the i'th position from the right.

Next, we have:
  x & (1 << i)

& is bitwise and.  for example, if
x == 5
i == 2

1 << 2 == 00000100
x == 5 == 00000101

  00000101     (5)
& 00000100     (1 << 2)  
= 00000100     (1 << 2)
     ^ ^ ^--- 1 and 0 is 0
      \ \---- 1 and 1 is 1
       \----- 0 and 0 is 0

Now, what if:
x == 5
i == 1

1 << 1 == 00000010

  00000101    (5)
& 00000010    (1 << 1)
= 00000000    (0)

So, if (x) in binary has a 1 in the same position as (1 << i), you get
(1 << i) back, but if (x) in binary has a 0 there, you get 0 back.
Try a few more examples if this doesn't make sense.

Combining this with what we learned about (1 << i), we can determine
that:

x & (1 << i)

  is (1 << i) if x in binary has a 1 in the i'th position from the right
  is    0     if x in binary has a 0 in the i'th position from the right

Is that enough to figure the rest out?

-- 
laurel at sdf.lonestar.org
http://dreadnought.gorgorg.org