Quote:Original post by Lode
I still don't get how it works though, or what numbers you have to put in there to make it work with 64-bit or 128-bit integers.

Quote:Original post by implicit
Out of curiosity have any of you guys found any interesting uses for the population count operation?

Quote:Original post by LodeI still don't get how it works though, or what numbers you have to put in there to make it work with 64-bit or 128-bit integers.

Here's the C code in an easier to read format:Taken from http://bits.stephan-brumme.com/countBits.html01: unsigned int countBits(unsigned int x)02: {03:   // count bits of each 2-bit chunk04:   x  = x - ((x >> 1) & 0x55555555);05:   // count bits of each 4-bit chunk06:   x  = (x & 0x33333333) + ((x >> 2) & 0x33333333);07:   // count bits of each 8-bit chunk08:   x  = x + (x >> 4);09:   // mask out junk10:   x &= 0xF0F0F0F;11:   // add all four 8-bit chunks12:   return (x * 0x01010101) >> 24;13: }I'll go through it step by step with an 8-bit exampleBit labels: | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |Number:       1   1   0   0   1   0   0   1Step 1: Count the number of bits in every 2-bit chunk.  This means we want to count how many bits are set in [1,0], [3,2], [5,4], and [7,6].  The result will be put into the same bit slots that we are counting.  Mask used: 0 1 0 1 0 1 0 1  So for every two bits, the mask is 01  Notice how the substraction gives the correct value for every possible bit value.  Bits 1, 0:    01              - 00     (01 shifted to the right one then ANDED with 01)              -----                01  Bits 3, 2:    10              - 01     (10 shifted to the right one then ANDED with 01)              -----                01  Bits 5, 4:    00              - 00     (00 shifted to the right one then ANDED with 01)              -----                00  Bits 7, 6:    11              - 01     (11 shifted to the right one then ANDED with 01)              -----                10  Value of x after Step 1:    | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |                                1   0   0   0   0   1   0   1  Every two bits now contains the number of bits that were set in the corresponding two bits of the original value.Step 2: Add each 2-bit count to its neighbor.  This means we want to add [1,0] to [3,2] and [7,6] to [5,4].    Mask used: 0 0 1 1 0 0 1 1  The mask is used to clear bits so that the final result can reside in the four adjacent bits.  So [3,2] + [1,0] will reside in [3,2,1,0] and [7,6] + [5,4] will be in [7,6,5,4].  Bits 3,2,1,0:       0001  (0101 ANDED with 0011)                    + 0001  (0101 shifted right 2, then ANDED with 0011)                    -----                      0010  Bits 7,6,5,4:       0000  (1000 ANDED with 0011)                    + 0010  (1000 shifted right 2, then ANDED with 0011)                     -----                      0010  Value of x after Step 2:    | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |                                0   0   1   0   0   0   1   0  Every four bits now contains the number of bits that were set in the corresponding 4 bits of the original value.Step 3: Add each 4-bit count to its neighbor.  This means we want to add [3,2,1,0] to [7,6,5,4].    No mask needed.  The result will be placed in the corresponding 8 bits.  Bits 7,6,5,4,3,2,1,0:       00100010                              + 00000010  (00100010 shifted right by 4)                            ----------                              00100100  Value of x after step 3:    | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |                                0   0   1   0   0   1   0   0  The lower four bits of each byte now contains the number of bits set in the corresponding byte of the original value.Step 4: Mask out top 4 bits of every byte, which is junk data.  Mask used: 1111000  Value of x after step 4:    | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |                                0   0   0   0   0   1   0   0Step 5: Add lower 4 bits of every byte together.  For a single byte, this step is not really necessary. The final result is already available, which is 4.  So for step 5 and 6, we will switch over to 32-bit and a made up intermediate result shown below.  For any junk of data larger than a byte, then we need to do this.  What we have at the end of step 4 is the number of bits set in each byte, which are located in the lower 4 bits of each byte.  We want to add together all these numbers. Multiplying by 0x01010101 accomplishes this because multiplication is addition with a few shifts included.  The result will end up being in the most significant byte.  Here is what it looks like, X denotes a 0 added because of a shift:                                00000100 00000011 00000110 00000001  (intermediate result, current x value)                              x 00000001 00000001 00000001 00000001  (0x01010101 to be multiplied to intermediate result)                              ------------------------------------                               |00000100|00000011 00000110 00000001                              0|00000000|00000000 00000000 0000000X                             00|00000000|00000000 00000000 000000XX                            000|00000000|00000000 00000000 00000XXX                           0000|00000000|00000000 00000000 0000XXXX                          00000|00000000|00000000 00000000 000XXXXX                         000000|00000000|00000000 00000000 00XXXXXX                        0000000|00000000|00000000 00000000 0XXXXXXX                       00000100|00000011|00000110 00000001 XXXXXXXX                               |        |                     0 00000000|00000000|00000000 0000000X XXXXXXXX                    00 00000000|00000000|00000000 000000XX XXXXXXXX                   000 00000000|00000000|00000000 00000XXX XXXXXXXX                  0000 00000000|00000000|00000000 0000XXXX XXXXXXXX                 00000 00000000|00000000|00000000 000XXXXX XXXXXXXX                000000 00000000|00000000|00000000 00XXXXXX XXXXXXXX               0000000 00000000|00000000|00000000 0XXXXXXX XXXXXXXX              00000100 00000011|00000110|00000001 XXXXXXXX XXXXXXXX                               |        |            0 00000000 00000000|00000000|0000000X XXXXXXXX XXXXXXXX           00 00000000 00000000|00000000|000000XX XXXXXXXX XXXXXXXX          000 00000000 00000000|00000000|00000XXX XXXXXXXX XXXXXXXX         0000 00000000 00000000|00000000|0000XXXX XXXXXXXX XXXXXXXX        00000 00000000 00000000|00000000|000XXXXX XXXXXXXX XXXXXXXX       000000 00000000 00000000|00000000|00XXXXXX XXXXXXXX XXXXXXXX      0000000 00000000 00000000|00000000|0XXXXXXX XXXXXXXX XXXXXXXX     00000100 00000011 00000110|00000001|XXXXXXXX XXXXXXXX XXXXXXXX     --------------------------------------------------------------Final result:                  |        |     [ All overflow, ignored  ]|00001110|00000000 00000000 00000000  Value of x after step 5:  00001110 00000000 00000000 00000000Step 6: Shift x right by 24 bits to put count into the lowest byte.  Final result: 00000000 00000000 00000000 00001110 (equal to 14) Now the result can be read from x like any other integer.