How to quickly count bits into separate bins in a series of ints on Sandy Bridge?

Look at Bit Twiddling Hacks

• Counting bits set
  • Counting bits set, naive way
  • Counting bits set by lookup table
  • Counting bits set, Brian Kernighan's way
  • Counting bits set in 12, 24, or 32-bit words using 64-bit instructions
  • Counting bits set, in parallel
  • Count bits set (rank) from the most-significant bit upto a given position
  • Select the bit position (from the most-significant bit) with the given count (rank)

Edit As for the 'bit position bucket accumulation' (bit_counter[]) I have a feeling that this might be a good case for valarrays + masking. That'd be a fair bit of coding+testing+profiling though. Let me know if you are really interested.

You could, these days, come very close to valarray behaviour using tied tuples (TR1, boost or C++11); I have a feeling it would come out being simpler to read and slower to compile.

Apparently this can be done quickly with "vertical counters". From the now-defunct page on Bit tricks (archive) by @steike:

Consider a normal array of integers, where we read the bits horizontally:

       msb<-->lsb
  x[0]  00000010  = 2
  x[1]  00000001  = 1
  x[2]  00000101  = 5

A vertical counter stores the numbers, as the name implies, vertically; that is, a k-bit counter is stored across k words, with a single bit in each word.

  x[0]  00000110   lsb ↑
  x[1]  00000001       |
  x[2]  00000100       |
  x[3]  00000000       |
  x[4]  00000000   msb ↓
             512

With the numbers stored like this, we can use bitwise operations to increment any subset of them all at once.

We create a bitmap with a 1 bit in the positions corresponding to the counters we want to increment, and loop through the array from LSB up, updating the bits as we go. The "carries" from one addition becomes the input for the next element of the array.

  input  sum

--------------------------------------------------------------------------------
   A B   C S
   0 0   0 0
   0 1   0 1      sum    = a ^ b
   1 0   0 1      carry  = a & b
   1 1   1 1

  carry = input;
  long *p = buffer;
  while (carry) {
    a = *p; b = carry;
    *p++ = a ^ b;
    carry = a & b;
  }

For 64-bit words the loop will run 6-7 times on average -- the number of iterations is determined by the longest chain of carries.

There's no way to answer this in general; it all depends on the compiler and the underlying architecture. The only real way to know is to try different solutions, and measure. (On some machines, for example, shifts can be very expensive. On others, no.) For starters, I'd use something like:

uint64_t mask = 1;
int index = 0;
while ( mask != 0 ) {
    if ( (bits & mask) != 0 ) {
        ++ bit_counter[index];
    }
    ++ index;
    mask <<= 1;
}

Unrolling the loop completely will likely improve performance. Depending on the architecture, replacing the if with:

bit_counter[index] += ((bits & mask) != 0);

might be better. Or worse... it's impossible to know in advance. It's also possible that on some machines, systematically shifting into the low order bit and masking, as you are doing, would be best.

Some optimizations will also depend on what typical data looks like. If most of the words only have one or two bits set, you might gain by testing a byte at at time, or four bits at a time, and skipping those that are all zeros completely.