Jump to content

Simple parallel bit count explanation

Counting the number of set bits in an integer is not too difficult in itself. LeetCode ranks it as "easy" with the naive solution being to linearly (with respect to bit length) shift every bit and count when the least-significant bit is 1. A logarithmic (with respect to bit length) approach, popularised by Brian Kernighan, uses subtraction to effectively clear the most-significant set bit (practically "encountering" only set bits, instead of both set and unset ones).

Still, the most efficient method is to "count bits in parallel" (shown by Sean Anderson). Surprisingly enough, there don't seem to be too many explanations online. The first result in search engines is made by Stephen Brumme, though I personally find the explanation unsatisfactory. Other results seem to just cite the one from Brumme.

This post will be an attempt to explain the esoteric nature and optimisations to the underlying algorithm in the plainest way possible. Knowledge and understanding of (C-style) bit-wise operations is expected.

Inductive-style construction

I'll establish the algorithm, starting from the lowest bit length possible and moving up.

1-bit

How many bits are contained in a single-bit integer? The answer is trivial, for 0 there are zero bits and for 1 there is one bit.

What needs to be noticed is that the value itself represents the count! So, if we're making a function, we can just return the 1-bit number directly.

2-bit

Let us ask the same question for two-bit integers, while trying to use what we learned. Given that a single bit represents its own bit-count, given two bits their sum will represent the total count.

Expressing this as an arithmetic operation (in C), for a 2-bit number x, we get something like:

((x & 0b10) >> 1) + (x & 0b01)

Via the 0b10 mask we take the first bit, then shift it right to use it as a standalone bit. Then thanks to 0b01 we take the second bit (which doesn't require a shift to be used as-is). Finally, both are summed.

4-bit

We're skipping over 3-bit numbers, computers only care about powers of two and you'll see how this helps us.

Now we'll look at the same task, bit-count of 4-bit numbers using what we know so far. It should be obvious: we know how to take the count of two 2-bit numbers, just split the number and sum both counts.

Assuming we've defined the function c2(x) which does what was expressed in the previous section, we can implement the following:

c2((x & 0b1100) >> 2) + c2(x & 0b0011)

Or by simplifying the expression, we get the following straight-forward result, which shows we're just summing the bits:

( ((x & 0b1000) >> 3) + ((x & 0b0100) >> 2) ) + ( ((x & 0b0010) >> 1) + (x & 0b0001) )

Even so, our work is not done. Observation number one: the count of bits in a 2-bit number is, in itself, a 2-bit number. In other words, the largest 2-bit integer is 11, which has two bits, represented in binary as 10. Obviously 10 is a 2-bit number, we have no overflow.

Observation number two, the main concept behind this algorithm: we can concatenate numbers when they don't overflow and be able to split them away. For a moment, let us consider base-10 numbers, the ones we're all used to.

Imagine we want to sum 12 with 40 and 34 with 7. This is easy, we sum the first pair and then the second, resulting in 52 and 41. Let us now sum 1234 with 4005, the result is 5241.

Hey, this 1234 is just the concatenation of 12 and 34, 4005 is of 40 and 7 (with an added zero for alignment) and the result 5241 is just 52 and 41 concatenated together. Because no two-digit decimal sum overflows, all two-digit sums are, in practice, isolated from each other. This allows us to concatenate, do a single sum, and then split back the two sums.

Going back to 2-bit integers, it should be easy to draw the parallels between 10 + 01 = 11, 01 + 01 = 10, and the "concatenation": 1001 + 0101 = 1110. The first result can be taken with (x & 0b1100) >> 2 and the second with x & 0b0011.

This is where the parallel in "parallel bit count" comes from! In reality, we're not doing counts asynchronously/on multiple threads/cores, but we're doing multiple bit counts during one operation/instruction.

Combining both observations, it's easy to realise that since our bit counts will not overflow, we can use the concatenation "ability" to eliminate a single addition. We "start" with our 2-bit numbers already concatenated, so our first step will be:

((x & 0b1010) >> 1) + (x & 0b0101)

Now every two bits contain the bit-count of the "underlying" 2-bit integer. We'll also need to sum those two counts. The final result looks like (where x has the count in the end):

x = ((x & 0b1010) >> 1) + (x & 0b0101);
x = ((x & 0b1100) >> 2) + (x & 0b0011);

8-bit

Doubling the bit-count allows us to very naturally extend the same trick to higher bit counts. If you've understood what happened in the previous section, you should understand this solution:

x = ((x & 0b10101010) >> 1) + (x & 0b01010101); /* Find 2-bit counts */
x = ((x & 0b11001100) >> 2) + (x & 0b00110011); /* Find 4-bit counts */
x = ((x & 0b11110000) >> 4) + (x & 0b00001111); /* Find 8-bit count */

On the first line every two bits become the bit-counts of the corresponding 2-bit number at the same position. x contains four 2-bit counts. The second line sums the upper/left-most and the lower/right-most two counts into two 4-bit numbers. Finally, the third lines sums those final two numbers.

16-bit

This shouldn't need any explanation at this point:

x = ((x & 0b1010101010101010) >> 1) + (x & 0b0101010101010101); /* Find 2-bit counts */
x = ((x & 0b1100110011001100) >> 2) + (x & 0b0011001100110011); /* Find 4-bit counts */
x = ((x & 0b1111000011110000) >> 4) + (x & 0b0000111100001111); /* Find 8-bit counts */
x = ((x & 0b1111111100000000) >> 8) + (x & 0b0000000011111111); /* Find 16-bit count */

32-bit

In both Brumme's solution and LeetCode's versions of the problem we're working with 32-bit integers, so that's where we'll stop. Of course, you can extend this version to as many bits as you'd like:

x = ((x & 0b10101010101010101010101010101010) >>  1) + (x & 0b01010101010101010101010101010101); /* Find 2-bit counts */
x = ((x & 0b11001100110011001100110011001100) >>  2) + (x & 0b00110011001100110011001100110011); /* Find 4-bit counts */
x = ((x & 0b11110000111100001111000011110000) >>  4) + (x & 0b00001111000011110000111100001111); /* Find 8-bit counts */
x = ((x & 0b11111111000000001111111100000000) >>  8) + (x & 0b00000000111111110000000011111111); /* Find 16-bit counts */
x = ((x & 0b11111111111111110000000000000000) >> 16) + (x & 0b00000000000000001111111111111111); /* Find 32-bit count */

This works, feel free to try it out over on LeetCode! All differences from the more succinct version posted by Brumme and Anderson are down to optimisations.

Optimising

Do note, every final version in every section is a successful solution to the task of bit counting.

Hexadecimal constants

Binary constants take up too much space. Hex ones are the shortest:

x = ((x & 0xAAAAAAAA) >>  1) + (x & 0x55555555); /* Find 2-bit counts */
x = ((x & 0xCCCCCCCC) >>  2) + (x & 0x33333333); /* Find 4-bit counts */
x = ((x & 0xF0F0F0F0) >>  4) + (x & 0x0F0F0F0F); /* Find 8-bit counts */
x = ((x & 0xFF00FF00) >>  8) + (x & 0x00FF00FF); /* Find 16-bit counts */
x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF); /* Find 32-bit count */

