大多数编译器都会将 %2 转换为位比较吗？真的更快吗？

Question

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

n % 2 == 0

但是，我的理解是

'%'

运算符实际上执行除法并返回其余数；因此，对于上述情况，直接检查最后一位会更快。就说吧

n = 5;

5 = 00000101

为了检查数字是奇数还是偶数，我们只需要检查最后一位。如果是

1

，则为奇数；否则，它是偶数。在编程中，会这样表达：

n & 1 == 0

根据我的理解，这会比

% 2

更快，因为不执行除法。只需要进行一点比较即可。

我有两个问题：

1）第二种方式真的比第一种方式更快（在所有情况下）吗？

2）如果 1 的答案是肯定的，编译器（所有语言）是否足够聪明，可以将

% 2

转换为简单的位比较？或者如果我们想要最好的性能，我们是否必须明确使用第二种方式？

Answer 1

是的，位测试比整数除法快得多，大约是 10 到 20 倍，甚至在 Intel 上对于 128 位 / 64 位 = 64 位 idiv 来说是 100 倍。特别是。因为 x86 至少有一个 test

 指令，可以根据按位 AND 的结果设置条件标志，因此您不必进行除法和 

then 比较；按位 ANDis 比较。

我决定实际

检查 Godbolt 上的编译器输出，并得到了一个惊喜： 来自有符号

return n % 2

值的

int n

 而不是仅仅测试它是否为非零 (

if (n % 2)

) 会产生比 

return n & 1

 更慢的代码。这是因为

(-1 % 2) == -1

，而

(-1 & 1) == 1

，所以编译器不能只使用按位AND。不过，编译器仍然避免整数除法，而是使用一些巧妙的移位 / 和 / 添加 / 子序列来获得 -1 / 0 / +1 余数，因为这仍然比整数除法便宜。 （gcc 和 clang 使用不同的序列。）

因此，如果您想基于 int

 返回 0/非零 

n % 2

 值，请返回 

n%2 != 0

。

对于 2 的补码（和符号/幅度）有符号 int，这与 n&1

 相同。我们大多数人只关心我们的代码如何针对 2 的补码机器进行优化，而 C++20 放弃了符号/数值或补码的可能性，使补码成为唯一的可能性。 （要检查相反的条件，

n%2 == 0

。不是

n%2 == 1

，这将强制它检查符号位以及有符号类型，如果它不能证明带符号的

int

必须是非负的。）

使用

unsigned

 类型也能获得同样的好处，因为它可以消除负数。无符号 

/

 和 

%

 的 2 次幂只是右移和按位 AND，与有符号不同，其中除法向 0 截断，但算术右移 (

>>

) 向 -无穷大舍入。这也让编译器始终将其优化为单个 AND 指令。 （在 godbolt 上，您可以翻转到其他架构，例如 ARM 和 PowerPC，并看到 

unsigned even

 (

%

) 函数和 

int even_bit

 (按位 

&

) 函数具有相同的 asm 代码。）

使用

bool

（必须是 0 或 1，而不仅仅是任何非零值）是另一种选择，

return n%2

 作为 

bool

 相当于 

return n%2 != 0

。但即使对于 

(bool) (n % 4)

 类型，编译器也必须做额外的工作才能返回 

n%2

（或除 

unsigned

 之外的任何测试）。其 

return n & 3

 版本将为 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 认为它与所有这些分支有关。

Answer 2

速度相当。

无论使用哪种实现语言，无论整数是正数、负数还是零，模版本通常都能保证正常工作。按位版本不是。

使用您认为最易读的内容。