counting 1 bits SPOILER

This spoiler/nodeshell rescue is in reference to Ariels's writeup in "counting 1 bits."

Sick of staring at that ampersand? Bitter at binary? Let's start by reviewing the given code.

for( n = 0; b; n++ )
	b &= (b - 1);

What we've got here is a loop that counts the number of "1" bits in a given number b. After this loop runs, b will equal zero and n will equal the number of 1 bits in b. The tricky part of that loop is the bitwise AND operator, the &=. Given two numbers, a bitwise AND will examine each bit in each number and set the corresponding bit in a result to 1 if both bits in the given numbers were 1; or in any other case 0. If you're not already familiar with this, you really ought to read Wharfinger's writeup for bitwise.

So how does it work? Let us unroll that loop! Set b equal to 45 (0010 1101) and let 'er rip.

n    b 
1    0010 1101
2    0010 1100
3    0010 1000
4    0010 0000
     0000 0000 (loop stops)

And so the loop runs four times, clearing the lowest bit each time through. Still not getting it? Look at (b-1) in comparison to b.

 
9:   0000 1001      27:   0001 1011
8:   0000 1000      26:   0001 1010
 
42:  0010 1010      116:  0111 0100
41:  0010 1001      115:  0111 0011

What's going on here? When you subtract 1 from a binary number, you're really turning off the rightmost 1 and turning on every bit after it. Toggling them all, if you will. Let's explicate the loop again. This time, pay close attention to what happens when we logically AND the two numbers together.

 
n    b
0    0010 1101
--------------
     0010 1101
   & 0010 1100
   = 0010 1100
1
--------------
     0010 1100
   & 0010 1011
   = 0010 1000
2
--------------
     0010 1000
   & 0010 0111
   = 0010 0000
3
--------------
     0010 0000
   & 0001 1111
   = 0000 0000
4
--------------

Each iteration through the loop, everything from the least significant 1 bit to the least significant bit is ANDed with its inverse, setting them and every bit betwixt the two to zero. Since the loop eats precisely one bit at a time, it will run until all of the bits have been turned to zeros, leaving n equal to the number of times the loop was processed, and thus counting the 1 bits in that given number b.