为什么left+(right-left)/2不会溢出？

问题描述 投票：0回答：8

在这篇文章中：http://googleresearch.blogspot.sg/2006/06/extra-extra-read-all-about-it-nearly.html，它提到大多数快速排序算法有一个错误（左+右） )/2，并指出该解决方案使用 

left+(right-left)/2
而不是 
(left+right)/2
。 问题中也给出了解决方案Bug in fastsort example (K&R C book)?

我的问题是为什么

left+(right-left)/2
可以避免溢出？如何证明呢？预先感谢。

integer-overflow
8个回答
49
投票

根据定义，您拥有 

left < right
。

因此，

right - left > 0
，以及
left + (right - left) = right
（来自基本代数）。

因此

left + (right - left) / 2 <= right
。因此不会发生溢出，因为操作的每一步都受 
right
的值限制。

相比之下，考虑一下有缺陷的表达式，

(left + right) / 2
。 
left + right >= right
，并且由于我们不知道
left
和
right
的值，因此该值完全有可能溢出。

15
投票

假设（为了使示例更容易）最大整数为 100、

left = 50
和 
right = 80
。如果你使用朴素的公式：

int mid = (left + right)/2;

相加会导致

130
，溢出。

如果您这样做：

int mid = left + (right - left)/2;

你不能在

(right - left)
中溢出，因为你是从一个较大的数字中减去一个较小的数字。这总是会导致一个更小的数字，因此它不可能超过最大值。例如。 
80 - 50 = 30
。

并且由于结果是

left
和
right
的平均值，因此它必须在它们之间。由于它们都小于最大整数，因此它们之间的任何值也都小于最大值，因此不会溢出。

7
投票

基本逻辑。

  1. 根据定义
    left <= MAX_INT
  2. 根据定义
    right <= MAX_INT
  3. left+(right-left)
    等于 
    right
    ，每 #2
     已经是
    <= MAX_INT
  4. 所以 
    left+(right-left)/2
    也必须 也为 
    <= MAX_INT
    ，因为 
    x/2
    总是小于 
    x
    。

与原版比较

  1. 根据定义
    left <= MAX_INT
  2. 根据定义
    right <= MAX_INT
  3. 因此
    left+right <= MAX_INT
  4. 所以
    (left+right)/2 <= MAX_INT

其中陈述 3 显然是错误的，因为 

left
可以是 
MAX_INT
（陈述 1），
right
也可以（陈述 2）。

7
投票

一个简单的例子将展示它。 为简单起见，假设数字溢出到 

999
以上。 如果我们有：

left = 997
right = 999

然后：

left + right = 1996
在我们到达

/2

 之前，
已经溢出了。 然而：

right - left = 2
(right-left)/2 = 1
left + (right-left)/2 = 997 + 1 = 998

所以我们避免了溢出。

更一般地说（正如其他人所说）：如果 

left
和 
right
都在范围内（并假设 
right > left
，那么 
(right-left)/2
将在范围内，因此 
left + (right-left)/2
也必须在范围内，因为这必须小于
right
（因为您已将 
left
与 
right
之间的差距增加了一半。

6
投票

由于 Java 中 int 数据类型是 32 位（假设编程语言），任何超过 32 位的值都会被滚动。从数值角度来说，这意味着 Integer.MAX_VALUE (2147483647) 加 1 后，返回值将是 -2147483648。

回到上面的问题，让我们假设以下内容：

int left = 1;
int right = Integer.MAX_VALUE;
int mid;

案例1：

mid = (left +right)/2; 
//Here the value of left + right would be -2147483648 which would overflow.

案例2：

mid = left + (right - left)/2;
//This would not have the same problem as above as the value would never exceed "right".

理论上：

两个值都与 left + (right - left)/2 = (2*left + right - left)/2 = (left + right)/2

希望这能回答您的问题。

2
投票

（这更像是一种直观的解释，而不是证明。）

假设您的数据为 

unsigned char
、
left = 100
和 
right = 255
（因此 
right
位于范围边缘）。 如果执行 
left + right
，您将得到 355，这不符合 
unsigned char
范围，因此会溢出。

但是，

(right-left)/2
是一个量 
X
，使得 
left + X < right < MAX
，其中 
MAX
对于 
unsigned char
来说是 255。这样，您就可以确保总和永远不会溢出。

0
投票

为什么不是 m = (l - r) / 2 ？因为我们不需要已经遍历过的索引，从开始到当前左边在哪里？

0
投票

关于问题本身，前面的答案已经解释得很清楚了。但当我试图弄清楚它的运作机制时，我发现了一些有趣的事情。

新的问题是当代码

mid = left + right - left
运行时会发生什么，它会先做
add
然后做
sub
吗？如果是的话，过程中会不会溢出？结果会不会被感染？

答案是

add
第一个
sub
是否取决于编译器，如果这样做的话过程会溢出，结果不会被感染。

测试代码

int square() {
    int mid, left = 2147483647, right = 2147483647;
    mid = left + right - left;
    return mid;
}

x86-64 Clang 18.1.0 编译后：

square:                                 # @square
        push    rbp
        mov     rbp, rsp
        mov     dword ptr [rbp - 8], 2147483647
        mov     dword ptr [rbp - 12], 2147483647
        mov     eax, dword ptr [rbp - 8]
        add     eax, dword ptr [rbp - 12] # add first (eax = -2)
        sub     eax, dword ptr [rbp - 8]  # sub second (eax = 2147483647) 
        mov     dword ptr [rbp - 4], eax
        mov     eax, dword ptr [rbp - 4]
        pop     rbp
        ret

x86-64 gcc 14.1编译后

square:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], 2147483647
        mov     DWORD PTR [rbp-8], 2147483647
        mov     eax, DWORD PTR [rbp-8]
        mov     DWORD PTR [rbp-12], eax
        mov     eax, DWORD PTR [rbp-12]  # it does't even do the simple math totally (optimized)
        pop     rbp
        ret

loongarch64 gcc 14.1.0编译后

square:
        addi.d  $r3,$r3,-32
        st.d    $r22,$r3,24
        addi.d  $r22,$r3,32
        lu12i.w $r12,2147479552>>12                 # 0x7ffff000
        ori     $r12,$r12,4095
        st.w    $r12,$r22,-20
        lu12i.w $r12,2147479552>>12                 # 0x7ffff000
        ori     $r12,$r12,4095
        st.w    $r12,$r22,-24
        ld.w    $r12,$r22,-24   # first
        st.w    $r12,$r22,-28   # second (same like gcc too, optimized)
        ldptr.w $r12,$r22,-28
        or      $r4,$r12,$r0
        ld.d    $r22,$r3,24
        addi.d  $r3,$r3,32
        jr      $r1

所以，结论是虽然进程溢出，但结果并没有完全被感染（注意不要和

left + right
混淆，这确实会终止你的运行）

最后免责声明：汇编代码来自Compilers，答案仅供娱乐，请勿践踏。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.