[OT] Number of 1's in 64 bit number

[OT] Number of 1's in 64 bit number

[Claus Fischer]

Off-topic though interesting. I wonder if there's a generic place
to find collections of such kind of algorithms.

The proposed solution

: unsigned count_ones(unsigned36 a)
: {
:   a = a - (a>>1 & 0333333333333);
:   a = a - (a>>1 & 0333333333333);
: 
:   // Each octal digit is replaced by number of 1's in it
: 
:   a = ((a>>3) + a) & 0070707070707;
:   return a % 63;    // casting out 63's
: }

is buggy for octal digits of 3 and 7.
A working modification of the 36-bit solution seems to be

unsigned long count_ones(unsigned36 a)
{
  /* Each octal digit is replaced by number of 1's in it */
  a = a - (a>>1 & 0333333333333) - (a>>2 & 0111111111111);

  /* Combine groups of two octal digits each */
  a = ((a>>3) + a) & 0070707070707;

  /* Add up, using the fact that 64 == 1 (mod 63) */
  return a % 63;
}

But this will only work if there are less than 63 bits set
in the number, so it's not generic for 64 bit numbers either.

For 64 bits use Nathan's solution.

Claus

-- 
Claus Fischer <claus.fischer@clausfischer.com>
http://www.clausfischer.com/