c++ - 大多数编译器是否将 % 2 转换为位比较？真的更快吗？

Question

在编程中，经常需要检查一个数是奇数还是偶数。为此，我们通常使用:

n % 2 == 0

但是，我的理解是'%' 运算符实际上执行除法并返回其余数；因此，对于上述情况，直接检查最后一位会更快。假设 n = 5;

5 = 00000101

为了检查数字是奇数还是偶数，我们只需要检查最后一位。如果是1，则为奇数；否则，它是偶数。在编程中，它会这样表达:

n & 1 == 0

据我所知，这会比 % 2 更快，因为没有执行除法。仅需进行位比较。

我有两个问题:

1) 第二种方式真的比第一种方式快吗(在所有情况下)？

2) 如果 1 的答案是肯定的，编译器(在所有语言中)是否足够聪明，可以将 %2 转换为简单的位比较？或者如果我们想要最好的性能，我们是否必须显式地使用第二种方式？

Answer 1

是的，位测试比整数除法快多，by about a factor of 10 to 20, or even 100 for 128bit / 64bit = 64bit idiv on Intel .特别是因为 x86 至少有一个 test 指令，它根据按位与的结果设置条件标志，所以你不必除法和然后比较；按位AND 是比较。

我决定实际上check the compiler output on Godbolt , 并得到了一个惊喜:

事实证明，使用 n % 2 作为有符号整数值(例如，return n % 2 来自返回 signed int 的函数>) 而不是仅仅测试它是否为非零 (if (n % 2)) 有时会产生比 return n & 1 更慢的代码。这是因为 (-1 % 2) == -1，而 (-1 & 1) == 1，所以编译器不能使用按位与。不过，编译器仍然避免整数除法，而是使用一些巧妙的 shift/and/add/sub sequence，因为这仍然比整数除法便宜。 (gcc 和 clang 使用不同的序列。)

因此，如果您想返回基于 n % 2 的真值，最好的办法是使用无符号类型。这让编译器始终将其优化为单个 AND 指令。 (在 Godbolt 上，您可以转到其他架构，如 ARM 和 PowerPC，并看到 unsigned even (%) 函数和 int even_bit (按位 &) 函数具有相同的 asm 代码。)

使用 bool(必须是 0 或 1，而不仅仅是任何非零值)是另一种选择，但编译器必须做额外的工作才能返回 (bool) (n % 4)(或 n%2 以外的任何测试)。它的按位与版本将是 0、1、2 或 3，因此编译器必须将任何非零值转换为 1。(x86 有一个有效的 setcc 指令设置一个注册为 0 或 1，具体取决于标志，因此它仍然只有 2 条指令而不是 1 条指令。clang/gcc 使用它，请参阅 godbolt asm 输出中的 aligned4_bool。)

对于任何高于 -O0 的优化级别，gcc 和 clang 都会将 if (n%2) 优化为我们所期望的。另一个巨大的惊喜是icc 13 不。我不明白WTF icc thinks it's doing with all those branches .