c++ - 哪个是整数除以 2 的更好选择？

Question

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

技术1：

x = x >> 1;

技术2：

x = x / 2;

这里x是一个整数。

score 853 · Accepted Answer

使用最能描述您正在尝试执行的操作的操作。

如果您将数字视为位序列，请使用 bitshift。
如果您将其视为数值，请使用除法。

请注意，它们并不完全相同。对于负整数，它们可以给出不同的结果。例如：

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

（想法）

score 227 · Accepted Answer

第一个看起来像分裂吗？不，如果要划分，请使用x / 2. 如果可能，编译器可以对其进行优化以使用位移（这称为强度降低），如果您自己进行，这将使其成为无用的微优化。

score 191 · Accepted Answer

继续说：有很多理由支持使用x = x / 2; 这里有一些：

它更清楚地表达了您的意图（假设您没有处理位旋转寄存器位或其他东西）
无论如何，编译器都会将其简化为移位操作
即使编译器没有减少它并选择了比 shift 更慢的操作，这最终以可测量的方式影响程序性能的可能性本身也很小（如果它确实对它产生了可测量的影响，那么你有一个实际的使用轮班的理由）
如果除法将成为更大表达式的一部分，则如果使用除法运算符，则更有可能获得正确的优先级：
```
x = x / 2 + 5;
x = x >> 1 + 5;  // not the same as above
```
有符号算术可能比上面提到的优先级问题更复杂
重申一下 - 无论如何，编译器都会为您执行此操作。实际上，它会将除以常数转换为一系列移位、加法和乘法运算，而不仅仅是 2 的幂。请参阅此问题以获取有关此问题的更多信息的链接。

简而言之，当你真的想要乘法或除法时，你编写一个班次代码什么都没有，除非可能会增加引入错误的可能性。这是一生，因为编译器不够聪明，无法在适当的时候将这种事情优化为转变。

score 63 · Accepted Answer

哪一个是最好的选择，为什么要将整数除以 2？

取决于你的意思best。

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

如果您想将一个数字除以 2，请使用第二个数字。

两者不相等，如果数字为负数或在较大的表达式中，它们的行为就不一样 - 位移位的优先级低于+or -，除法的优先级更高。

您应该编写代码来表达其意图。如果您关心性能，请不要担心，优化器在这些微优化方面做得很好。

score 60 · Accepted Answer

60

只需使用除 ( /)，假设它更清晰。编译器将相应地进行优化。

于 2012-05-21T07:56:04.133 回答

score 39 · Accepted Answer

我同意您应该喜欢的其他答案，x / 2因为它的意图更清晰，编译器应该为您优化它。

然而，另一个优先考虑的原因x / 2是，如果是有符号且为负数x >> 1，则的行为>>取决于实现。xint

从 ISO C99 标准的第 6.5.7 节第 5 点：

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

score 31 · Accepted Answer

x / 2更清晰，x >> 1速度也不快（根据微基准，Java JVM 大约快 30%）。正如其他人所指出的，对于负数，舍入略有不同，因此在处理负数时必须考虑这一点。如果某些编译器知道数字不能为负数，则可能会自动转换x / 2为x >> 1（即使我无法验证这一点）。

甚至x / 2可能不会使用（慢）除 CPU 指令，因为一些捷径是可能的，但它仍然比x >> 1.

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

score 22 · Accepted Answer

克努特说：

过早的优化是万恶之源。

所以我建议使用x /= 2;

这样代码很容易理解，而且我认为以这种形式优化这个操作，对处理器来说并没有太大的区别。

score 18 · Accepted Answer

查看编译器输出以帮助您做出决定。
我使用gcc (GCC) 4.2.1 20070719 [FreeBSD]在 x86-64 上运行了这个测试

另请参阅godbolt 的在线编译器输出。

您看到的是编译器sarl在这两种情况下都使用（算术右移）指令，因此它确实识别出两个表达式之间的相似性。如果使用除法，编译器还需要针对负数进行调整。为此，它将符号位向下移动到最低位，并将其添加到结果中。与除法相比，这解决了在移动负数时的非一问题。
由于除法情况进行了 2 次移位，而显式移位情况仅进行了一次，因此我们现在可以在此处解释由其他答案测量的一些性能差异。

带有汇编输出的 C 代码：

对于除法，您的输入将是

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

这编译为

    movl    %edi, %eax
    shrl    $31, %eax
    addl    %edi, %eax
    sarl    %eax
    ret

同样对于班次

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

输出：

    sarl    %edi
    movl    %edi, %eax
    ret

score 15 · Accepted Answer

只是一个补充说明 -

x *= 0.5 在某些基于 VM 的语言中通常会更快——特别是 actionscript，因为不必检查变量是否被 0 整除。

score 13 · Accepted Answer

使用x = x / 2; OR x /= 2;因为将来可能会有新的程序员使用它。所以他会更容易找出代码行中发生了什么。大家可能不知道这样的优化。

score 12 · Accepted Answer

