Count the number of ones in a binary number using as few instructions as possible.

arithmetic/count.one.bits New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Count the number of ones in a binary number using as few instructions
as possible.

1. One simple solution is to keep on shifting the number and checking
the carry bit.  This will take the order of number of bits in the
number.

It can be done in the order of number of 1's in the number.

-- Pawan Singh <psingh@newbridge.com>

Show solution

A pseudo-function:

X is the input number , and n is the return value.

n = 0

loop:
if (x == 0) return

x = x ^ (x-1)       ! "^" means bitwise exclusive-or.
n = n + 1

go to loop

-- Ken Kelley <kkelley@athena.mit.edu>

[ Editor: with exclusive-or the loop does not terminate in general: for
x = 2, 2 XOR 1 = 3, then 3 XOR 2 = 1, then 1 XOR 0 = 1 for ever.  The
next posting uses bitwise AND, which clears the lowest 1 bit. ]

In C:

unsigned nCountBits(unsigned nCount)
{
  unsigned nRet = 0;

  while (nCount)
  {
    nRet++;
    nCount &= (nCount - 1);
  }

  return nRet;
}

In English:

Taking a binary number and doing a binary AND with the number minus one
will result in the same number with its rightmost set bit "switched
off".  Iterating until the number reaches zero will count the number of
set bits.

-- Jonathan S. Haas <positron@Starbase.NeoSoft.COM>