您可以为此使用编译器内置.gcc和clang支持这一点:
内置功能:int __builtin_clz(unsigned int x)
返回从最高有效位位置开始的x
中前导0位的数目.如果x
为0
,则结果未定义.
int bit_index32(unsigned x) {
return 31 - __builtin_clz(x);
}
要获得更具可移植性的解决方案,您可以使用一个简单的循环:
int bit_index32(unsigned x) {
int n = 0;
while (x > 1) { n++; x >>= 1; }
return n;
}
速度更快,只需5次测试,而不是最多31次:
int bit_index32(unsigned x) {
int n = 0;
if (x > 0xFFFF) { n += 16; x >>= 16; }
if (x > 0xFF) { n += 8; x >>= 8; }
if (x > 0xF) { n += 4; x >>= 4; }
if (x > 0x3) { n += 2; x >>= 2; }
if (x > 0x1) { n += 1; x >>= 1; }
return n;
}
由于v
是2的幂,索引是v-1
中的位数,无需测试即可计算:
int bit_index32(unsigned v) {
v--;
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
另一个只对2的幂起作用的无分支的:
int bit_index32(unsigned v) {
return !!(v & 0xAAAAAAAA)
| !!(v & 0xCCCCCCCC) << 1
| !!(v & 0xF0F0F0F0) << 2
| !!(v & 0xFF00FF00) << 3
| !!(v & 0xFFFF0000) << 4;
}
肖恩·安德森的Bit Twiddling Hacks岁生日更有趣!