Summary Files Commits Branches @commit @diff @stats
path: root / src / blog
diff options
context:
space:
mode:
Commitceef2b48dd810132728898a6d4b940d4b5afea9a (patch)
Author
 Syndamia <kamen@syndamia.com>
2026-11-22 10:59:11 +0200
Committer
 Syndamia <kamen@syndamia.com>
2026-11-22 10:59:11 +0200
Files182f07003f26f1893deab117c941ead693c097a3 /src/blog
syndamia.com-ceef2b48dd810132728898a6d4b940d4b5afea9a.tar
syndamia.com-ceef2b48dd810132728898a6d4b940d4b5afea9a.tar.gz
syndamia.com-ceef2b48dd810132728898a6d4b940d4b5afea9a.zip
Parentd60f782300a16f6582b22e139f6fc641184c5756 (diff)
feat(blog): Write "Simple parallel bit count explanation" post HEAD master
2 files changed, 537 insertions, 0 deletions
-rw-r--r--src/blog/index.du3
-rw-r--r--src/blog/simple-parallel-bit-count/index.du534
diff --git a/src/blog/index.du b/src/blog/index.du
index 70ae473..bd6a944 100644
--- a/src/blog/index.du
+++ b/src/blog/index.du
@@ -10,6 +10,9 @@ Articles detailing personal experiences or exploration of certain topics.
#### {i 2026}
:defs
+; {gb} 22 Nov &emsp; {url Simple parallel bit count explanation;/blog/simple-parallel-bit-count}
+: {` Deep dive} | {` Algorithms} | {` bit count} {` optimizations} {` bitwise operations} {` C}
+
; {gb} 15 Nov &emsp; {url GitLab killed itself;/blog/gitlab-killed-itself}
: {` Medium dive} | {` Opinion} | {` git} {` GitLab} {` GitHub} {` SourceHut} {` Codeberg}
diff --git a/src/blog/simple-parallel-bit-count/index.du b/src/blog/simple-parallel-bit-count/index.du
new file mode 100644
index 0000000..8b7fd0d
--- /dev/null
+++ b/src/blog/simple-parallel-bit-count/index.du
@@ -0,0 +1,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}