devxlogo

Counting Bits Efficiently

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.

devxblackblue

About Our Editorial Process

At DevX, we’re dedicated to tech entrepreneurship. Our team closely follows industry shifts, new products, AI breakthroughs, technology trends, and funding announcements. Articles undergo thorough editing to ensure accuracy and clarity, reflecting DevX’s style and supporting entrepreneurs in the tech sphere.

See our full editorial policy.

About Our Journalist