代码之家 › 专栏 › 技术社区 › Bitcoin Cash - ADA enthusiast

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

division compiler-optimization compiler-construction performance c++

8

Bitcoin Cash - ADA enthusiast · 技术社区 · 11 年前

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

n % 2 == 0

然而,我的理解是 '%' 运算符实际执行除法并返回其余数;因此,对于上述情况,只检查最后一位会更快。让我们说 n = 5;

5 = 00000101

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

n & 1 == 0

据我了解,这将比 % 2 因为不执行分割。只需要一点点比较。

我有两个问题:

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

2) 如果1的答案是肯定的,那么编译器(所有语言)是否足够聪明,能够转换 % 2 变成一个简单的比特比较?或者,如果我们想要最好的性能,我们是否必须明确使用第二种方法?

2 回复 | 直到 11 年前

1

18

CÅur Gustavo Armenta 7 年前

是的,一点测试是很比整数除法更快, by about a factor of 10 to 20, or even 100 for 128bit / 64bit = 64bit idiv on Intel .特别是,因为x86至少具有 test 基于位AND的结果设置条件标志的指令,因此您不必对然后比较按位排列 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 ,因此编译器不能使用位AND。不过,编译器仍然避免整数除法,而是使用一些巧妙的shift/和/add/子序列,因为这仍然比整数除法便宜。(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 setcc 根据标志将寄存器设置为0或1的指令,因此仍然只有2条指令而不是1。clang/gcc使用此指令,请参阅 aligned4_bool 在godbolt asm输出中。)

任何优化级别高于 -O0 ,gcc和clang优化 if (n%2) 达到我们的预期。另一个巨大的惊喜是 国际商会13 不 . 我不明白 WTF icc thinks it's doing with all those branches .

2

-2

David 11 年前

速度相当。

无论整数是正的、负的还是零,模版本通常都能保证工作,而不管实现语言如何。按位版本不是。

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