如果您真正关心性能,最近在x86中使用BMI指令是清除msb的最佳方式。
x86汇编中:
clear_msb:
bsrq %rdi, %rax
bzhiq %rax, %rdi, %rax
retq
现在需要将其改写为C语言,并让编译器发出这些指令,同时对不支持BMI指令的非x86体系结构或旧x86处理器进行优雅降级。
与汇编代码相比,C版本真的很丑陋和冗长。但至少它满足了可移植性的要求。如果你有必要的硬件和编译器指令(-mbmi,-mbmi2)匹配,编译后你就可以回到美丽的汇编代码。
如所写,bsr()依赖于GCC/Clang内置函数。如果针对其他编译器,则可以用等效的可移植C代码和/或不同的特定于编译器的内置函数进行替换。
#include <inttypes.h>
#include <stdio.h>
uint64_t bsr(const uint64_t n)
{
return 63 - (uint64_t)__builtin_clzll(n);
}
uint64_t bzhi(const uint64_t n,
const uint64_t index)
{
const uint64_t leading = (uint64_t)1 << index;
const uint64_t keep_bits = leading - 1;
return n & keep_bits;
}
uint64_t clear_msb(const uint64_t n)
{
return bzhi(n, bsr(n));
}
int main(void)
{
uint64_t i;
for (i = 0; i < (uint64_t)1 << 16; ++i) {
printf("%" PRIu64 "\n", clear_msb(i));
}
return 0;
}
无论是汇编版本还是C版本,都很适合使用32位指令进行替换,因为最初的问题就是这样提出的。
(sizeof(int)*CHAR_BIT)
(limits.h
中有CHAR_BIT
)而不是(sizeof(int)*8)
。 - David X