Find most significant bit (left-most) that is set in a bit array

c bit-manipulation 32-bit
Claudiu picture Claudiu · Apr 7, 2010 · Viewed 84.1k times · Source

I have a bit array implementation where the 0th index is the MSB of the first byte in an array, the 8th index is the MSB of the second byte, etc...

What's a fast way to find the first bit that is set in this bit array? All the related solutions I have looked up find the first least significant bit, but I need the first most significant one. So, given 0x00A1, I want 8 (since it's the 9th bit from the left).

Answer

Andras Vass picture Andras Vass · Apr 7, 2010

GCC has __builtin_clz that translates to BSR on x86/x64, CLZ on ARM, etc. and emulates the instruction if the hardware does not implement it.
Visual C++ 2005 and up has _BitScanReverse.

Related questions

How do you set, clear, and toggle a single bit?

How do you set, clear, and toggle a bit?

Read More
What is Bit Masking?

I am fairly new to C programming, and I encountered bit masking. Can someone explain to me the general concept and function of bit masking? Examples are much appreciated.

Read More
C/C++ check if one bit is set in, i.e. int variable

int temp = 0x5E; // in binary 0b1011110. Is there such a way to check if bit 3 in temp is 1 or 0 without bit shifting and masking. Just want to know if there is some built in function for this, or am …

Read More