c++ - Efficient bitwise operations for counting bits or find the right|left most ones

Question

Given an unsigned int, I have to implement the following operations :

1. Count the number of bits set to 1
2. Find the index of the left-most 1 bit
3. 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?

Answer 1

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.