3 ms·
This is great. However, he omitted one I encountered a need for pretty recently and have so far not found a good solution: How do you count the number of bits
by winstonprivacy 4y ago
This is great. However, he omitted one I encountered a need for pretty recently and have so far not found a good solution:
How do you count the number of bits which have been set in a bitfield of type uint32_t?
I couldn't find any x64_64 intrinsics for this, which would probably be incredibly efficient.
- bluesnowmonkey 4y agopopcount?
- philiplu 4y agoLike bluesnowmonkey says, the concept you're looking for is called popcount, for population count. It's also called the Hamming weight. Wikipedia has 5 different example implementations under that latter name. Many C/C++ compilers have it available as an intrinsic as well, like __builtin_popcount or __popcnt. It's also std::popcount in C++20.
- winstonprivacy 4y agoWow! Just 5 instructions. This is almost 4 times faster than my previous best solution: // 19 instructions, does not use intrinsics int countbits(unsigned x) { unsigned n; n = (x >> 1) & 0x77777777; x = x - n; n = (n >> 1) & 0x77777777; x = x - n; n = (n >> 1) & 0x77777777; x = x - n; x = (x + (x >> 4)) & 0x0F0F0F0F; x = x\*0x01010101; return x >> 24; } Amazing tip, thanks.