c++ - 在没有循环的情况下从 C++ 中的 int 中提取 n 个最重要的非零位

Question

我想从 C++ 中的整数中提取 n 个最高有效位并将这 n 位转换为整数。

例如

int a=1200;
// its binary representation within 32 bit word-size is
// 00000000000000000000010010110000

现在我想从该表示中提取 4 个最重要的数字，即 1111

00000000000000000000010010110000
                     ^^^^

并将它们再次转换为整数(十进制的 1001 = 9)。

没有循环的简单 C++ 函数怎么可能？

Answer 1

一些处理器有一条指令来计算整数的前导二进制零，而一些编译器有允许您使用该指令的内部函数。例如，使用 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;
}