Summary Files Commits Branches @commit @diff @stats
path: root / src / blog / simple-parallel-bit-count / index.du
blob: 8b7fd0d4f6f4e01159da80c21c1164b9d229a8aa (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
'def title Simple parallel bit count explanation
'def  desc Explaining the parallel bit count algorithm and its optimisations in a simple manner

# {title}

{pagenav 12 min;15 Nov 2026;22 Nov 2026}

:contents
:numbered
1. {uhref Inductive-style construction}
.numbered
1. {uhref 1-bit}
2. {uhref 2-bit}
3. {uhref 4-bit}
4. {uhref 8-bit}
5. {uhref 16-bit}
6. {uhref 32-bit}

2. {uhref Optimising}
.numbered
1. {uhref Hexadecimal constants}
1. {uhref Using a single mask}
1. {uhref Subtraction and multiplication}
1. {uhref Multiplication for repeated addition}

3. {uhref Constructing Brumme's implementation}
.numbered
1. {uhref Simplification on Sean Anders' page}

4. {uhref Appendix A: Checking the one-mask variant}
5. {uhref Appendix B: Shifting is not distributive}



Counting the number of set bits in an integer is not too difficult in itself.
{url LeetCode ranks it as "easy";https://leetcode.com/problems/counting-bits/description/} with the {url naive solution;https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive} 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, {url popularised by Brian Kernighan;https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan}, uses subtraction to effectively clear the most-significant {b set} bit (practically "encountering" only set bits, instead of both set and unset ones).

Still, the most efficient method is to {url "count bits in parallel";https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel} (shown by Sean Anderson).
Surprisingly enough, there don't seem to be too many explanations online.
{url The first result in search engines is made by Stephen Brumme;https://bits.stephan-brumme.com/countBits.html}, though I personally find the explanation unsatisfactory.
{url Other results;https://ivandemarino.me/posts/count-bits-set-in-parallel/} 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 {b 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 {b 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:

```c
((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 {b 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:

```c
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:

```c
( ((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 {b no overflow}.

Observation number two, the main concept behind this algorithm: {b 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 {b 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:

```c
((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):

```c
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:

```c
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:

```c
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:

```c
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 {url LeetCode;https://leetcode.com/problems/counting-bits/description/}!
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:

```c
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:

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

Doing it for everything generates:

```c
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":

```c
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:

```c
((x >> 1) & 0b01010101010101010101010101010101)

Which we've shown is equal to:

```c
(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:

```c
      ((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:

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

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

```c
      ((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" operation{fn Subtraction and addition function very similarly, so their performance is practically equal.}.

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:

```c
      ((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 {` 2{^ a} - 1} where {` a} in this case refers to the amount by which we're right shifting.
The factor for 8-bit sums will be {` 2{^ 4} - 1 = 16 - 1 = 15}, for 16-bit sums - {` 2{^ 8} - 1 = 256 - 1 = 255}, and for the 32-bit sum - {` 2{^ 16} - 1 = 65536 - 1 = 65535}.

Putting it all together we get:

```c
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 {b 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 {url long multiplication;https://en.wikipedia.org/wiki/Multiplication_algorithm#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
------------
      {b 12}3456
    12{b 34}56
+ 1234{b 56}

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
----------------------------------------------------------
                          {b AAAAAAAA}BBBBBBBBCCCCCCCCDDDDDDDD
                  AAAAAAAA{b BBBBBBBB}CCCCCCCCDDDDDDDD
          AAAAAAAABBBBBBBB{b CCCCCCCC}DDDDDDDD
+ AAAAAAAABBBBBBBBCCCCCCCC{b DDDDDDDD}

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
----------------------------------
  {b AAAAAAAA}BBBBBBBBCCCCCCCCDDDDDDDD
  {b BBBBBBBB}CCCCCCCCDDDDDDDD
  {b CCCCCCCC}DDDDDDDD
+ {b DDDDDDDD}

Getting the top-most byte is as easy as doing a right-shift by 24 ({` 32 - 8}) bits{fn On an unsigned integer in the general case, since that would invoke a {url logical shift;https://en.wikipedia.org/wiki/Logical_shift}. In our situation, the number 32 does not flip the most-significant bit, so this detail does not matter.}!

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

```
  AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHH
* 00010001000100010001000100010001
----------------------------------
  {b AAAA}BBBBCCCCDDDDEEEEFFFFGGGGHHHH
  {b BBBB}CCCCDDDDEEEEFFFFGGGGHHHH
  {b CCCC}DDDDEEEEFFFFGGGGHHHH
  {b DDDD}EEEEFFFFGGGGHHHH
  {b EEEE}FFFFGGGGHHHH
  {b FFFF}GGGGHHHH
  {b GGGG}HHHH
+ {b HHHH}

{b 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:

```c
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:

```c
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:

```c
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:

```c
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:

```c
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 {url Bit Twiddling Hacks;https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel}:

>
```c
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:

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

Instead of:

```c
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:

```
'emplace
$ 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
'endemplace

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

Testing with gcc version 15.2.0 results in something slightly different:

```
'emplace
$ 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
'endemplace

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}:

```
'emplace
$ 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
'endemplace

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

Looking at {url Agner Fog's x86-64 instruction table;https://www.agner.org/optimize/instruction_tables.pdf}, 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 {b mistake}:

```c
  ((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 {b NOT} equal {` x >> (a + b)} for all possible values.
It's fairly straight forward to show this is the case:
.bulleted
- {` (5 >> 1) + (5 >> 0) = 2 + 5 = 7}
- {` 5 >> (1 + 0) = 5 >> 1 = 2}
- {` 7 != 2}
- QED

{footnotes}