logo标签列表

就性能而言，位运算符与普通模数运算符相比速度有多快？

c++bit-manipulationbitwise-operators
47

在普通流程或条件语句（如 for、if 等）中使用位运算是否会提高整体性能，并且在可能的情况下是否更好地使用它们？例如：

if(i++ & 1) {

}

对比。

if(i % 2) {

}
11
这是一个每个人都知道的技巧，包括编译器。在其他情况下，使用位运算可以有所帮助，具体取决于可替代选项是什么。 - harold
10
为什么第一个条件包括 i 的后缀递增而第二个条件则不包括？如果两段代码的功能不一样，那么对它们进行性能比较是没有意义的。 - AnT stands with Russia
涉及至少一个编译时常量的整数除法/取模将被编译器优化为一系列乘法和位移操作。 - Simple
2
个人而言，我更喜欢使用 (i & 0xFF) 而不是 (i % 0x100)。如果我用十进制说“你出生年份的后两位是什么”，你不会想，“哦，电话操作员想知道我的出生年份模100的余数……”你只会说出数字然后忘掉它。为什么人们认为取模更容易阅读呢？每次我看到它时，我都要检查变量是否带符号。这并不更容易阅读。使用 (&) 根本不是过早优化。 - Samuel Danielson
8个回答
64

除非你使用的是古老的编译器，否则它已经可以独立处理这个级别的转换。也就是说，现代编译器可以并将使用按位 AND 指令来实现 i % 2，前提是在目标 CPU 上有意义（公平地说，通常是有意义的）。

换句话说，至少对于一个具有合理的优化器的相当现代的编译器而言，不要期望在这些代码之间看到任何性能差异。在这种情况下，“合理”还有一个相当广泛的定义--即使是几十年前的许多编译器也可以毫不费力地处理这种微小的优化。

13
如果所有的值都是带符号整数类型，表达式a=b & 1;在我所知道的所有符合标准的实现中都会比a=b % 2;计算得更快，因为后者等价于a= b < 0 ? -(b & 1) : b & 1;。如果结果仅用于测试是否为零，则优化器可能能够识别b<0和b>=0两种情况是等价的，但我特别不期望这种优化。 - supercat
1
@supercat 这里有一种避免分支的方法，只需将符号位添加到掩码中：a = b & 0b1000....0001 - potato
1
@potato：在补码机器上，那样做不会产生正确的结果。有无分支的方法可以实现结果，事实上编译器已经生成了它们，但是它们比 b＆1 的代码更复杂。 - supercat
43
TL;DR: 优先考虑语义，其次再优化热点部分。 在 CPU 级别上，整数模运算和除法是最慢的操作之一。但你不是在 CPU 级别编程，而是在写 C++ 代码，你的编译器会将其转换成中间表示形式，最终根据编译的 CPU 模型将其转换为汇编代码。
在此过程中，编译器将应用Peephole 优化，其中包括强度降低优化，例如（引自维基百科）：
Original Calculation  Replacement Calculation
y = x / 8             y = x >> 3
y = x * 64            y = x << 6
y = x * 2             y = x << 1
y = x * 15            y = (x << 4) - x
最后一个例子或许是最有趣的。虽然通过2的幂次方进行乘法或除法可以（手动）转换为位移操作，但编译器通常会教给你更聪明的转换方式，你可能自己想不到，并且这种转换也不容易被识别（至少我个人不能立即意识到 (x << 4) - x 等价于 x * 15）。
4
最后一个例子的解释：x * 15 == x * (16 - 1) == (x * 16) - (x * 1) == (x << 4) - x。 - Yay295
16

显然，这取决于CPU，但可以预期的是，按位操作完成所需的CPU周期永远不会更多，通常会更少。一般来说，整数除法和求余（/ 和 %）非常慢，就CPU指令而言。

最佳实践是编写可理解、可维护和表达其逻辑的代码。这种微小优化很少能够产生明显的影响，因此只有在分析表明存在关键瓶颈并且已经证明此优化能够产生显著影响时才应使用它。而且，如果在某些特定平台上确实产生了显著影响，则编译器优化器可能已经在可以看到等效性时替换为按位操作（这通常要求您通过一个常量进行除法或求余）。

无论值得与否，在特定于x86指令，且当除数是运行时变量值（因此不能轻松地优化为例如位移或按位与）时，/ 和 % 操作所需的CPU周期可以在此处查找。这里无法列出太多x86兼容芯片，但以最近的CPU为任意例子-如果我们采用Agner的“Sunny Cove（Ice Lake）”（即第10代英特尔Core）数据，DIV和IDIV指令的延迟时间在12至19个周期之间，而按位与具有1个周期。在许多旧CPU上，DIV可能会慢40-60倍。

