将整数除以2，哪种选项更好？

Question

以下哪种技术是将整数除以2的最佳选项，为什么？

技术1：

x = x >> 1;

技巧2：

x = x / 2;

这里的x是一个整数。

- Abhineet

---

如果你真的想再次将结果分配给 x，那么这两种方式都不太合适：应该是 x >>= 1 或者 x /= 2，具体取决于你希望表达的操作意义。这并不是因为它更快（现代编译器会将所有等效变体编译为相同、快速的汇编代码），而是因为它更清晰易懂。 - leftaroundabout

我不同意leftaroundabout的观点。但是我认为值得注意的是，许多编程语言中都有一种称为"算术移位"的操作，它保留符号位并因此按预期处理带符号值。其语法可能类似于x = x >>> 1。另请注意，根据平台和编译器的不同，手动优化除法和乘法使用移位操作可能是相当合理的。举个例子，微控制器没有直接的ALU支持乘法。 - JimmyB

我更喜欢使用x /= 2，因为x >>= 1看起来太像单子绑定（monadic bind）了 ;) - fredoverflow

@leftaroundabout - 我认为写x = x / 2比写x /= 2更易读。这可能是主观偏好 :) - JimmyB

@HannoBinder：当然是主观的，尤其是很多习惯方面。在一个所有算术运算符都有“⬜=”组合的语言中，只要可能，应该使用这些组合。这可以消除噪音并强调“x”被修改的事实，而一般的“=”运算符则暗示它采用了完全独立于旧值的新值。避免使用组合运算符（这样数学符号的初学者也能读懂）也有其优点，但这样你将需要放弃极其实用的“++”、“--”、“+=”等运算符。 - leftaroundabout

Answer 1

选用最符合你所需的操作。

• 如果你将数字视为位序列，请使用位移操作。
• 如果你将其视为数值，请使用除法操作。

请注意它们并不完全等价。对于负整数，它们可能会产生不同的结果。例如：

-5 / 2  = -2
-5 >> 1 = -3

(ideone)

注：此链接为一个网站地址，可能与所讨论的上下文相关。

- Mark Byers

---

原问题中提到的"best"这个词很模糊。它可以指速度、易读性、设置考试陷阱等方面的"最佳"。由于没有具体说明"best"的含义，因此这似乎是最正确的答案。 - Ray

在C++03中，对于负数的情况，两者都是实现定义，并且可能会给出相同的结果。在C++11中，除法对负数有明确定义，但移位仍然是实现定义的。 - James Kanze

虽然在早期的C标准中定义了/运算符的实现方式（对于负数是向上还是向下取整），但它必须始终与%（模运算符/余数运算符）保持一致。 - ctrl-alt-delor

“Implementation defined”意味着编译器的实现者可以在几种实现选项中进行选择，通常有实质性的限制。这里，一个限制是％和/运算符必须对于正数和负数操作数保持一致，以便(a/b)*b+(a%b)==a无论a和b的符号如何都成立。通常，作者会做出最优性能的选择，以充分发挥CPU的性能。 - RBerteig

每个说“编译器最终会把它转换成移位操作”的人都是错的，对吗？除非编译器可以保证你处理的是非负整数（无论是常量还是无符号整数），否则它不能将其转换为移位操作。 - Kip

Answer 2

第一个看起来像除法吗？不是的。如果你想要除法，使用x / 2。编译器可以在可能的情况下优化它为位移操作（这被称为强度降低），如果你自己这样做会变成无用的微小优化。

- Cat Plus Plus

---

许多编译器不会将二的幂除法转换为位移运算。对于带符号整数来说，这将是一种错误的优化。你应该尝试查看编译器的汇编输出并自行确认。 - exDM69

我记得我用这个来加速CUDA上的并行约化（避免整数除法）。不过这已经是一年多以前的事了，我想知道现在的CUDA编译器有多聪明。 - Nils

许多编译器即使针对有符号整数也会这样做，并根据符号进行调整。一个很好的用于尝试这些内容的工具是：http://tinyurl.com/6uww253 - PlasmaHH

那与此有何关联呢？我说的是“如果可能”，而不是“总是”。如果优化不正确，那么手动操作也不能使其变得正确（另外如前所述，GCC足够聪明，可以找到适当替代有符号整数的方法）。 - Cat Plus Plus

根据维基百科页面显示，这似乎是有争议的，但我不会称其为强度降低。强度降低是在循环中将乘法等运算改为加法等运算，通过对循环内先前的值进行逐步相加来实现。这更像是一种窥视孔优化，编译器可以相当可靠地执行。 - SomeCallMeTim

