找到整数的最后 N 位的最快方法是什么？

Question

哪种算法最快返回无符号整数的最后 n 位？

1.

return num & ((1 << bits) - 1)

2.

return num % (1 << bits)

3.

let shift = num.bitWidth - bits
return (num << shift) >> shift

（其中 bitWidth 是整数的宽度，以位为单位）

或者有其他更快的算法吗？

Answer 1

这在很大程度上取决于您使用的编译器、优化设置以及您使用的整数大小。

我在本节中的假设是答案是 "the compiler will be smart enough to optimize all of these in a way that's better than whatever you'd choose to write." 从某种意义上说，这是正确的。考虑以下三段代码：

#include <stdint.h>
#include <limits.h>

uint32_t lastBitsOf_v1(uint32_t number, uint32_t howManyBits) {
    return number & ((1 << howManyBits) - 1);
}

uint32_t lastBitsOf_v2(uint32_t number, uint32_t howManyBits) {
    return number % (1 << howManyBits);
}

uint32_t lastBitsOf_v3(uint32_t number, uint32_t howManyBits) {
    uint32_t shift = sizeof(number) * CHAR_BIT - howManyBits;
    return (number << shift) >> shift;
}

在启用了 -march=native 的情况下，在 godbolt compiler explorer 优化到 -Ofast，我们得到了为三个函数生成的代码：

lastBitsOf_v1(unsigned int, unsigned int):
        bzhi    eax, edi, esi
        ret

lastBitsOf_v2(unsigned int, unsigned int):
        bzhi    eax, edi, esi
        ret

lastBitsOf_v3(unsigned int, unsigned int):
        mov     eax, 32
        sub     eax, esi
        shlx    edi, edi, eax
        shrx    eax, edi, eax
        ret

请注意，编译器识别出您尝试使用此函数的前两个版本执行的操作，并完全重写了代码以使用 bzhi x86 指令。该指令将一个寄存器的低位复制到另一个寄存器中。换句话说，编译器能够生成一条汇编指令！另一方面，编译器无法识别上一个版本试图做什么，所以它实际上生成了编写的代码并实际进行了移位和减法。

但这还没有结束。想象一下，要提取的位数是预先知道的。例如，假设我们想要低 13 位。现在，看看这段代码会发生什么：

#include <stdint.h>
#include <limits.h>

uint32_t lastBitsOf_v1(uint32_t number) {
    return number & ((1 << 13) - 1);
}

uint32_t lastBitsOf_v2(uint32_t number) {
    return number % (1 << 13);
}

uint32_t lastBitsOf_v3(uint32_t number) {
    return (number << 19) >> 19;
}

这些实际上是相同的函数，只是比特数被硬编码了。现在 look at what gets generated:

lastBitsOf_v1(unsigned int):
        mov     eax, edi
        and     eax, 8191
        ret
lastBitsOf_v2(unsigned int):
        mov     eax, edi
        and     eax, 8191
        ret
lastBitsOf_v3(unsigned int):
        mov     eax, edi
        and     eax, 8191
        ret

所有三个版本都编译为完全相同的代码。编译器看到了我们在每种情况下所做的事情，并将其替换为基本上是第一个版本的更简单的代码。

看完这一切，你该怎么办？我的建议如下：

除非此代码是绝对的性能瓶颈 - 例如，您已经测量了代码的运行时间并且您绝对确定用于提取低位数字的代码实际上正在减慢您的速度down - 我根本不会太担心这个。尽可能选择最易读的代码。我个人认为选项 (1) 最干净，但这就是我。
如果您绝对必须从中获得每一点性能，而不是相信我的话，我建议您修改不同版本的代码并查看什么程序集在每种情况下都会生成运行一些性能实验。毕竟，如果这样的事情真的很重要，你会想亲眼看看的！

希望对您有所帮助！

找到整数的最后 N 位的最快方法是什么？

Which is the fastest way to find the last N bits of an integer?

optimization

integer

bit-manipulation

mathematical-optimization

unsigned