Efficient bitwise operations for counting bits or find the right|left most ones
binary, bit, bit-manipulation, c, c++
Solution
If you want the fastest way, you will need to use non-portable methods.
Windows/MSVC:
- _BitScanForward()
- _BitScanReverse()
- __popcnt()
GCC:
- __builtin_ffs()
- __builtin_ctz()
- __builtin_clz()
- __builtin_popcount()
These typically map directly to native hardware instructions. So it doesn't get much faster than these.
But since there's no C/C++ functionality for them, they're only accessible via compiler intrinsics.
Problem
Given an unsigned int, I have to implement the following operations : - Count the number of bits set to 1 - Find the index of the left-most 1 bit - Find the index of the righ-most 1 bit (the operation should not be architecture dependents). I've done this using bitwise shift, but I have to iterate through almost all the bits(es.32) . For example, counting 1's: ``` unsigned int number= ...; while(number != 0){ if ((number & 0x01) != 0) ++count; number >>=1; } ``` The others operation are similar. So my question is: is there any faster way to do that?