在没有循环的情况下从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;
}