一些处理器有一条指令来计算整数的前导二进制零,而一些编译器具有允许您使用该指令的内在函数。例如,使用 GCC:
uint32_t significant_bits(uint32_t value, unsigned bits) {
unsigned leading_zeros = __builtin_clz(value);
unsigned highest_bit = 32 - leading_zeros;
unsigned lowest_bit = highest_bit - bits;
return value >> lowest_bit;
}
为简单起见,我省略了检查请求的位数是否可用。对于 Microsoft 的编译器,内在函数称为__lzcnt
.
如果您的编译器不提供该内在函数,并且您的处理器没有合适的指令,那么快速计算零的一种方法是使用二进制搜索:
unsigned leading_zeros(int32_t value) {
unsigned count = 0;
if ((value & 0xffff0000u) == 0) {
count += 16;
value <<= 16;
}
if ((value & 0xff000000u) == 0) {
count += 8;
value <<= 8;
}
if ((value & 0xf0000000u) == 0) {
count += 4;
value <<= 4;
}
if ((value & 0xc0000000u) == 0) {
count += 2;
value <<= 2;
}
if ((value & 0x80000000u) == 0) {
count += 1;
}
return count;
}