@exDM69：只需要进行额外的移位和加法操作，就可以使用逻辑移位和算术移位实现x/2。https://godbolt.org/z/G9TTYG6Ke 因此，对于有符号数来说，x>>1更便宜，但是如果编译器不太合理，x/2将不会使用idiv。这个答案可以更好地解释如果不能使用单个shr或sar时会发生什么。 - Peter Cordes

Answer 3

进一步补充：有很多理由支持使用x = x / 2;，以下是其中的一些：

• 它更清晰地表达了你的意图（假设你不处理位操作寄存器位或其他类似情况）

• 编译器会将其优化为移位操作

• 即使编译器没有将其优化为移位操作且选择了一个比移位更慢的操作，它对程序性能的影响也微乎其微，几乎可以忽略不计（如果确实会明显影响性能，那么你就有一个实际理由使用移位操作）

• 如果除法运算是一个更大表达式的一部分，如果你使用除法运算符，则更可能正确设置优先级：

x = x / 2 + 5;
x = x >> 1 + 5;  // not the same as above

• 有符号算术可能会比上面提到的优先级问题更加复杂。

• 再次强调 - 编译器实际上已经为您执行此操作。实际上，它将除以常数的运算转换为一系列移位、加法和乘法，适用于各种数字，而不仅仅是2的幂。请参见此问题，其中包含更多相关信息的链接。

简而言之，使用移位运算代替乘法或除法并不能带来任何好处，反而可能增加引入错误的可能性。编译器可以很聪明地将这种操作优化为移位运算，这样已经有很长时间了。

- Michael Burr

---

值得一提的是，虽然有优先级规则，但使用括号并没有任何问题。在改进一些生产代码时，我实际上看到了一个形式为 a/b/c*d（其中a..d代表数字变量）而不是更可读的 (a*d)/(b*c)的表达式。 - user554546

性能和优化取决于编译器和目标平台。例如，我为微控制器做一些工作，除非您购买商业编译器，否则禁用高于-O0的任何内容，因此编译器绝对不会将除法转换为位移。此外，在该目标平台上，位移需要一个周期，而除法需要18个周期，由于微控制器的时钟速度相当低，这可能确实会对性能产生影响（但这取决于您的代码-您应该在分析表明存在问题之前使用/！） - user21037

如果a*d或b*c可能会产生溢出，那么不太易读的形式就不等同于原来的形式，并且具有明显的优势。顺便说一下，我同意括号是你最好的朋友。 - Mark Ransom

