哪个是找到整数的最后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

这将在很大程度上取决于您拥有的编译器，优化设置是什么，以及要使用的整数的大小。

我在本节中的假设是，答案将是“编译器将足够聪明，可以以比您选择编写的任何方法都要好的方式来优化所有这些方法。”从某种意义上说，这是正确的。考虑以下三段代码：

#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;
}

[在godbolt compiler explorer处的优化使-Ofast处于启用状态，在-march=native处，我们获得了为三个功能生成的代码：

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

所有三个版本都编译为完全相同的代码。编译器看到了我们在每种情况下的工作，并用基本上是第一版的这段简单得多的代码替换了它。

看到所有这些之后，您应该怎么办？我的建议如下：

1. 除非此代码是绝对的性能瓶颈-例如，您已经测量了代码的运行时，并且绝对可以确定提取低位数字的代码实际上会使您减速-我不会完全不用为此担心。选择最易读的代码。我个人认为选项（1）最干净，但这就是我。

2. 如果您绝对必须从中获得最大的性能，而不是信守承诺，我建议您修改一下不同版本的代码，并查看每种情况下生成的程序集，并进行一些性能实验。毕竟，如果这样的事情真的很重要，那么您想自己看看吧！

希望这会有所帮助！