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 (X1)) always has exactly one fewer
ones in it than X does.
Of course making it recursive would slow it down, so I suppose the nonrecursive
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 nonrecursive implementation can be optimized a bit further. Modern (Delphi)
Pascals have a builtin "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 comfortablyhandled 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
4bit, 8bit, 12bit
or 16bit initial array.
