3 ms·

This is an awesome way to do it in software: int BitCount(unsigned int u) { unsigned int uCount; uCount = u – ((u

This is an awesome way to do it in software: int BitCount(unsigned int u) { unsigned int uCount; uCount = u – ((u >> 1) & 033333333333) – ((u >> 2) & 011111111111); return ((uCount + (uCount >> 3)) & 030707070707) % 63; } O(1) solution This explains why it works. https://blogs.msdn.microsoft.com/jeuge/2005/06/08/bit-fiddling-3/ https://blogs.msdn.microsoft.com/jeuge/2005/06/08/bit-fiddli...

thrownaway2424 11y ago
If you're into that kind of thing you might be pleased to know that Haswell CPUs have "bit manipulation instructions" designed to accelerate the kinds of C expressions you find in Hacker's Delight.
reikonomusha 11y ago
Any solution with a bounded loop is O(1) too, as would be the case for a loop on the bits of a 32- or 64-bit uint. What makes this interesting is that it's loopless and compiles to only a few instructions.
dalke 11y ago
It's also a slow way. Years ago I did a comparison of the many different ways to compute popcount. My use case computes millions of popcounts, and popcount is the limiting factor. The HAKMEM 169 version you mentioned was 1/2 of the performance of a simple 8-bit lookup table. http://www.dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html http://www.dalkescientific.com/writings/diary/archive/2011/1... . (Note: this assumes the LUT is in cache, which is true for my code.) HAKMEM 169 was also 1/3 the performance of the "popcount_3" implementation from https://en.wikipedia.org/wiki/Hamming_weight https://en.wikipedia.org/wiki/Hamming_weight . (Note: that works on 64 bit integers, not 32 bit ints as yours does.) When I wrote that blog post, I did not have a processor which supported the POPCNT instruction. The fastest SSSE3 version, using the same source as the SSSE3 version referenced in this link, was 8x faster than HAKMEM 169. If you want to compute the popcount of dozens of words, then a bitslice method by Lauradoux is nearly as fast as one which uses intrinsics. http://www.dalkescientific.com/writings/diary/archive/2008/07/05/bitslice_and_popcount.html http://www.dalkescientific.com/writings/diary/archive/2008/0...
eloff 11y ago
That % 63 at the end is integer division, that's horribly slow. Literally any other sensible approach will beat it, including a naive LUT.
- versteegen 11y ago
  Optimising compilers are smart enough to get rid of unsigned divisions by constants. See [1] (part one of a series; also [2] is neat). To quote [2], "libdivide's scalar code is up to 16 times faster for powers of 2, 10 times faster for non-powers of 2, compared to naive hardware division." In this case GCC (even with -O0) replaces % 63 with a complicated sequence of one integer multiplication, three subtractions, an addition, and three shifts, which I couldn't be bothered decompiling. [1] http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html http://ridiculousfish.com/blog/posts/labor-of-division-episo... [2] http://libdivide.com/ http://libdivide.com/
  - eloff 11y ago
    You're right. I read somewhere that no compiler optimizes modulus by a constant. That's clearly very outdated. I tested with clang 3.2, gcc 4.5, and icc 13 (all on a 32bit platform) and they all quite happily replace the division with other instructions.

thrownaway2424 11y ago

If you're into that kind of thing you might be pleased to know that Haswell CPUs have "bit manipulation instructions" designed to accelerate the kinds of C expressions you find in Hacker's Delight.

reikonomusha 11y ago

Any solution with a bounded loop is O(1) too, as would be the case for a loop on the bits of a 32- or 64-bit uint. What makes this interesting is that it's loopless and compiles to only a few instructions.

dalke 11y ago

It's also a slow way. Years ago I did a comparison of the many different ways to compute popcount. My use case computes millions of popcounts, and popcount is the limiting factor. The HAKMEM 169 version you mentioned was 1/2 of the performance of a simple 8-bit lookup table. http://www.dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html http://www.dalkescientific.com/writings/diary/archive/2011/1... . (Note: this assumes the LUT is in cache, which is true for my code.) HAKMEM 169 was also 1/3 the performance of the "popcount_3" implementation from https://en.wikipedia.org/wiki/Hamming_weight https://en.wikipedia.org/wiki/Hamming_weight . (Note: that works on 64 bit integers, not 32 bit ints as yours does.) When I wrote that blog post, I did not have a processor which supported the POPCNT instruction. The fastest SSSE3 version, using the same source as the SSSE3 version referenced in this link, was 8x faster than HAKMEM 169. If you want to compute the popcount of dozens of words, then a bitslice method by Lauradoux is nearly as fast as one which uses intrinsics. http://www.dalkescientific.com/writings/diary/archive/2008/07/05/bitslice_and_popcount.html http://www.dalkescientific.com/writings/diary/archive/2008/0...

eloff 11y ago

That % 63 at the end is integer division, that's horribly slow. Literally any other sensible approach will beat it, including a naive LUT.

versteegen 11y ago
Optimising compilers are smart enough to get rid of unsigned divisions by constants. See [1] (part one of a series; also [2] is neat). To quote [2], "libdivide's scalar code is up to 16 times faster for powers of 2, 10 times faster for non-powers of 2, compared to naive hardware division." In this case GCC (even with -O0) replaces % 63 with a complicated sequence of one integer multiplication, three subtractions, an addition, and three shifts, which I couldn't be bothered decompiling. [1] http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html http://ridiculousfish.com/blog/posts/labor-of-division-episo... [2] http://libdivide.com/ http://libdivide.com/
- eloff 11y ago
  You're right. I read somewhere that no compiler optimizes modulus by a constant. That's clearly very outdated. I tested with clang 3.2, gcc 4.5, and icc 13 (all on a 32bit platform) and they all quite happily replace the division with other instructions.