c++ 大多数编译器会把% 2转换成位比较吗?它真的更快吗?

yi0zb3m4  于 11个月前  发布在  其他
关注(0)|答案(2)|浏览(82)

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

n % 2 == 0

字符串
然而,我的理解是,'%'运算符实际上执行除法并返回其余数;因此,对于上面的情况,简单地检查最后一位会更快。

5 = 00000101


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

n & 1 == 0


在我的理解中,这将比% 2快,因为没有执行除法。只需要位比较。
我有两个问题:
1)第二种方法真的比第一种方法快吗(在所有情况下)?
2)如果1的答案是肯定的,那么编译器(在所有语言中)是否足够聪明,可以将% 2转换为简单的位比较?或者如果我们想要最好的性能,我们必须显式地使用第二种方式吗?

sgtfey8w

sgtfey8w1#

是的,位测试比整数除法快得多,by about a factor of 10 to 20, or even 100 for 128bit / 64bit = 64bit idiv on Intel。特别是因为x86至少有一个test指令,它根据位与的结果设置条件标志,所以你不必除法然后比较;位AND * 就是比较。
我决定实际检查Godbolt上的编译器输出,并得到了一个惊喜:
return n % 2从一个有符号的int n值,而不是只测试它的非零值(if (n % 2))产生的代码比return n & 1慢。这是因为(-1 % 2) == -1,而(-1 & 1) == 1,所以编译器不能只使用按位AND。编译器仍然避免整数除法,但是,使用一些巧妙的移位/和/加/减序列来得到-1/0/ +1余数,因为这仍然比整数除法便宜。(gcc和clang使用不同的序列。)

**因此,如果你想根据n % 2返回一个0/非零的int值,返回n%2 != 0。**对于2的补码(和sign/magnitude)signed int,这与n&1相同。我们大多数人只关心我们的代码如何优化2的补码机器,C++20放弃了sign/magnitude或1的补码的可能性,使二进制补码成为唯一的可能性。(为了检查相反的条件,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认为它对所有这些分支都有作用。

mwg9r5ms

mwg9r5ms2#

速度相当。
无论整数是正的、负的还是零的,模的版本通常都能保证工作,不管实现语言是什么。
使用你觉得最可读的东西。

相关问题