Author: Jonas Bilinkevicius

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).
1   
2   function CountBits(X: word): integer;
3   {return the number of bits that are ones in X}
4   begin
5     if (x = 0) then
6       CountBits := 0
7     else
8       CountBits := 1 + CountBits(X and (X - 1));
9   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:
10  
11  function CountBits(X: word): integer;
12  {return number of bits that are ones in X}
13  var
14    temp: word;
15    result: integer;
16  begin
17    temp := X;
18    result := 0;
19    while temp < > 0 do
20    begin
21      result := result + 1;
22      temp := (temp and (temp - 1));
23    end;
24    CountBits := result;
25  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:
26  
27  function CountBits(X: integer): integer;
28  {return number of bits that are ones in X}
29  begin
30    result := 0;
31    while x < > 0 do
32    begin
33      inc(result);
34      X := (X and (X - 1));
35    end;
36  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:
37  
38  function countbits(n: cardinal): integer;
39  const
40    bytebits: array[0..255] of byte = (0, 1, 1, 2, 1, 2, 2, 3, 1...);
41      {these values generated by your program??}
42  begin
43    result := 0;
44    repeat
45      inc(result, bytebits[n and $FF];
46        n := n shr 8;
47    until
48    n = 0;
49  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.