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

Question

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.

It's a 16-bit value? Write a `switch` statement that identifies which of the 16 bits is set. — tadman, Feb 17 '21 at 22:07
Either you go for a Switch Case, or you go for a loop with a mask `(data & (1< — Grégoire BOUX, Feb 17 '21 at 22:09
What are you actually trying to achieve? It seems like you're trying to put a square peg in a round hole here (xy problem) — Rogue, Feb 17 '21 at 22:10
Are you targeting a specific compiler? If so, there may be a built-in function you can use. — dbush, Feb 17 '21 at 22:10
@Devolus *There is only going to be one bit set in the 16-bit register* — kaylum, Feb 17 '21 at 22:14
https://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i — Hans Passant, Feb 17 '21 at 22:14
not trying to fit a square peg in a round hole here... I have a vendor giving me a device that has a 16-bit register that has 1 bit (and only 1) set at a time. that bit corresponds to a "database" of values in other registers in their device as the index. so if bit 14 is set, I need to go read that 14th entry's set of registers. — linsek, Feb 17 '21 at 22:18
@dbush gcc version 8.2.0 for an ARM Cortex-R5... I'll look into hacatu's comment as well. — linsek, Feb 17 '21 at 22:20
From what I can tell, ARM processors have at least count leading zeros so any of the similar bit scan builtins should compile to one or two instructions — hacatu, Feb 17 '21 at 22:29
For questions like this, I usually consult this: https://graphics.stanford.edu/~seander/bithacks.html — John Bayko, Feb 17 '21 at 23:28

score 3 · Accepted Answer · answered Feb 17 '21 at 22:12

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.

This is exactly why I was looking for. Thank you. – linsek Feb 17 '21 at 22:34 — linsek, Feb 17 '21 at 22:34

Govind Parmar · Answer 2 · 2021-02-17T22:31:52.083

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.

up-voted for a good answer. the __builtin_ctzl() was easy to use and accomplished the task in 3 instructions. 2 moves and the bsf you noted. as a point of comparison, I generated the assembly for your while loop too. It accomplishes the task in pure C as you stated in just +6 instructions and a couple jumps. In my case, I'll leverage the built-in, but for a more portable solution, the while loop is efficient as well. thanks! — linsek, Feb 17 '21 at 22:54

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

2 Answers2