Though I won't be using hex constants for the rest of the sections, because it's less visible what bits we're actually working with.

Using a single mask

On the left-hand side of every sum, we first take the bits we need and then shift. What if we first shift? Then we'll need to also shift the mask. Let's show this as a series of equivalent transformations:

  (x & 0b10101010101010101010101010101010) >> 1
= (x >> 1) & (0b10101010101010101010101010101010 >> 1)
= (x >> 1) &  0b01010101010101010101010101010101

Doing it for everything generates:

x = ((x >>  1) & 0b01010101010101010101010101010101) + (x & 0b01010101010101010101010101010101); /* Find 2-bit counts */
x = ((x >>  2) & 0b00110011001100110011001100110011) + (x & 0b00110011001100110011001100110011); /* Find 4-bit counts */
x = ((x >>  4) & 0b00001111000011110000111100001111) + (x & 0b00001111000011110000111100001111); /* Find 8-bit counts */
x = ((x >>  8) & 0b00000000111111110000000011111111) + (x & 0b00000000111111110000000011111111); /* Find 16-bit counts */
x = ((x >> 16) & 0b00000000000000001111111111111111) + (x & 0b00000000000000001111111111111111); /* Find 32-bit count */

The masks on each row/iteration are the same! We can place them outside of brackets and eliminate a single "and":

x = ((x >>  1) + x) & 0b01010101010101010101010101010101; /* Find 2-bit counts */
x = ((x >>  2) + x) & 0b00110011001100110011001100110011; /* Find 4-bit counts */
x = ((x >>  4) + x) & 0b00001111000011110000111100001111; /* Find 8-bit counts */
x = ((x >>  8) + x) & 0b00000000111111110000000011111111; /* Find 16-bit counts */
x = ((x >> 16) + x) & 0b00000000000000001111111111111111; /* Find 32-bit count */

Subtraction and multiplication

