logo标签列表

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

c++coptimizationdivisionmicro-optimization
416

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

技术1：

x = x >> 1;

技巧2：

x = x / 2;

这里的x是一个整数。

77
如果你真的想再次将结果分配给 x，那么这两种方式都不太合适：应该是 x >>= 1 或者 x /= 2，具体取决于你希望表达的操作意义。这并不是因为它更快（现代编译器会将所有等效变体编译为相同、快速的汇编代码），而是因为它更清晰易懂。 - leftaroundabout
35
我不同意leftaroundabout的观点。但是我认为值得注意的是，许多编程语言中都有一种称为"算术移位"的操作，它保留符号位并因此按预期处理带符号值。其语法可能类似于x = x >>> 1。另请注意，根据平台和编译器的不同，手动优化除法和乘法使用移位操作可能是相当合理的。举个例子，微控制器没有直接的ALU支持乘法。 - JimmyB
36
我更喜欢使用x /= 2，因为x >>= 1看起来太像单子绑定（monadic bind）了 ;) - fredoverflow
19
@leftaroundabout - 我认为写x = x / 2比写x /= 2更易读。这可能是主观偏好 :) - JimmyB
8
@HannoBinder：当然是主观的，尤其是很多习惯方面。在一个所有算术运算符都有“⬜=”组合的语言中，只要可能，应该使用这些组合。这可以消除噪音并强调“x”被修改的事实，而一般的“=”运算符则暗示它采用了完全独立于旧值的新值。避免使用组合运算符（这样数学符号的初学者也能读懂）也有其优点，但这样你将需要放弃极其实用的“++”、“--”、“+=”等运算符。 - leftaroundabout
显示剩余6条评论
22个回答
13

我在这里分享一些关于编程竞赛的技巧。通常情况下，竞赛使用非常大的输入数据，其中会多次进行除以2的操作，且已知输入为正数或负数。

对于x/2和x>>1这两种操作，x>>1的效率更高。我在ideone.com上运行了一个程序，在该程序中进行了超过10^10次的除以2操作。结果表明，x/2用了近5.5秒的时间，而x>>1只用了近2.6秒。

1
对于无符号值，编译器应该将 x/2 优化为 x>>1。对于有符号值，几乎所有实现都定义了 x>>1 的含义等同于 x/2，但当 x 为正数时可以更快地计算，并且在 x 为负数时与 x/2 有用的不同。 - supercat
13

我认为有几件事需要考虑：

  1. 按位移动应该更快，因为没有真正需要特殊计算来移动位，但是正如指出的那样，负数可能会存在问题。如果保证输入的是正数，并且想要速度更快，那么我建议使用位移操作。

  2. 除法运算符非常容易被人类阅读理解。因此，如果您正在寻求代码可读性，则可以使用这个。请注意，编译器优化领域已经发展了很长一段时间，因此使代码易于阅读和理解是良好的实践。

  3. 根据底层硬件的不同，操作执行速度可能会有所不同。Amdal定律是让常见情况变得更快。因此，您可能拥有可以比其他操作更快执行的硬件。例如，乘以0.5可能比除以2更快。（当然，如果您希望强制执行整数除法，则可能需要取乘法的向下取整）。

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

2
"位移操作应该更快。编译器会将除法优化为位移操作。" - Trevor Hickey
我希望他们会这样做，但是除非你有编译器源代码的访问权限，否则你不能确定 :) - James Oravec
1
如果某个实现以最常见的方式处理位移并且负数的处理方式与 >> 相匹配且不匹配 /，那么我也建议使用位移运算符。 - supercat
这是一个非常好的答案，不仅总结了上面许多其他帖子的内容，而且列出了许多需要考虑的事情，而不是选择一个主观的立场。 - Kröw
13

就CPU而言，位移操作比除法操作快。 然而，编译器知道这一点并会尽可能地进行优化， 因此您可以按照最有意义的方式编写代码，并放心地知道您的代码正在高效运行。 但请记住，对于先前指出的原因，unsigned int 在某些情况下可以被更好地优化而不是int。 如果您不需要有符号算术运算，则不要包含符号位。

12

使用 x = x / 2; 或 x /= 2;，因为有可能会有新的程序员在未来处理这段代码。这样他就可以更容易地找出代码行中发生了什么。并非所有人都知道此类优化。

10

x = x / 2; 是适合使用的代码。但具体操作取决于你的程序以及你想要生成的输出。

10

让你的意图更明确...例如，如果您想进行除法运算，请使用 x / 2，并让编译器将其优化为移位运算符（或其他任何操作）。

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

9
这取决于你所处的环境。
如果你在8位微控制器或任何没有硬件支持乘法的设备上工作，那么使用位移是很普遍的。虽然编译器几乎肯定会将 x /= 2 转换为 x >>= 1，但在这种情况下，除法符号的存在会比使用移位操作更加引人注目。
如果你在性能关键的环境中编写代码，或者你的代码可能会关闭编译器优化，则最好使用带有说明理由的 x >>= 1，以保持清晰明了的目的。
如果你不处于以上条件之一，那么通过简单地使用 x /= 2 来使你的代码更加易读。比需要无谓地证明你知道移位操作更高效而导致下一个查看你代码的程序员需要费10秒钟才能明白你的移位操作要好得多。
所有这些都假设使用无符号整数。对于带符号的整数，简单的移位操作可能不是你想要的。此外，DanielH提出了一个关于某些语言（如ActionScript）使用 x *=0.5 的好方法。
8

模2，测试等于1。不知道在C语言中的语法，但这可能是最快的方法。

6
一般情况下，右移操作相当于除以2的n次方：
q = i >> n; is the same as: q = i / 2**n;

这种方式有时用于加速程序，但会牺牲代码的清晰度。我认为你不应该这么做。编译器已经足够聪明，可以自动执行加速操作。这意味着，只为了加速而进行位移并不会在清晰度上获得任何收益。请查看 Practical C++ Programming 的此页。
1
如果想要计算出例如(x+128)>>8对于不接近最大值的x值所计算出的数值，怎样才能在没有移位的情况下简洁地完成呢？请注意，(x+128)/256无法达到预期效果。你知道任何适用的表达式吗？ - supercat
6
显然，如果你写代码是为了让下一个读者更容易理解，那么就使用“x/2”这种清晰易懂的方式。
然而，如果速度是你的目标，可以尝试两种方法并计时结果。几个月前，我编写了一个位图卷积程序，需要遍历整数数组并将每个元素除以2。我采用了各种优化措施，包括使用“x>>1”代替“x/2”的老技巧。
当我实际计时比较两种方法时，惊奇地发现“x/2”比“x>>1”更快。这是在使用默认优化设置的Microsoft VS2008 C++环境下进行的测试。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接