如何有效地提取c中作为值的位位置

Question

我正在寻找一种有效的(最好是宏)方法来提取位的位置并将其保存为c中的值。

data = 0x4000

会产生:

pos = 14

在我正在读取的16位寄存器中只会设置一个位。目前，我只是将数据与位移位值进行比较以提取位置，但一定有更好的方法，我不知道。

我花了一些时间在这里寻找类似的问题，但没有找到。

Answer 1

现代处理器有单个指令来完成此操作(计数尾零，查找第一组，计数前导零，查找最后一组)。在gcc和clang中，__builtin_ctz(n)将返回一个数字后面的零的个数。在支持单指令ctz的处理器上，它编译为一条指令。确保使用足够宽的函数(即__builtin_ctz用于int或更窄，__builtin_ctzl用于long int或更窄，__builtin_ctzll用于long long int或更窄)。对于16位寄存器，__builtin_ctz应该足够了。

查看gcc文档和wikipedia获取更多信息。

Answer 2

平台无关的解决方案是最可移植和有效的解决方案，但它也很悲观;很多现代处理器都有这样的位操作指令和内在特性。

例如，x86-64有bsf指令，它将用另一个操作数中最高位的位置填充一个操作数:

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

然而，一个"纯"的C解决方案看起来像这样:

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

注意，这只适用于OP的情况，他保证在整个值中有一个集合位，所有其他位都是0。

我不担心它是一个线性算法;位运算非常快。