I won't call this trick an observation, because I feel it will diminish it's cleverness.

The concept is simple, we know that a - a = 0, so there might be some value, which will allows us to eliminate or simplify something. Looking at the 2-bit count, the left-hand side of the sum can be represented as:

((x >> 1) & 0b01010101010101010101010101010101)

Which we've shown is equal to:

(x & 0b10101010101010101010101010101010) >> 1

Do not forget that >> 1 is the same as division by 2. So, if we add another one of those values, we'll get:

      ((x & 0b10101010101010101010101010101010) >> 1) + ((x & 0b10101010101010101010101010101010) >> 1)
= 2 * ((x & 0b10101010101010101010101010101010) >> 1)
=     ((x & 0b10101010101010101010101010101010) >> 1) << 1
=       x & 0b10101010101010101010101010101010

An obvious observation is that we can represent x as the sum:

(x & 0b10101010101010101010101010101010) + (x & 0b01010101010101010101010101010101)

Using both of these ideas results in the following series of transformations:

      ((x >> 1) & 0b01010101010101010101010101010101)    + (x & 0b01010101010101010101010101010101)
=     ((x >> 1) & 0b01010101010101010101010101010101)    + (x & 0b01010101010101010101010101010101) + ((x >> 1) & 0b01010101010101010101010101010101) - ((x >> 1) & 0b01010101010101010101010101010101)
= 2 * ((x >> 1) & 0b01010101010101010101010101010101)    + (x & 0b01010101010101010101010101010101) - ((x >> 1) & 0b01010101010101010101010101010101)
= 2 * ((x & 0b10101010101010101010101010101010) >> 1)    + (x & 0b01010101010101010101010101010101) - ((x >> 1) & 0b01010101010101010101010101010101)
= (((x & 0b10101010101010101010101010101010) >> 1) << 1) + (x & 0b01010101010101010101010101010101) - ((x >> 1) & 0b01010101010101010101010101010101)
=   (x & 0b10101010101010101010101010101010)             + (x & 0b01010101010101010101010101010101) - ((x >> 1) & 0b01010101010101010101010101010101)
= x - ((x >> 1) & 0b01010101010101010101010101010101)

This way we eliminate one bitwise "and" operation1.

Of course, we can go further. Our goal is to get ... >> a) << a) ..., which will create our x. For the 4-bit sums we have a right-shift of 2, which corresponds to dividing by 4. We'll need to multiply by 4 and since we're given one value already, we need to add 3 times the shifted value. Writing it out we get:

      ((x >> 2) & 0b00110011001100110011001100110011)    + (x & 0b00110011001100110011001100110011)
=     ((x >> 2) & 0b00110011001100110011001100110011)    + (x & 0b00110011001100110011001100110011) + 3 * ((x >> 2) & 0b00110011001100110011001100110011) - 3 * ((x >> 2) & 0b00110011001100110011001100110011)
= 4 * ((x >> 2) & 0b00110011001100110011001100110011)    + (x & 0b00110011001100110011001100110011) - 3 * ((x >> 2) & 0b00110011001100110011001100110011)
= 4 * ((x & 0b11001100110011001100110011001100) >> 2)    + (x & 0b00110011001100110011001100110011) - 3 * ((x >> 2) & 0b00110011001100110011001100110011)
= (((x & 0b11001100110011001100110011001100) >> 2) << 2) + (x & 0b00110011001100110011001100110011) - 3 * ((x >> 2) & 0b00110011001100110011001100110011)
=   (x & 0b11001100110011001100110011001100)             + (x & 0b00110011001100110011001100110011) - 3 * ((x >> 2) & 0b00110011001100110011001100110011)
= x - 3 * ((x >> 2) & 0b00110011001100110011001100110011)

The direct problem is that we're introducing a multiplication, this operation is significantly slower than bitwise or summation/subtraction. This is why nobody ever uses it for the other counts.

All the same, I'll complete the calculation. It is fairly easy to figure out that the multiplication factor is 2a - 1 where a in this case refers to the amount by which we're right shifting. The factor for 8-bit sums will be 24 - 1 = 16 - 1 = 15, for 16-bit sums - 28 - 1 = 256 - 1 = 255, and for the 32-bit sum - 216 - 1 = 65536 - 1 = 65535.

Putting it all together we get:

x = x -     1 * ((x >>  1) & 0b01010101010101010101010101010101); /* Find 2-bit counts */
x = x -     3 * ((x >>  2) & 0b00110011001100110011001100110011); /* Find 4-bit counts */
x = x -    15 * ((x >>  4) & 0b00001111000011110000111100001111); /* Find 8-bit counts */
x = x -   255 * ((x >>  8) & 0b00000000111111110000000011111111); /* Find 16-bit counts */
x = x - 65535 * ((x >> 16) & 0b00000000000000001111111111111111); /* Find 32-bit count */

