How to count the number of ones in a binary word

Problem/Question/Abstract:

How to count the number of ones in a binary word

Answer:

This was written (but not necessarily invented) by Paul King. The algorithm counts the number of ones in a binary word. You could of course just look at each bit and count how many of them are ones. But that takes as many cycles as the number of bits in a word. This clever algorithm takes as many cycles as the number of ones in the word, so on average is faster (unless all your data consists of words in which all the bits are ones). I don't know if it is well known, but I have frequently shown it to younger programmers, who are always surprised by it.

I only ever saw the algorithm in assembler, but as a recursive Pascal function it would be something like this. (Asssuming that X and Y gives the bitwise 'and' of X and Y).

function CountBits(X: word): integer;
{return the number of bits that are ones in X}
begin
  if (x = 0) then
    CountBits := 0
  else
    CountBits := 1 + CountBits(X and (X - 1));
end;

This works because if X is not zero, (X and (X-1)) always has exactly one fewer ones in it than X does.

Of course making it recursive would slow it down, so I suppose the non-recursive version would be better. Something like this:

function CountBits(X: word): integer;
{return number of bits that are ones in X}
var
  temp: word;
  result: integer;
begin
  temp := X;
  result := 0;
  while temp < > 0 do
  begin
    result := result + 1;
    temp := (temp and (temp - 1));
  end;
  CountBits := result;
end;


Your non-recursive implementation can be optimized a bit further. Modern (Delphi) Pascals have a built-in "result" variable within functions. Beyond other benefits, it makes renaming functions easier, too. No hunting through for other internal name references.

Also: If you're not making the parameter a const parameter, I find it easier to read (and more efficient?) to just use the parameter in the calculations. (No need for the temp var.) Delphi would probably optimize that immediately to a register variable/ parameter, too. I also expanded the parameter and temp var. to an integer; words are only 16 bits. Integers will "grow" with the compiler and available hardware support to the largest comfortably-handled integer size within the environment.

So you'd end up with something like:

function CountBits(X: integer): integer;
{return number of bits that are ones in X}
begin
  result := 0;
  while x < > 0 do
  begin
    inc(result);
    X := (X and (X - 1));
  end;
end;


I've seen this before, but it smacks of "tricks" (which I avoid) so I fear that when I needed it I did it the obvious way by a preprepared table:

function countbits(n: cardinal): integer;
const
  bytebits: array[0..255] of byte = (0, 1, 1, 2, 1, 2, 2, 3, 1...);
    {these values generated by your program??}
begin
  result := 0;
  repeat
    inc(result, bytebits[n and $FF];
      n := n shr 8;
  until
  n = 0;
end;

Should be a lot faster and you can trade off storage against speed by using a 4-bit, 8-bit, 12-bit
or 16-bit initial array.