在一个32位的整数中取消最高位（最左边的一位）[C]

Question

如何取消一个字的最高位（例如0x00556844-> 0x00156844）？gcc中有一个__builtin_clz，但它只计算零，这对我来说是不必要的。还有，我应该如何替换msvc或intel c编译器的__builtin_clz？

目前我的代码是：

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

更新：好的，如果你说这段代码相当快，那我要问你，我该如何为这段代码添加可移植性呢？这个版本是针对GCC的，但是MSVC和ICC呢？

- osgx

---

“一个字的最高位是指什么？” 是指第22位吗？这是我在你的示例中看到的。 - Marius Bancila

不，给定的整数中设置的是最高有效位。对于0x12345678，结果将为0x02345678；对于0x00000123 -> 0x00000023。 - osgx

你的实现非常高效，实际上比我的答案更好，因为编译器会优化减法。 - Gunther Piez

为了可移植性，您应该使用(sizeof(int)*CHAR_BIT)（limits.h中有CHAR_BIT）而不是(sizeof(int)*8)。 - David X

David X，谢谢，但是如此广泛的可移植性并不需要。可移植性只涉及最常见的x86和x86_64编译器之间。这段代码将被少数用户在桌面和小型集群上使用。 - osgx

Answer 1

只需将数字向下舍入到最近的2的幂次方，然后将其与原始值进行异或运算，例如使用《黑客秘籍》中的flp2()函数：

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
}

- Paul R

---

@osgx：这取决于您想在哪种CPU上运行它 - 并非所有CPU都具有计算前导零指令或等效指令。当然，还存在可移植性的问题... - Paul R

我的主要CPU是x86(Core2)，可能还有带有clz指令的x86_64(Core2)。可移植性只关注于最常见的x86和x86_64编译器之间。 - osgx

Answer 2

如果您真正关心性能，最近在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位指令进行替换，因为最初的问题就是这样提出的。

- user2875414

---

维基百科称，BMI扩展从Haswell开始可用https://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets。我可以在32位模式x86和64位x86_64模式下使用它吗？是否有bsrq / bzhiq的内置函数？（最近的Clang / gcc可移植性是可以的） - osgx

对于32位指令，您可以在汇编中将“q”后缀替换为“l”。或者在C版本中，无论何时看到uint64_t，请替换为uint32_t。至于带有bsr/bzhi的内置函数，GCC/Clang中有内部函数可用（包括“immintrin.h”），允许您本地使用BMI指令，尽管您的代码不会优雅地降级 - 它将在不支持BMI的硬件上作为非法指令捕获。不要太担心C代码的冗长：当您添加-mbmi -mbmi2并具有Haswell或更新的CPU时，它实际上只会编译为bsr/bzhi。 - user2875414

Answer 3

您可以做

unsigned resetLeadingBit(uint32_t x) {
    return x & ~(0x80000000U >> __builtin_clz(x))
}

针对MSVC，有_BitScanReverse函数，它等同于31-__builtin_clz()。

实际上，情况相反，BSR是自然的x86指令，而gcc内置函数是通过实现31-BSR来达到相同效果的。

- Gunther Piez