Calculating Hamming weight efficiently in matlab

Question

Given a MATLAB uint32 to be interpreted as a bit string, what is an efficient and concise way of counting how many nonzero bits are in the string? I have a working, naive approach which loops over the bits, but that's too slow for my needs. (A C++ implementation using std::bitset count() runs almost instantly). I've found a pretty nice page listing various bit counting techniques, but I'm hoping there is an easy MATLAB-esque way. http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive Update #1 Just implemented the Brian Kernighan algorithm as follows: ``` w = 0; while ( bits > 0 ) bits = bitand( bits, bits-1 ); w = w + 1; end ``` Performance is still crappy, over 10 seconds to compute just 4096^2 weight calculations. My C++ code using count() from std::bitset does this in subsecond time. Update #2 Here is a table of run times for the techniques I've tried so far. I will update it as I get additional ideas/suggestions. ``` Vectorized Scheiner algorithm => 2.243511 sec Ve…

Accepted Answer

I'd be interested to see how fast this solution is:

```
function r = count_bits(n)

shifts = [-1, -2, -4, -8, -16];
masks = [1431655765, 858993459, 252645135, 16711935, 65535];

r = n;
for i=1:5
   r = bitand(bitshift(r, shifts(i)), masks(i)) + ...
      bitand(r, masks(i));
end
```

Going back, I see that this is the 'parallel' solution given on the bithacks page.

Calculating Hamming weight efficiently in matlab

Solution

Problem