Multiplication for repeated addition

What is the maximum amount of set bits in a 32-bit integer? Obviously, that is 32 or 00100000, which takes up exactly 6 bits. Interestingly enough, after finding the 8-bit counts, every byte contains the number of ones in the corresponding byte of the original number and a single byte can store the entire count of the set bits.

Is there an efficient way to accumulate all the counts into one byte? If there is, and this operation is faster than two shifts, two sums and two masks (the 16 and 32-bit counts) we would've found an optimisation.

Evidently, there is, and this operation is multiplication. To explain what we're doing, let's look at long multiplication.

You take the first number, multiply it by the right-most digit and add it. Then you shift the number one digit to the left, multiply by the second right-most digit and add it. Shift, multiply, add, shift, multiply, add, until there are no more digits.

A while ago we talked about the idea of concatenating numbers, doing one big operation and then splitting the result. We can do something similar here, imagining the number as a concatenation, what would happen if we tried to multiply every number by 1 and also concatenated the multipliers?

Here's an example of exactly that, with the decimal numbers 123456 and 10101 (we're "multiplying" 12 by 1, 34 by 1 and 56 by 1):

      123456
*      10101
------------
      123456
    123456
+ 123456

Huh, in the middle column (in bold) we'll sum all three 2-digit numbers. In this case the result will be nonsense, since there will be overflow. Our 8-bit sums will not, since the values will be too small.

Let's try the same idea, now in the context of binary numbers and our bit-counting:

                          AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD
*                         00000001000000010000000100000001
----------------------------------------------------------
                          AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD
                  AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD
          AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD
+ AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD

Would you look at that, the middle column will sum all bytes! Furthermore, we're working with 32-bit integers, so everything after the right-most 32 bits will not exists, meaning our actual calculation will be:

  AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD
* 00000001000000010000000100000001
----------------------------------
  AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD
  BBBBBBBBCCCCCCCCDDDDDDDD
  CCCCCCCCDDDDDDDD
+ DDDDDDDD

Getting the top-most byte is as easy as doing a right-shift by 24 (32 - 8) bits2!

To illustrate, we could also do the same for the 4-bit numbers:

  AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHH
* 00010001000100010001000100010001
----------------------------------
  AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHH
  BBBBCCCCDDDDEEEEFFFFGGGGHHHH
  CCCCDDDDEEEEFFFFGGGGHHHH
  DDDDEEEEFFFFGGGGHHHH
  EEEEFFFFGGGGHHHH
  FFFFGGGGHHHH
  GGGGHHHH
+ HHHH

However, if our count is larger than 15 we'll overflow and the result will be wrong.

Nonetheless, we could replace the last two operations, where we find 16-bit and 32-bit counts, with the following:

x = (x * 0b00000001000000010000000100000001) >> 24; /* Find 32-bit count from 8-bit counts */

Constructing Brumme's implementation

We now have everything needed to create the most optimal solution to the bit-counting task!

First, we take the single mask variant:

x = ((x >>  1) + x) & 0b01010101010101010101010101010101; /* Find 2-bit counts */
x = ((x >>  2) + x) & 0b00110011001100110011001100110011; /* Find 4-bit counts */
x = ((x >>  4) + x) & 0b00001111000011110000111100001111; /* Find 8-bit counts */
x = ((x >>  8) + x) & 0b00000000111111110000000011111111; /* Find 16-bit counts */
x = ((x >> 16) + x) & 0b00000000000000001111111111111111; /* Find 32-bit count */

Replace binary constants with hex ones:

x = ((x >>  1) + x) & 0x55555555; /* Find 2-bit counts */
x = ((x >>  2) + x) & 0x33333333; /* Find 4-bit counts */
x = ((x >>  4) + x) & 0x0F0F0F0F; /* Find 8-bit counts */
x = ((x >>  8) + x) & 0x00FF00FF; /* Find 16-bit counts */
x = ((x >> 16) + x) & 0x0000FFFF; /* Find 32-bit count */

Apply subtraction and multiplication to the 2-bit count:

