How to efficiently extract the bit position as a value in C

user_450780 0
Viewed 109

I'm looking for an efficient (preferably macro) way to extract the position of a bit and save it as a value in C.

data = 0x4000

would produce:

pos = 14

There is only going to be one bit set in the 16-bit register I'm reading. Currently, I'm just comparing the data to bit shifted values to extract the position, but there's gotta be a better way I don't know about.

I spent some time searching through here for a similar question and couldn't find one.

bit-manipulation c-preprocessor c
2 Answers

Modern processors have single instructions to do this (count trailing zeros, find first set, count leading zeros, and find last set). In gcc and clang, __builtin_ctz(n) will return the number of trailing zeros in a number. On processors where single instruction ctz is supported, it compiles to one instruction. Make sure to use a sufficiently wide function (ie __builtin_ctz for int or narrower, __builtin_ctzl for long int or narrower, or __builtin_ctzll for long long int or narrower. For a 16 bit register, __builtin_ctz should be sufficient.

See gcc documentation and wikipedia for more information.

user_21719810

A platform agnostic solution is the most portable and valid one, but it's also pessimistic; a lot of modern processors have instructions and intrinsics for bit operations like this.

For example, x86-64 have the bsf instruction which will populate one operand with the location of the most significant set bit in the other operand:

bsf eax, 0x00004000
; eax now holds the value '14'

However, a 'pure' C solution would look something like:

int MSBPos = 0;
while(data && !(data & 1)) // 'data' check avoids infinite loop if data is 0
{
    MSBPos++;
    data >>= 1;
}

Note, this only works in OP's case where he's guaranteed that there is a single set bit in the entire value and all other bits are 0.

I wouldn't worry about it being a linear algorithm though; bit operations are incredibly fast.

user_17734340
Related