Bit Counting Methods Overview

Counting the number of bits set to “1” in a number is a classic programming problem. Donald Knuth discusses solution methods in his classic work.

This problem matters for three reasons. First, several solution methods differ drastically in performance, and choosing the right implementation can significantly speed up your code. Second, it has many practical applications in routing protocols and search. Third, it appears in interviews at major companies.

Counting methods fall into three categories: shifting, algebraic logic, and table lookup.

• Shifting
• Algebraic logic
• Table lookup
• Performance Comparison
• Further Reading

Shifting

These methods count bits by gradually shifting the number right. Variations (clearing the rightmost set bit instead of shifting the entire number) provide speed gains when data is dominated by “0”s or “1”s. Overall, this is the slowest category.

Algebraic logic

These methods use mathematical operations, such as grouping bits within a number in several passes. One method first splits bits into pairs, converting the number of ones in each pair to binary representation (00 -> 00, 01 -> 01, 10 -> 01, 11 -> 10), then groups by 4 bits, 8, and so on. These methods run about four times faster than iterative counting.

Table lookup

These methods first build lookup tables in the form [number]->[number of bits set to “1”] and then use them for fast value retrieval. Table size varies (8-16-… bits). These methods are fastest, especially on large data volumes, when the time spent calculating tables becomes negligible compared to counting time itself.

Performance Comparison

Here are benchmark results from various algorithms on my machine (Darwin Kernel Version 10.3.0, Intel Core 2 Duo 2.26 GHz). I compiled with speed optimization (-O3 and other flags); source code is here.

 8-bit lookup table calculation took 0.32 ms
 16-bit lookup table calculation took 2.34 ms

---> Shitfing methods
 Iterated 4.646 sec 21.524 Mcps
 Sparse 3.475 sec 28.775 Mcps
 Dense 3.670 sec 27.251 Mcps

---> Algebraic methods
 Parallel 1.172 sec 85.328 Mcps
 Nifty 1.204 sec 83.083 Mcps
 Hakmem 1.217 sec 82.193 Mcps

---> Table lookup methods
 Precomp 8 0.732 sec 136.684 Mcps
 Precomp 16 0.688 sec 145.268 Mcps

The slowest method runs almost seven times slower than the fastest, while the overhead of creating lookup tables is minimal—measured in milliseconds.

Further Reading

You can easily find specific algorithms online. Start with Puzzle: Fast Bit Counting for details. Also check out Bit Twiddling Hacks, which contains extensive information about various operations on bits and bit arrays.