Population count in arrays
The function that returns the number of 1-bits of a binary word is called population count or side way addition. We will call it popc for short.
It is an important task that occurs in several contexts. Some computers have even a special machine instruction for it, e.g.\ it is called SADD (on a Mark I), POPCNT (in the SSE4.2 instruction set) or VPCNT (on a NEC SX-4).
Since many current architectures (like the Intel i386) do not have a machine level population count, algorithms that compute the population count with simple logic and arithmetic operations are still important.
In this paper Y. Edel and I give an algorithm for counting the 1-bits in the columns of a bit-matrix, i.e. for the "vertical population count" problem, which arises in some contexts. Such an algorithm is even on machines with build in population count instruction of importance, as it is expensive to transpose a binary matrix.
We implementet our new algorithm and serverel other algorithms for the population count in C. We use a newly devolped literate programming system to document the code.
Your can find the source-code of our programm here. You can also directly download the C Source and the documentation in PDF.