As far as the CPU is concerned, bit-shift operations are faster than division operations. However, the compiler knows this and will optimize appropriately to the extent that it can, so you can code in the way that makes the most sense and rest easy knowing that your code is running efficiently. But remember that an unsigned int can (in some cases) be optimized better than an int for reasons previously pointed out. If you don't need signed arithmatic, then don't include the sign bit.

score 12 · Accepted Answer

我说的是编程竞赛的目的。通常，它们具有非常大的输入，其中除以 2 发生多次，并且已知输入是正数或负数。

x>>1 将优于 x/2。我通过运行一个程序检查了 ideone.com，其中发生了超过 10^10 除以 2 的操作。x/2 花了将近 5.5 秒，而 x>>1 花了将近 2.6 秒。

score 12 · Accepted Answer

我想说有几件事需要考虑。

位移应该更快，因为实际上不需要特殊的计算来位移位，但是正如所指出的，负数存在潜在的问题。如果您确定有正数，并且正在寻找速度，那么我建议您使用 bitshift。
除法运算符对人类来说非常容易阅读。因此，如果您正在寻找代码可读性，您可以使用它。请注意，编译器优化领域已经取得了长足的进步，因此使代码易于阅读和理解是一种很好的做法。
根据底层硬件，操作可能有不同的速度。Amdal 法则是让普通案件快速解决。因此，您可能拥有比其他硬件更快地执行不同操作的硬件。例如，乘以 0.5 可能比除以 2 更快。（当然，如果您希望强制执行整数除法，则可能需要乘法的下限）。

如果您追求纯粹的性能，我建议您创建一些可以执行数百万次操作的测试。对执行进行多次采样（您的样本大小），以确定哪一个在统计上最适合您的操作系统/硬件/编译器/代码。

score 11 · Accepted Answer

x = x / 2; 是适合使用的代码.. 但操作取决于您自己的程序，您想如何产生输出。

score 11 · Accepted Answer

让你的意图更清楚......例如，如果你想除法，使用 x / 2，并让编译器优化它以移位运算符（或其他任何东西）。

今天的处理器不会让这些优化对程序的性能产生任何影响。

score 10 · Accepted Answer

这个问题的答案将取决于你工作的环境。

如果您正在使用 8 位微控制器或任何没有硬件支持乘法的东西，移位是预期的并且司空见惯，虽然编译器几乎肯定会x /= 2变成x >>= 1，但在该环境中，除法符号的存在会引起更多关注使用移位来实现除法。
如果您在性能关键的环境或代码部分中工作，或者您的代码可以在关闭编译器优化的情况下进行编译，x >>= 1那么最好使用注释来解释其推理，以便清楚地说明目的。
如果您不符合上述条件之一，只需使用x /= 2. 最好为下一个碰巧查看您的代码的程序员节省 10 秒重复执行您的 shift 操作，而不是不必要地证明您知道在没有编译器优化的情况下 shift 更有效。

所有这些都假设无符号整数。简单的转变可能不是您想要的签名。此外，DanielH 提出了关于使用x *= 0.5某些语言（如 ActionScript）的一个好点。

score 8 · Accepted Answer

8

mod 2，测试 = 1。不知道 c 中的语法。但这可能是最快的。

于 2012-05-21T20:30:22.530 回答

score 7 · Accepted Answer

显然，如果您正在为下一个阅读它的人编写代码，请确保“x/2”的清晰性。

但是，如果速度是您的目标，请尝试两种方式并计算结果的时间。几个月前，我研究了一个位图卷积例程，其中涉及遍历整数数组并将每个元素除以 2。我做了各种优化它，包括用“x>>1”替换“x”的老技巧/2"。

当我实际上对两种方式进行计时时，我惊讶地发现x/2 比 x>>1 快

这是使用 Microsoft VS2008 C++ 并打开默认优化。

score 7 · Accepted Answer

一般来说，右移分为：

q = i >> n; is the same as: q = i / 2**n;

这有时用于以清晰度为代价加快程序的速度。我认为你不应该这样做。编译器足够聪明，可以自动执行加速。这意味着换班不会以牺牲清晰度为代价。

看看这个来自 Practical C++ Programming 的页面。

score 4 · Accepted Answer

在性能方面。CPU 的移位操作比除法操作码要快得多。因此除以 2 或乘以 2 等都受益于移位操作。

至于外观和感觉。作为工程师，我们什么时候变得如此痴迷于连美女都不用的化妆品！:)

score 3 · Accepted Answer

X/Y 是正确的...和“>>”移位运算符..如果我们想要两个除以一个整数，我们可以使用 (/) 被除数运算符。移位运算符用于移位位..

x=x/2；x/=2；我们可以这样使用..

score 0 · Accepted Answer

虽然 x>>1 比 x/2 快，但在处理负值时正确使用 >> 有点复杂。它需要类似于以下内容：

// Extension Method
public static class Global {
    public static int ShiftDivBy2(this int x) {
        return (x < 0 ? x + 1 : x) >> 1;
    }
}

c++ - 哪个是整数除以 2 的更好选择？

23 回答 23

Related

Reference