x = x - ((x >> 1) & 0x55555555; /* Find 2-bit counts */
x = ((x >>  2) + x) & 0x33333333; /* Find 4-bit counts */
x = ((x >>  4) + x) & 0x0F0F0F0F; /* Find 8-bit counts */
x = ((x >>  8) + x) & 0x00FF00FF; /* Find 16-bit counts */
x = ((x >> 16) + x) & 0x0000FFFF; /* Find 32-bit count */

Supersede the 16-bit and 32-bit counts with a single multiplication and shift:

x = x - ((x >> 1) & 0x55555555; /* Find 2-bit counts */
x = ((x >>  2) + x) & 0x33333333; /* Find 4-bit counts */
x = ((x >>  4) + x) & 0x0F0F0F0F; /* Find 8-bit counts */
x = (x * 0x01010101) >> 24; /* Find 32-bit count */

Et voilĂ !

Well, in reality there are a couple of differences, in his implementation the 4-bit counts uses the mask twice and the 8-bit counts is split on two lines. Those differences are fairly insignificant, the code does the exact same thing.

Simplification on Sean Anders' page

Going back to the "best method", shown in Bit Twiddling Hacks:

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

We can see, a familiar sight!

The primary difference is using the result of 8-bit counts directly in the final expression, instead of storing it again in our value. Clever, on the final 32-bit count we use x (or v in this code) only once, so this works.

Appendix A: Checking the one-mask variant

In both optimized implementations, the 4-bit count is written as:

x = (x & 0x33333333) + ((x >> 2) & 0x33333333);

Instead of:

x = (x + (x >> 2)) & 0x33333333;

We can easily check if this matters for performance. Compiling a C implementation with -S will output the resultant assembly.

Using clang version 21.1.8 I get the following diff:

$ diff two_masks.s one_mask.s
22d21
<       andl    $858993459, %eax                # imm = 0x33333333
25d23
<       andl    $858993459, %ecx                # imm = 0x33333333
26a25
>       andl    $858993459, %eax                # imm = 0x33333333

My version results in one less instruction, it is slightly more optimal.

Testing with gcc version 15.2.0 results in something slightly different:

$ diff two_masks.s one_mask.s
19c19
<       andl    $858993459, %eax
---
>       shrl    $2, %eax
22,23d21
<       shrl    $2, %eax
<       andl    $858993459, %eax
24a23
>       andl    $858993459, %eax

We remove one shrl and replace one andl with a shrl. Could be slightly faster?

Hold on, I didn't compile using optimisations, comparing after using -O3:

$ diff two_masks.s one_mask.s
9,12d8
<       movl    %edi, %eax
<       shrl    %eax
<       andl    $1431655765, %eax
<       subl    %eax, %edi
13a10,14
>       movl    %edi, %eax
>       shrl    %edx
>       andl    $1431655765, %edx
>       subl    %edx, %eax
>       movl    %eax, %edi
15c16
<       andl    $858993459, %edx
---
>       addl    %eax, %edi
17,18c18
<       addl    %edi, %edx
<       movl    %edx, %eax
---
>       movl    %edi, %eax
20c20
<       addl    %edx, %eax
---
>       addl    %edi, %eax

Now this is something! Excluding some changes in addresses, this post's version adds a movl instruction and removes an addl instruction.

Looking at Agner Fog's x86-64 instruction table, it looks to me that andl, shrl, movl and addl should all take about one operation. Thus, my conclusion is that the performance difference probably does not matter, at least with modern compilers and hardware.

Appendix B: Shifting is not distributive

While figuring out all the needed transformations for this algorithm to work, I made the following mistake:

  ((x & 0b10101010101010101010101010101010) >> 1) + (x & 0b01010101010101010101010101010101)
= ((x & 0b10101010101010101010101010101010) >> 1) + (x & 0b01010101010101010101010101010101) + x - x
= ((x & 0b10101010101010101010101010101010) >> 1) + (x & 0b01010101010101010101010101010101) + x - (x & 0b10101010101010101010101010101010) - (x & 0b01010101010101010101010101010101)
= ((x & 0b10101010101010101010101010101010) >> 1) + x - (x & 0b10101010101010101010101010101010)
= ((x & 0b10101010101010101010101010101010) >> 1) + x - ((x & 0b10101010101010101010101010101010) >> 0)
= ((x & 0b10101010101010101010101010101010) >> (1 - 0)) + x
= x - ((x & 0b10101010101010101010101010101010) >> 1)

The issue should be evident, (x >> a) + (x >> b) does NOT equal x >> (a + b) for all possible values. It's fairly straight forward to show this is the case:


  1. Subtraction and addition function very similarly, so their performance is practically equal.

  2. On an unsigned integer in the general case, since that would invoke a logical shift. In our situation, the number 32 does not flip the most-significant bit, so this detail does not matter.

︽