4
强调易读性加一分；通常优化是在最后阶段进行的，我们最好能够尽量避免让我们的代码看起来非常陌生。 - legends2k
5
默认情况下，应该使用最能表达您意图的操作，因为您应该优化可读性代码。（今天，最稀缺的资源大多是人类程序员。）
因此，如果您提取位，请使用 &，如果您测试可除性，即值是偶数还是奇数，请使用 %。
对于无符号值，这两个操作具有完全相同的效果，您的编译器应该足够聪明，可以用相应的位操作替换除法。如果您担心，可以检查它生成的汇编代码。
不幸的是，对于有符号值，整数除法略微不规则，因为它向零舍入，% 的结果取决于第一个操作数的符号。另一方面，位操作总是向下舍入。因此，编译器不能仅仅用简单的位操作替换除法。相反，它可能会调用整数除法例程，或者用额外的逻辑替换为位操作以处理不规则性。这可能取决于优化级别和哪个操作数是常量。
这种在零点的不规则性甚至可能是一件坏事，因为它是非线性的。例如，我最近遇到一个情况，我们在 ARM Cortex M0 上使用带符号值的除法，这必须非常快。在这种情况下，最好用右移替换它，既可以提高性能，又可以摆脱非线性。
1
我想知道现有代码在除法和取模的带符号行为的哪些方面上依赖了多少？ 我所知道的唯一使用负结果的情况是当“％”产生负数时，代码想要从“/”的结果中减去一个。 在多年的编程中，我认为我只遇到过一次截断向零对称性实际上有用的情况，而许多情况下周期性行为会更好。 特别具有讽刺意味的是，ANSI开始强制执行截断向零的时间大约是... - supercat
在大多数常见情况下，它可能已经停止成为更快的行为方式（因为新型处理器可以快速执行长乘法，并且通过常量进行向下取整除法可以使用长乘法更有效地评估而不是截断除法）。 - supercat
很不幸，尽管这是唯一正确的答案，它却出现在页面的最底部。遗憾的是，我的单个+1无法解决这个问题。“始终相信编译器会做最优化的事情”并不完全错误，但盲目地遵循它可能会非常误导人。 - Cody Gray
3

在“性能”方面，C运算符无法有意义地进行比较。从语言层面上来说，并没有什么“更快”或“更慢”的运算符。只有生成的机器代码可以被分析性能。在您的特定示例中，生成的机器代码通常完全相同（如果我们忽略第一个条件出于某种原因包含了后缀递增），这意味着性能上不会有任何差异。

1

总是有人谈论编译器的聪明程度，认为人们不应该考虑代码的性能，不敢质疑编译器的智慧，等等...结果就是人们相信每次使用% [某个二次幂]时，编译器会神奇地将他们的代码转换为& ([某个二次幂] - 1)。这简直是不真实的。如果一个共享库有这个函数：

int modulus (int a, int b) {
    return a % b;
}

当一个程序启动modulus(135, 16)时，在编译后的代码中将没有任何位运算的痕迹。原因是什么呢？编译器很聪明，但它在编译库时并没有水晶球。它看到了一个通用的模数计算，对于只涉及二的幂次方的事实一无所知，因此保持不变。
但是，你可以知道一个函数是否只传递二的幂次方。如果是这种情况，优化代码的唯一方法就是重写函数。
unsigned int modulus_2 (unsigned int a, unsigned int b) {
    return a & (b - 1);
}

编译器无法为您完成此操作。

1

这是编译器（GCC 4.6）为两个选项生成的经过优化的-O3代码：

int i = 34567;
int opt1 = i++ & 1;
int opt2 = i % 2;

生成的 opt1 代码：

l     %r1,520(%r11)
nilf  %r1,1
st    %r1,516(%r11)
asi   520(%r11),1

opt2的生成代码：

l     %r1,520(%r11)
nilf  %r1,2147483649
ltr   %r1,%r1
jhe  .L14
ahi   %r1,-1
oilf  %r1,4294967294
ahi   %r1,1
.L14: st %r1,512(%r11)

所以这4个额外的指令对于生产环境来说毫无意义。这将是一种过早的优化，只会引入复杂性。
这是哪种架构？你编译时启用了优化吗？ - phuclv
这是使用GCC 4.6编译器在IBM z/OS上生成的。-O3优化级别。 - user9164692
2
我不知道那些指令是什么意思。它们不像x86或PowerPC那样常见，而且助记符甚至都无法阅读。此外，计算指令数量并不是一个好的度量标准，因为一段具有更多指令的代码片段可能比较短的代码片段运行得更快。重要的是指令的复杂程度，例如div的吞吐量和延迟与移位操作相比如何。这不是一个好的答案，缺乏解释，并且没有向读者提供任何信息。 - phuclv
-4

位运算速度更快。 这就是为什么编译器会为您使用位运算。 实际上，我认为将其实现为以下方式会更快：

~i & 1

同样地，如果你查看编译器生成的汇编代码，你可能会看到像 x ^= x 而不是 x=0 这样的东西。但是（我希望）你不会在你的 C++ 代码中使用这个。
总之，为了自己和那些需要维护你的代码的人着想，请让你的代码易读，并让编译器完成这些微小的优化。它会做得更好。
2
"!"比"&"的优先级更高，布尔值是等于零或一的数字，因此(! i & 1)与!i完全相同。" - Potatoswatter
(!i)将翻转所有位。位运算符&1将检查最低有效位是否打开。因此，如果i是偶数，则其最低有效位将为0，(!i)的最低有效位将为1，因此执行位运算(&1)将为真。 - yosim
你要想的是~，而不是!。 - Potatoswatter
2
@yosim：!i 是布尔类型，返回 0 或 1。它不是按位取反运算符。您可能在想 ~。 - rici
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接