Login | Register   
RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX

Tip of the Day
Home » Tip Bank » C++
Language: C++
Expertise: Intermediate
Dec 12, 2001

Counting Bits Efficiently

Sometimes you need to know the number of bits set in a word. I often see code to count the number set bits written as a loop, processing one bit at a time. There is a much faster method that uses a few statements of straight-line code.

You can think of a 32-bit number as a vector of 32 1-bit numbers side-by side. Replace each of the 16 pairs of 1-bit numbers with a 2-bit number that is the sum of the 1-bit numbers. Next replace each of the 8 pairs of 2-bit numbers with a 4-bit number that is the sum of the 2-bit numbers. Repeat until you have one 32-bit number. You can use standard integer addition to add all the numbers at once, provided you make sure that none of the fields overflow into an adjacent number.

typedef unsigned int UINT32;

UINT32 count_bits_first_version(UINT32 bits)
    bits = ((bits >> 1) & 0x55555555) + _
(bits & 0x55555555);
    bits = ((bits >> 2) & 0x33333333) + _
(bits & 0x33333333);
    bits = ((bits >> 4) & 0x0F0F0F0F) + _
(bits & 0x0F0F0F0F);
    bits = ((bits >> 8) & 0x00FF00FF) + _
(bits & 0x00FF00FF);
    bits = ((bits >>16) & 0x0000FFFF) + _
(bits & 0x0000FFFF);
    return bits;


This code can be made faster by removing unnecessary operations. Here is the fully optimized version.

UINT32 count_bits(UINT32 bits)
    bits = bits - ((bits >> 1) & 0x55555555);
    bits = ((bits >> 2) & 0x33333333) + _
(bits & 0x33333333);
    bits = ((bits >> 4) + bits) & 0x0F0F0F0F;
    return (bits * 0x01010101) >> 24;


The first line saves an AND instruction by exploiting this clever relationship for each pair of bits. The two bits 'ab' represent the number 2a+b. To count the bits we subtract 'a' (i.e. 2a+b - a = a+b).

The last line uses a multiplication to do several additions at once.
Stephen Adams
Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.



Thanks for your registration, follow us on our social networks to keep up-to-date