Getting the index of the leftmost active bit in an integer instantly

Question

How would I scan an integer (in binary) from left to right instead of right to left? I know that I can start from the left and try every bit, and then record the leftmost bit, but is there a faster way? Is there a built-in function that can instantly find the leftmost active bit (that is a 1) in an integer?

I know that for right to left, I can do something like

int myInt = 1234;
for(int i = 0; i < 32; i++) {
  int curr_bit = myInt & (1 << i);
  // do something with curr_bit
}

But, I want to start off at the leftmost available bit, and I want its number "x" so that 1 << x will point to that exact digit (Just as a side note, I am trying to implement repeated squaring, and I need this in my code).

Any help would be greatly appreciated!

Answer 1

iBug's answer is very interesting, and I had never thought of doing it this way. If you're doing huge calculations where you want to find the leftmost digit many many times, I would recomment __builtin_clz in c++11. If you perform the snippet

for(int i = 31 - __builtin_clz; i >= 0; i--) {
    int left_most_bit = myInt & (1 << i);
}

This will start from the left_most_bit and work it's way to the right. Hope this helps! Implementation of __builtin_clz

Answer 2

This is called Find first set and most modern architectures have an instruction to do that quickly. In C++20 it can be done with std::countl_zero in the <bit> header

int left_most_bit_pos = sizeof(myInt)*CHAR_BIT - std::countl_zero(myInt);
int left_most_bit = myInt & (1 << left_most_bit_pos)

Answer 3

Use this:

int left_most_bit = myInt & (1 << (sizeof myInt * CHAR_BIT - 1));

How does it work?

• sizeof myInt returns the size of the variable myInt in bytes
• CHAR_BIT is a (possibly) platform-dependent macro that tells you how many bits are there in a byte, which is typically 8
• Shift 1 left by that gets the leftmost bit.

Works great in O(1) time because both sizeof myInt and CHAR_BIT are compile-time constants, so the whole expression (1 << (sizeof myInt * CHAR_BIT - 1)) is a compile-time constant, too. The compiler can then apply maximum optimization to it.

Answer 4

If you're interested in the actual fastest answer (at least on a desktop), here it is: use the _bit_scan_reverse intrinsic supported by Intel Compiler and Clang (maybe Visual Studio and GCC as well).

#include "immintrin.h"
int main() { printf("%i", _bit_scan_reverse(9)); }

Result: 3 (because 1<<3 = 8 is the highest bit set in 9).

Documentation

If you're worried about portability (as you should be with all proprietary extensions like this one), just include a fallback function and use the preprocessor to select the implementation you need:

#ifdef __SSE__ // All SSE processors support bsf/bsr
#include "immintrin.h"
static inline int bit_scan_reverse(int n) { return _bit_scan_reverse(n); }
#else
// Fallback implementation here
#endif

Note that the _bit_scan_reverse returns an unspecified value for n=0. If this is a problem you can add a ternary to the code in bit_scan_reverse: return n == 0 ? 0 : _bit_scan_reverse(n);.

Answer 5

Java has a method in the Integer class called highestOneBit(int value) which returns an int value with at most a single one-bit, in the position of the most significant (left most) bit that is set in the specified int value. It is implemented like this:

int highestOneBit(int value)
{
    value |= (value >>  1);
    value |= (value >>  2);
    value |= (value >>  4);
    value |= (value >>  8);
    value |= (value >> 16);
    return value - (value >> 1);
}