davidmaxwaterman

April 28th, 2008, 04:51 AM

Hi,

I've been looking at the online solutions to the problem of how to count the number of bits set to '1' in a byte (or whatever).

Here's some I've found - some also include explanations: one (http://infolab.stanford.edu/~manku/bitcount/bitcount.html), two (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive), three (http://groups.google.com/group/comp.graphics.algorithms/msg/43dfb1f4a0f08441), and four (http://aggregate.org/MAGIC/#Population%20Count%20(Ones%20Count)).

Most of them I can understand fairly easily. For example, the naïve one is obvious, and the optimisations to it are straight forward too. The lookup table solution is also easy (though debatably it's not really working anything out).

However, the one involving magic binary numbers I still cannot 'get my head around'. There are a few 'explanations' of how it works in the links above, but nothing really explains it well enough for me to grasp the basic concepts. The post on comp.graphics.algorithms (http://groups.google.com/group/comp.graphics.algorithms/msg/43dfb1f4a0f08441) comes closest, but still no cigar :|

Can anyone help me understand what is going on - from the most basic level - or refer me to something that will help?

Thanks!

Max.

I've been looking at the online solutions to the problem of how to count the number of bits set to '1' in a byte (or whatever).

Here's some I've found - some also include explanations: one (http://infolab.stanford.edu/~manku/bitcount/bitcount.html), two (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive), three (http://groups.google.com/group/comp.graphics.algorithms/msg/43dfb1f4a0f08441), and four (http://aggregate.org/MAGIC/#Population%20Count%20(Ones%20Count)).

Most of them I can understand fairly easily. For example, the naïve one is obvious, and the optimisations to it are straight forward too. The lookup table solution is also easy (though debatably it's not really working anything out).

However, the one involving magic binary numbers I still cannot 'get my head around'. There are a few 'explanations' of how it works in the links above, but nothing really explains it well enough for me to grasp the basic concepts. The post on comp.graphics.algorithms (http://groups.google.com/group/comp.graphics.algorithms/msg/43dfb1f4a0f08441) comes closest, but still no cigar :|

Can anyone help me understand what is going on - from the most basic level - or refer me to something that will help?

Thanks!

Max.