diff options
| Commit | ceef2b48dd810132728898a6d4b940d4b5afea9a (patch) | |
|---|---|---|
| Author | 2026-11-22 10:59:11 +0200 | |
| Committer | 2026-11-22 10:59:11 +0200 | |
| Files | 182f07003f26f1893deab117c941ead693c097a3 /src | |
| syndamia.com-ceef2b48dd810132728898a6d4b940d4b5afea9a.tar syndamia.com-ceef2b48dd810132728898a6d4b940d4b5afea9a.tar.gz syndamia.com-ceef2b48dd810132728898a6d4b940d4b5afea9a.zip | ||
| Parent | d60f782300a16f6582b22e139f6fc641184c5756 (diff) | |
3 files changed, 540 insertions, 0 deletions
| -rw-r--r-- | src/blog.du | 3 | ||||
| -rw-r--r-- | src/blog/index.du | 3 | ||||
| -rw-r--r-- | src/blog/simple-parallel-bit-count/index.du | 534 |
diff --git a/src/blog.du b/src/blog.du index 70ae473..bd6a944 100644 --- a/src/blog.du +++ b/src/blog.du @@ -10,6 +10,9 @@ Articles detailing personal experiences or exploration of certain topics. #### {i 2026} :defs +; {gb} 22 Nov   {url Simple parallel bit count explanation;/blog/simple-parallel-bit-count} +: {` Deep dive} | {` Algorithms} | {` bit count} {` optimizations} {` bitwise operations} {` C} + ; {gb} 15 Nov   {url GitLab killed itself;/blog/gitlab-killed-itself} : {` Medium dive} | {` Opinion} | {` git} {` GitLab} {` GitHub} {` SourceHut} {` Codeberg} 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   {url Simple parallel bit count explanation;/blog/simple-parallel-bit-count} +: {` Deep dive} | {` Algorithms} | {` bit count} {` optimizations} {` bitwise operations} {` C} + ; {gb} 15 Nov   {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} |