首页 文章

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

提问于
浏览 次
395

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

技术1：

x = x >> 1;

技术2：

x = x / 2;

这里 x 是一个整数 .

c++ c optimization division micro-optimization

23 回答

  • 188

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

    • 如果要将数字视为位序列，请使用bitshift .

    • 如果您将其视为数值，请使用除法 .

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

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

    (ideone)

    回复于
  • 18

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

    回复于
  • 12

    要坚持：有很多理由赞成使用 x = x / 2; 这里有一些：

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

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

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

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

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

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

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

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

    回复于
  • 4

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

    取决于你的意思 best .

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

    If you want to divide a number by 2, go with the second one.

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

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

    回复于
  • 12

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

    回复于
  • 10

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

    但是， x / 2 优于 x >> 1 的另一个原因是 >> 的行为是依赖于实现的，如果 x 是有符号的 int 并且是否定的 .

    从6.5.7节，ISO C99标准的第5章：

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

    回复于
  • 11

    x / 2 更清晰，而且 x >> 1 的速度并不快（根据微基准测试，Java JVM快30％左右） . 正如其他人所指出的那样，对于负数，舍入略有不同，所以当你想要处理负数时你必须考虑这个 . 有些编译器可能会自动将 x / 2 转换为 x >> 1 ，如果他们知道数字不能为负数（即使我认为无法验证这一点） .

    即使 x / 2 也可能不使用（慢）除法CPU指令，因为some shortcuts are possible，但它仍然比 x >> 1 慢 .

    （这是一个C / C问题，其他编程语言有更多的运算符 . 对于Java，还有无符号右移， x >>> 1 ，这又是不同的 . 它允许正确计算两个值的均值（平均值），这样 (a + b) >>> 1 将返回平均值，即使对于非常大的 a 和 b 值 . 如果数组索引可能变得非常大，这对于二进制搜索是必需的 . 有a bug in many versions of binary search，因为他们使用 (a + b) / 2 来计算平均值 . 这不是正确的解决方法是使用 (a + b) >>> 1 代替 . ）

    回复于
  • 11

    克努特说：

    过早优化是万恶之源 .

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

    这样代码很容易理解，而且我认为以这种形式优化此操作，并不意味着处理器的巨大差异 .

    回复于
  • 22

    看看编译器输出，以帮助您决定 . 我在x86-64上运行了这个测试
    gcc（GCC）4.2.1 20070719 [FreeBSD]

    另见compiler outputs online at 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
    回复于
  • 3

    只是一个补充说明 -

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

    回复于
  • 38

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

    回复于
  • 58

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

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

    回复于
  • 7

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

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

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

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

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

    回复于
  • 15

    就CPU而言，位移操作比除法操作更快 . 但是，编译器知道这一点并将在适当的范围内进行适当的优化，因此您可以以最有意义的方式进行编码，并且知道您的代码是否有效运行 . 但请记住，由于之前指出的原因， unsigned int 可以（在某些情况下）优于 int . 如果你不包括符号位 .

    回复于
  • 32

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

    回复于
  • 0

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

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

    回复于
  • 7

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

    • 如果您正在使用8位微控制器或任何没有硬件支持进行乘法运算的东西，那么位移是预期的并且很普通，虽然编译器几乎肯定会将 x /= 2 转换为 x >>= 1 ，但是分割符号的存在会引起更多的关注 . 那个环境比使用转移来实现分裂 .

    • 如果您正在一个性能关键的环境或代码段工作，或者您的代码可以通过关闭编译器优化来编译， x >>= 1 并附有解释其推理的注释可能最好只是为了明确目的 .

    • 如果您不符合上述条件之一，只需使用 x /= 2 即可使代码更具可读性 . 更好的是保存下一个程序员，他们碰巧看你的代码，你的移位操作10秒的双重操作，而不是不必要地证明你知道转换是更有效的没有编译器优化 .

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

    回复于
  • 8

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

    回复于
  • 842

    通常右移分为：

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

    这有时用于以清晰为代价加速程序 . 我认为你不应该这样做 . 编译器足够智能，可以自动执行加速 . 这意味着 putting in a shift gains you nothing at the expense of clarity .

    看看这个page from Practical C++ Programming.

    回复于
  • 62

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

    However, if speed is your goal, try it both ways and time the results. 几个月前，我研究了一个位图卷积例程，它涉及逐步遍历整数数组并将每个元素除以2.我做了各种各样的事情来优化它，包括用"x>>1"代替"x/2"的旧技巧 .

    当我实际上两种方式时，我惊讶地发现 x/2 was faster than x>>1

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

    回复于
  • 12

    在性能方面 . CPU的移位操作比分割操作码快得多 . 所以除以2或乘以2等都可以从换班操作中受益 .

    至于外观和感觉 . 作为工程师，我们什么时候变得如此依赖化妆品，即使是漂亮女士也不会使用！ :)

    回复于
  • 223

    X / Y是正确的...和“>>”移位运算符..如果我们想要两个除以整数我们可以使用（/）除数运算符 . shift运算符用于移位位..

    X = X / 2; X / = 2;我们可以像这样使用..

    回复于
  • 13

    虽然x >> 1比x / 2快，但在处理负值时正确使用>>会稍微复杂一些 . 它需要类似于以下内容：

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

相关问题