如果x永远不会是奇数负数或者你不关心off-by-one错误，那么代码x=x/2;比x>>=1更加"清晰"。否则，x=x/2;和x>>=1;有不同的含义。如果需要的是由x>>=1计算出的值，我认为这比使用除以二的任何其他公式如x = (x & ~1)/2或x = (x < 0) ? (x-1)/2 : x/2更清晰。同样，如果需要由x/=2计算出的值，则比((x + ((unsigned)x>>31)>>1)更清晰。 - supercat

@Dan：为非优化编译器编写代码是一个非常特殊的情况。你将不得不以更多的方式编写难以阅读的代码来尝试优化汇编语言。此外，即使在-O0级别下，gcc和icc也使用移位+调整符号位的方法实现带符号除以2。（godbolt链接）。然而，clang -O0确实使用div。现代x86 CPU的除法与移位操作具有类似的延迟和吞吐量比率，因此编译器避免使用除法是一个大问题。这可能不像分支预测错误那么糟糕，但可能会像L1缓存未命中那样影响L2。 - Peter Cordes

Answer 4

哪种方法是将整数除以2的最佳选项，为什么？

这要取决于你所说的“最佳”是什么意思。

如果你想让同事讨厌你，或者让你的代码难以阅读，那我一定会选择第一个选项。

如果你想将一个数字除以2，就选择第二个选项。这两种方法并不相同，如果数字为负数或在更大的表达式中，它们的行为不同 - 位移比加减法优先级低，而除法优先级高。你应该编写代码来表达其意图。如果性能是你关心的问题，不用担心，优化器可以做好这些微小的优化。

- Luchian Grigore

Answer 5

只需使用除法运算符 (/)，假定这更加清晰易懂。编译器会根据情况进行优化。

- justin

---

编译器 应该 相应地进行优化。 - Noctis Skytower

如果编译器没有进行相应的优化，你应该使用更好的编译器。 - David Stone

哪些处理器可以使编译器对除以任何常数（除1外）的可能为负的有符号整数进行优化，使其与移位一样高效？ - supercat

@supercat：这是一个很好的观点。当然，您可以将该值存储在无符号整数中（我认为与有符号/无符号不匹配警告结合使用时，它们的声誉要差得多），大多数编译器也有一种方法，在优化时告诉它们假定某些东西是真实的。我更喜欢将其包装在兼容性宏中，比如ASSUME(x >= 0); x /= 2;而不是 x >>= 1;，但这仍然是一个重要的观点需要提出来。 - David Stone

@DavidStone，除非你能为任何可能阅读这个问题的人列出每个微控制器所使用的“更好的编译器”，否则我倾向于不同意你的评论。有很多编译器可能因为各种原因而需要使用，并且告诉他们“你不应该这样做”是相当无用的信息。我无法想象任何主流编译器没有执行优化，但那些不执行优化的编译器仍然存在。 - Kröw

Answer 6

我同意其他答案的观点，您应该倾向于使用x / 2，因为它的意图更清晰，编译器应该会为您进行优化。

然而，喜欢x / 2而不是x >> 1的另一个原因是，如果x是有符号的int并且是负数，则>>的行为取决于实现。

来自ISO C99标准的第6.5.7节，第5个小点：

 

E1 >> E2的结果是E1向右移动E2位。 如果E1具有无符号类型或者E1具有带符号类型和非负值，   则结果的值是E1 /2^E2的商的整数部分。 如果E1具有带符号类型和负值，则结果的值是   实现定义的。

- jamesdlin

---

值得注意的是，许多实现在负数上对 x>>scalepower 定义的行为恰好适用于将值除以二的幂次方，例如用于屏幕渲染等目的，而使用 x/scalefactor 将是错误的，除非对负值进行修正。 - supercat

实际上，几乎所有的实现都将有符号整数类型的 >> 定义为算术右移，即对于二进制补码，移位时会复制符号位。例如，GNU C 保证了这一点：https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html。当然，Deathstation 9000 可能会执行一些无用的操作，但这对大多数代码来说并不是一个重要的可移植性问题。ISO C++ 甚至正在朝着将其作为算术右移进行标准化的方向发展。 - Peter Cordes

Answer 7

x / 2更清晰，而x >> 1并没有明显加速（根据微基准测试，Java JVM大约快了30%）。正如其他人所指出的那样，对于负数，四舍五入略有不同，因此在处理负数时需要考虑这一点。一些编译器可能会自动将x / 2转换为x >> 1，如果它们知道数字不能是负数(即使我无法验证这一点)。

即使是 x / 2 也可能不使用（慢速的）除法 CPU 指令，因为 可能存在某些快捷方式，但它仍然比 x >> 1 慢。

（这是一道 C / C++ 问题，其他编程语言有更多的运算符。对于 Java，也有无符号右移运算符 x >>> 1，它又与众不同。它允许正确计算两个值的平均值，因此即使对于非常大的 a 和 b 值，(a + b) >>> 1 将返回平均值。例如，如果数组索引可能非常大，则需要这样做才能进行二分查找。在许多版本的二分查找中存在一个错误，因为它们使用 (a + b) / 2 来计算平均值。这并不能正常工作。正确的解决方案是使用 (a + b) >>> 1。）

- Thomas Mueller

---

编译器无法将 x/2 转换为 x>>1，特别是当 x 可能为负数时。如果想要的是 x>>1 计算出的值，那么几乎肯定比任何涉及计算相同值的 x/2 表达式更快。 - supercat

你是对的。如果编译器知道值不为负，它可能只会将 x/2 转换为 x>>1。我会尝试更新我的答案。 - Thomas Mueller

编译器仍然会避免使用div指令，而是将x/2转换为(x + (x<0?1:0)) >> 1（其中>>是算术右移，它将符号位移入）。这需要4条指令：复制值，shr（以在寄存器中获取符号位），加法，sar。http://goo.gl/4F8Ms4 - Peter Cordes

该问题被标记为C和C++。 - Josh Sanford

Answer 8

Knuth说：

 

过早优化是万恶之源。

因此，我建议使用x /= 2;

这样代码易于理解，而且我认为在该形式下对此操作进行优化对处理器来说不会有太大的差异。

- Ivan Californias

---

如果想要整数遵守公理（适用于自然数和实数）(n+d)/d = (n/d)+1，在将一个数字缩小2的幂次方时，您认为最好的缩放方法是什么？如果在缩放图形时违反该公理，会导致结果中出现可见的“接缝”。如果希望得到关于零几乎对称的均匀物体，“(n+8)>>4”效果很好。您能否提供任何与此类似或效率更高的方法而不使用有符号右移？ - supercat

Answer 9

看一下编译器输出，帮助你做出决策。我在x86-64上运行了这个测试，使用的是gcc (GCC) 4.2.1 20070719 [FreeBSD]。

还可以在godbolt上查看编译器输出。

你可以看到，编译器在两种情况下都使用了一个“sarl”（算术右移）指令，因此它确实认识这两个表达式之间的相似性。如果你使用除法，编译器还需要调整负数的值。为了做到这一点，它会将符号位向下移动到最低位，并将其加到结果中。这样就修正了移位负数的错误，与除法的处理方式进行比较。

由于除法需要2次移位，而显式移位只需要一次，因此我们现在可以解释其他答案中测量到的一些性能差异。

带有汇编输出的C代码：

对于除法，您的输入将是：

int div2signed(int a) {
  return a / 2;
}

并且这将编译为

    movl    %edi, %eax
    shrl    $31, %eax            # (unsigned)x >> 31
    addl    %edi, %eax           # tmp = x + (x<0)
    sarl    %eax                 # (x + 0 or 1) >> 1  arithmetic right shift
    ret

同样地，对于 "shift" 操作。

int shr2signed(int a) {
  return a >> 1;
}

输出结果为：

    sarl    %edi
    movl    %edi, %eax
    ret

其他指令集同样可以高效地执行此操作，甚至可能更高效。例如，AArch64架构的GCC使用：

        add     w0, w0, w0, lsr 31      // x += (unsigned)x>>31
        asr     w0, w0, 1               // x >>= 1
        ret

- Michael Donohue

---

根据所做的事情，它可能会修复一个 off-by-one 错误，或者它可能会导致一个 off-by-one 错误（与实际需要的相比），这将需要使用进一步的代码来修复它。如果想要一个向下取整的结果，右移比我知道的任何其他方法都更快更容易。 - supercat

如果你需要地板，你不太可能将你想要的描述为“除以2”。 - Michael Donohue

自然数和实数的除法遵循公理(n+d)/d = (n/d)+1。实数的除法也遵循(-n)/d = -(n/d)这个公理，但这个公理在自然数中是没有意义的。不可能有一个整数上封闭且同时遵循这两个公理的除法运算符。在我看来，说第一个公理应该适用于所有数字，而第二个只适用于实数，似乎比说第一个公理应该适用于整数或实数但不适用于自然数更自然。此外，我很好奇第二个公理在哪些情况下实际上是有用的。 - supercat

一个满足第一公理的整数除法方法将把数线分割成大小为 d 的区域。这种分区对许多目的都很有用。即使你想要断点不在 0 和 -1 之间，添加一个偏移量就可以移动它。满足第二公理的整数除法将把数线分成大部分大小为 d 的区域，但其中一个区域的大小为 2*d-1。并非完全“平等”的划分。你能提供一些奇怪的划分实际上有用的建议吗？ - supercat

你的shr2signed编译器输出有误。在x86上，gcc选择使用算术移位（sar）来实现有符号整数的>>操作。这篇邮件列表帖子（https://gcc.gnu.org/ml/gcc/2000-04/msg00152.html）证实了gcc历史上使用算术移位来处理有符号整数，因此FreeBSD gcc 4.2.1使用无符号移位的可能性非常小。我更新了你的帖子以修复这个问题，并且修改了早期段落中说两者都使用shr的错误描述，实际上它们都使用SAR。SHR是用于提取“/”情况下的符号位的。同时，我还包含了一个godbolt链接。 - Peter Cordes

由于这些操作并不相同，因此比较它们的性能没有多大意义。 - skyking

Answer 10

额外说明：

x *= 0.5 在一些基于虚拟机的语言中——特别是 ActionScript 中，往往比直接除以2更快，因为变量不必检查除以0的情况。

- ansiart

---

@minitech：这是一个非常糟糕的测试。测试中的所有代码都是常量。在代码被JIT编译之前，它将消除所有常量。 - user2352506

@M28：我非常确定jsPerf的内部（即eval）每次都会重新发生这种情况。无论如何，是的，这是一个非常糟糕的测试，因为它是一个非常愚蠢的优化。 - Ry-

OP是否特别询问除以2？哪里可能出现除以0的情况？ - Kröw