Search code examples
c++cbinarybit-manipulationbit

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

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?

Solution

  • If you want the fastest way, you will need to use non-portable methods.

    Windows/MSVC:

    GCC:

    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.