Search code examples
c++algorithmbit-manipulationbitwise-operators

Is there a fast way to get the index of bit which equal 1 in a binary value?


I want to get the index which equals to 1 in binary format, now I use codes like this:

inline static uint8_t the_index(uint32_t val){
  return uint8_t(log(val & ((~val) + 1))/log(2));
}

I want to know if there are other ways to achieve the same target? Is there any possible to use bit operation to solve this problem?

I do this to iterater a value and build some operations which depends on the position iterated, the pesudo codes like this:

 while (temp) {
            auto cur_index = the_index(temp);
            auto window = ((1 << i) - 1) << cur_index;
            if (((temp & window) ^ window) == 0) {
              //....do something
            }
            temp &= temp - 1;
        }

Solution

  • There is a standard function for this:

    auto cur_index = std::countr_zero(temp);
    

    On my system, this compiled down to:

    xor     eax, eax
    tzcnt   eax, edi
    

    Note that this function successfully counts the zero bits from right until first one bit whether the input has exactly one set bit or not.