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

user_14552430 0
Viewed 583

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;
        }
bitwise-operators bit-manipulation algorithm c++
3 Answers

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.

user_20793030

If the question is about finding the index of a single bit in a value, say uint32_t x = b000010000;, one quick method is to

auto index = builtin_popcount(x - 1);

// example: b000010000 - 1
//          b000001111
// popcount(b000001111) == 4

In arm64 architecture the best method would be to use the count_leading_zero(x) instruction/operation, due to lack of fast popcount for general purpose registers.

Reading the OP more carefully, it's not guaranteed that x only has one bit set -- the question seems to be rather finding the index of the least significant bit set. That can be isolated with

 x = temp & (0-temp);
user_17163390

I would suggest you to use __builtin_ctzl : Returns the number of trailing 0-bits in x, starting at the least significant bit position. (warning: If x is 0, the result is undefined).

examples : __builtin_ctzl(0x10) = 4, __builtin_ctzl(0x20) = 5

For your case you could just use it like :

unsigned index;
do {
    index = temp ? __builtin_ctzl(temp) : 0;
    ... //do your stuff
    temp -= pow(2, index);
} while (index);
user_175394200
Related