Counting 1 bits (idea)

Let's say b is of some unsigned integer type, and we want to count how many of b's bits are set. This is just plain boring:

  for(n=0; b; b >>= 1)
    if (b & 1) n++;

Or in Pascal (yuck):

  n := 0;
  while (b) do begin
    if (odd(b)) then n:=n+1;
    b = b div 2
  end

It's really just converting b to binary, and counting how many 1's it would need for that. Disgusting, really. Here's a nicer way:

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

Simple, elegant and concise, this hack is guaranteed to make the uninitiated want to take up gardening.

This hack is extremely useful on job interviews, but you'll need to know how it works, over on the counting 1 bits SPOILER.

Late addition:

A friend showed me a source for this amazing idea. It appears in almost exactly the same form in K&R2 (The C Programming Language, 2nd edition, aka the New Testament). And it's exercise 2-9 (on page 47) of K&R (The C Programming Language, aka the Old Testament).