Re: Number of 1's in 64 bit number...[don't read if not interested in algos/math...]

[David Rasmussen <pinkfloydhomer@yahoo.com>]

I'm amazed to read all these suggestions. The problem is old and 
wellknown. It is usually called Population Count or PopCount. It is used 
in several situations, but the use I know best is from bitboard-based 
chess programs. Do a search of "chess bitboard" in google, and read 
about. The lookup-table is the usual implementation if potability is 
required. There are usually faster methods on a given platform, and some 
CPU's have this as a native instruction.

In chess, the board is often relatively sparse and the following 
implementation is better overall than the lookup-table for such 
programs. It loops one time for each 1-bit:

int PopCount(unsigned long long bitboard)
{
         int count = 0;
         while(bitboard)
         {
                 ++count;
                 bitboard &= bitboard - 1;
         }
         return count;
}