• Create Account

### #Actualalvaro

Posted 05 October 2012 - 12:25 PM

This code (or similar) is somewhere in that bithacks page wqking linked:

```unsigned popcount(unsigned x) {
x -= (x >> 1) & 0x55555555u;
x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
x = (x + (x >> 4)) & 0x0f0f0f0fu;
return (x * 0x01010101u) >> 24; // assumes unsigned is 32 bits
}
```

That function scares me...

Yeah, it is kind of scary... Let me see if I can break it down for you:

The general plan is to treat the unsigned integer initially as 32 integers of size 1 bit each. We'll pair up these 1-bit numbers and add them. The result is 16 integers of size 2 bits. We'll then pair those up, add them together and get 8 integers of size 4 bits. Then pair them up, add the pairs together and we'll have 4 integers of size 8 bits. At this point we use one final trick to compute the sum of all 4, and that's our answer.

For the first step, we need to map every 2 bits by the following table:
00 -> 00
01 -> 01
10 -> 01
11 -> 10

Notice that in the first two cases we aren't changing anything, and in the other two, we are just subtracting one. So we can do that by just computing `x-=x>>1' (if x were a 2-bit integer). Since we are doing this 16 times in parallel, we need to select the appropriate bits after the shift:
`x -= (x >> 1) & 0x55555555u; // 0x55555555u is 01010101010101010101010101010101 in binary`

So now x can be interpreted as 16 2-bit integers, whose sum we are trying to compute. The next two steps are very similar, and easier to understand than the previous one:
```x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
x = (x + (x >> 4)) & 0x0f0f0f0fu;```

By now x can be seen as 4 8-bit integers. In order to compute their sum, let's see what happens when we multiply ABCD times 1111 (in base 256):
```   ABCD
x 1111
------
ABCD
ABCD
ABCD
ABCD
-------
abcdefg```
Notice that there is no carry in this sum, because all the digits A, B, C and D are at most 8. Since we are doing this whole thing in 32-bit arithmetic, abc is lost to overflow, and the result of the multiplication is really just defg. As you see d=A+B+C+D, and we can extract it with a shift 24 bits to the right.

`return (x * 0x01010101u) >> 24; // assumes unsigned is 32 bits`

Are you less scared now? ;)

### #1alvaro

Posted 05 October 2012 - 12:24 PM

This code (or similar) is somewhere in that bithacks page wqking linked:

```unsigned popcount(unsigned x) {
x -= (x >> 1) & 0x55555555u;
x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
x = (x + (x >> 4)) & 0x0f0f0f0fu;
return (x * 0x01010101u) >> 24; // assumes unsigned is 32 bits
}
```

That function scares me...

Yeah, it is kind of scary... Let me see if I can break it down for you:

The general plan is to treat the unsigned integer initially as 32 integers of size 1 bit each. We'll pair up these 1-bit numbers and add them. The result is 16 integers of size 2 bits. We'll then pair those up, add them together and get 8 integers of size 4 bits. Then pair them up, add the pairs together and we'll have 4 integers of size 8 bits. At this point we use one final trick to compute the sum of all 4, and that's our answer.

For the first step, we need to map every 2 bits by the following table:
00 -> 00
01 -> 01
10 -> 01
11 -> 10

Notice that in the first two cases we aren't changing anything, and in the other two, we are just subtracting one. So we can do that by just computing `x-=x>>1' (if x were a 2-bit integer). Since we are doing this 16 times in parallel, we need to select the appropriate bits after the shift:
`x -= (x >> 1) & 0x55555555u; // 0x55555555u is 01010101010101010101010101010101 in binary`

So now x can be interpreted as 16 2-bit integers, whose sum we are trying to compute. The next two steps are very similar, and easier to understand than the previous one:
```x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
x = (x + (x >> 4)) & 0x0f0f0f0fu;```

By now x can be seen as 4 8-bit integers. In order to compute their sum, let's see what happens when we multiply ABCD times 1111 (in base 256):
```    ABCD
x 1111
------
ABCD
ABCD
ABCD
ABCD
-------
abcdefg```
Notice that there is no carry in this sum, because all the digits A, B, C and D are at most 8. Since we are doing this whole thing in 32-bit arithmetic, abc is lost to overflow, and the result of the multiplication is really just defg. As you see d=A+B+C+D, and we can extract it with a shift 24 bits to the right.

`return (x * 0x01010101u) >> 24; // assumes unsigned is 32 bits`

Are you less scared now? ;)

PARTNERS