哪个是用于将整数除以2的更好选项？

Question

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

技巧1:

x = x >> 1;

技术2:

x = x / 2;

这x是一个整数.

Answer 1

使用最能描述您要执行的操作的操作.

• 如果您将数字视为位序列,请使用bitshift.
• 如果您将其视为数值,请使用除法.

请注意,它们并不完全等效.它们可以为负整数提供不同的结果.例如:

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

(ideone)

Answer 2

第一个看起来像分裂吗？不.如果你想分开,请使用x / 2.如果可能的话,编译器可以对其进行优化以使用位移(称为强度降低),如果您自己进行,则会使其成为无用的微优化.

Answer 3

要坚持:有很多理由支持使用x = x / 2; 以下是一些:

• 它更清楚地表达了你的意图(假设你没有处理比特错误的寄存器位或其他东西)

• 无论如何,编译器会将其减少为移位操作

• 即使编译器没有减少它并选择比移位更慢的操作,这最终会以可测量的方式影响程序性能的可能性本身也很小(如果它确实影响了它,那么你有一个实际的使用班次的原因)

• 如果除法将成为更大表达式的一部分,那么如果使用除法运算符,则更有可能获得优先权:

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

• 签名算术可能比上面提到的优先级问题更复杂

• 重申 - 无论如何编译器已经为你做了这个.实际上,它会将除以常数转换为各种数字的一系列移位,加法和乘法,而不仅仅是2的幂.请参阅此问题以获取有关此内容的更多信息的链接.

简而言之,当你真正想要乘法或除法时,你不需要通过编码移动来购买任何东西,除非可能增加引入错误的可能性.这是一辈子的事情,因为编译器不够智能,无法在适当的时候优化这种转变.

Answer 4

哪一个是最佳选择以及为什么将整数除以2？

取决于你最好的意思.

如果你希望你的同事讨厌你,或者让你的代码难以阅读,我肯定会选择第一个选项.

如果要将数字除以2,请使用第二个数字.

这两个不等价,如果数字为负数或在较大的表达式内,它们的行为不相同 - bitshift的优先级低于+或者-,除法具有更高的优先级.

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

Answer 5

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

Answer 6

我同意你应该支持的其他答案,x / 2因为它的意图更清晰,编译器应该为你优化它.

然而,另一个原因宁愿x / 2在x >> 1是的行为>>是实现相关的,如果x是签名int和为负.

从6.5.7节,ISO C99标准的第5章:

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

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) >>> 1可以了即使对于非常大的a和值,也返回平均值b.如果数组索引可能变得非常大,则需要二进制搜索.在许多版本的二进制搜索中存在一个错误,因为它们用于(a + b) / 2计算平均值.工作正常.正确的解决方案是使用(a + b) >>> 1.)

Answer 8

克努特说:

过早优化是万恶之源.

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

这样代码很容易理解,而且我认为以这种形式优化这个操作,并不意味着处理器有很大的不同.

Answer 9

看看编译器输出,以帮助您决定.我用
xcc(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

Answer 10

只是一个补充说明 -

在某些基于VM的语言中,x*= 0.5通常会更快 - 特别是actionscript,因为不必检查变量除以0.

Answer 11

使用x = x / 2; OR x /= 2;因为将来新程序员可能会使用它.因此,他更容易找到代码行中发生的事情.每个人都可能不知道这种优化.

Answer 12

我告诉编程比赛的目的.通常它们具有非常大的输入,其中除以2发生多次并且已知输入为正或负.

x >> 1将优于x/2.我通过运行一个程序来检查ideone.com,该程序进行了超过10 ^ 10除以2的操作.x/2花费了近5.5秒而x >> 1花费了近2.6秒的同一节目.

Answer 13

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

1. Bitshift应该更快,因为实际上不需要特殊的计算来移位位,但是正如所指出的那样,负数存在潜在的问题.如果你确保有正数,并且正在寻找速度,那么我会推荐bitshift.

2. 除法运算符对人类来说非常容易阅读.因此,如果您正在寻找代码可读性,您可以使用它.请注意,编译器优化领域已经走过了漫长的道路,因此使代码易于阅读和理解是一种很好的做法.

3. 根据底层硬件,操作可能具有不同的速度.Amdal的法律是使常见案例快速进行.因此,您可能拥有可以比其他操作更快地执行不同操作的硬件.例如,乘以0.5可能比除以2更快.(如果您希望强制执行整数除法,则可能需要采用乘法的底线).

如果你是在追求纯粹的性能,我建议你创建一些可以进行数百万次操作的测试.多次尝试执行(您的样本大小),以确定哪个在统计上最适合您的OS /硬件/编译器/代码.

Answer 14

就CPU而言,位移操作比除法操作更快.但是,编译器知道这一点,并将在适当的范围内进行适当的优化,因此您可以以最有意义的方式进行编码,并且知道您的代码是否有效运行.但请记住,unsigned int罐头(在某些情况下)的优化程度优于int之前指出的原因.如果您不需要签名算术,则不要包含符号位.

Answer 15

x = x/2; 是适合使用的代码..但操作取决于您自己的程序,您希望如何生成输出.

Answer 16

让你的意图更清晰...例如,如果你想分裂,使用x/2,让编译器优化它以移动运算符(或其他任何东西).

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

Answer 17

答案取决于您所处的环境.

• 如果您正在使用8位微控制器或任何没有硬件支持进行乘法运算的东西,那么位移是预期的并且很普遍,虽然编译器几乎肯定会x /= 2变成x >>= 1,但是分区符号的存在会在该环境中引起更多的关注.使用转移实现分裂.
• 如果您正在一个性能关键的环境或代码段中工作,或者您的代码可以通过编译器优化来编译,x >>= 1那么解释其推理的注释可能最好只是为了明确目的.
• 如果您不符合上述条件之一,只需使用即可使代码更具可读性x /= 2.更好的是保存下一个程序员,他们碰巧看你的代码,你的班次操作10秒加倍,而不必毫无疑问地证明你知道转换是更有效的没有编译器优化.

所有这些都假设无符号整数.简单的转变可能不是你想签名的.此外,DanielH提出了一个关于使用x *= 0.5ActionScript等特定语言的好处.

Answer 18

mod 2,test for = 1. dunno c中的语法.但这可能是最快的.

Answer 19

通常右移分为:

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

这有时用于以清晰为代价加速程序.我认为你不应该这样做.编译器足够智能,可以自动执行加速.这意味着投入班次不会以牺牲清晰度为代价.

从Practical C++ Programming看一下这个页面.

Answer 20

显然,如果你是为下一个阅读它的人编写代码,那么请选择"x/2"的清晰度.

但是,如果速度是您的目标,请尝试两种方式和结果.几个月前,我研究了一个位图卷积例程,它涉及逐步遍历整数数组并将每个元素除以2.我做了各种各样的事情来优化它,包括用"x >> 1"代替"x"的旧技巧/ 2" .

当我实际上两种方式时,我惊讶地发现x/2比x >> 1更快

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