取消设置单词中最重要的位(int32)[C]

Question

如何取消设置一个字的最重要的设置位(例如0x00556844 - > 0x00156844)？__builtin_clzgcc中有一个,但它只计算零,这对我来说是不必要的.另外,我应该如何为msvc或intel c编译器替换__builtin_clz？

目前我的代码是

 int msb = 1<< ((sizeof(int)*8)-__builtin_clz(input)-1);
 int result = input & ~msb;

更新:好的,如果你说这段代码相当快,我会问你,我应该如何为这段代码添加一个可移植性？这个版本适用于GCC,但是MSVC和ICC？

Answer 1

只需向下舍入到最接近的2的幂,然后用原始值进行异或,例如使用flp2()来自Hacker's Delight:

uint32_t flp2(uint32_t x) // round x down to nearest power of 2
{
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >>16); 
    return x - (x >> 1); 
}

uint32_t clr_msb(uint32_t x) // clear most significant set bit in x
{
    msb = flp2(x);  // get MS set bit in x
    return x ^ msb; // XOR MS set bit to clear it
}

Answer 2

如果您真的关心性能,那么最近清除msb的最佳方法是通过添加BMI指令来更改x86.

在x86汇编中:

clear_msb:
    bsrq    %rdi, %rax
    bzhiq   %rax, %rdi, %rax
    retq

现在要在C中重写并让编译器发出这些指令,同时优雅地降级非x86架构或不支持BMI指令的旧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位指令替换,因为提出了原始问题.