2 ms·
> Out of curiosity, what is this weird way of computing popcount you mention? I haven't seen it before. So lets just do 8-bits at a time, in binary. It makes i
by dragontamer 5y ago
> Out of curiosity, what is this weird way of computing popcount you mention? I haven't seen it before.
So lets just do 8-bits at a time, in binary. It makes it clear what's going on.
Your 8-bit number is: x = x0 x1 x2 x3 x4 x5 x6 x7
* 0x55 is 01010101 in binary.
* 0xAA is 10101010 in binary.
* (x & 0x55) is (0 & x0) (1 & x1) (0 & x2) (1 & x3)...
* (x & 0xaa) is (1 & x0) (0 & x1) (1 & x2) ...
* (x & 0x55) + ((x & 0xaa) >> 1) is: |x0 + x1|,|x2 + x3|,|x4+x5|, |x6+x7|, where |blahblah| is a 2-bit number taking up 2-bits of the 8-bit number.
* step2 = (x & 0x55) + ((x & 0xaa) >> 1)
* (step2 & 0x33) is now |00| |x2+x3| |00| |x6+x7|
* (step2 & 0xcc) is now |x0+x1| |00| |x4+x5| |00|
* (step2 & 0x33) + ((step2 & 0xcc) >> 2) is //x0+x1+x2+x3// //x4+x5+x6+x7//, where //blah// is a 4-bit number.
You probably can figure out the last step at this point. Take the bottom 4 bits and add them with the top 4 bits.
A 2-bit number (such as |x0+x1|) can only take on 3 values: 0, 1, or 2. As such, |x0+x1| will never "carry" outside of the 2-bit space you've allocated for it.
Similarly, a 4-bit number (such as //x0+x1+x2+x3//) can only take on 5 values: 0, 1, 2, 3, 4. The 4-bits you've allocated can take on values all the way up to 16, so you also never have to worry about overflow.
- a1369209993 5y agoDeliberately more obviously 'weird' version, from memory: uint64_t x = ...; for(size_t i = 1; i<UINT_BIT ;i*=2) // loop unroll { unsigned m = UINT_MAX / ((1<<i)+1); // constant-fold // divide 2^(2k)-1 by 2^k+1 to get 2^k-1 in each group // 2k-bit group means 2^k-1 sets bottom half x = (x & m) + (x>>i & m); // we can save a AND w/o carry but 1-bit and 2-bit // need 2 ANDs to prevent carry between groups // x = (x + (x>>i)) & m; }