为什么Java（高+低）/ 2错误但（高+低）>>> 1不是？ [英] Why in Java (high + low) / 2 is wrong but (high + low) >>> 1 is not?

问题描述

我理解>>> 修复了溢出：当添加两个大的正数时，你可能会得到一个负数。有人可以解释这种按位转换如何神奇地修复溢出问题吗？它是如何与>> 不同？

I understand the >>> fixes the overflow: when adding two big positive longs you may endup with a negative number. Can someone explain how this bitwise shift magically fixes the overflow problem? And how it is different than >> ?

我怀疑：我认为这与Java使用两个赞美这一事实有关，所以如果我们有额外的空间，但溢出是正确的数字，但是因为我们没有变成负面。所以当你移动并用零划桨时，它会因为两个赞美而神奇地得到修复。但我可能是错的，有点大脑的人必须证实。 ：）

My suspicious: I think it has to do with the fact that Java uses two-compliments so the overflow is the right number if we had the extra space but because we don't it becomes negative. So when you shift and paddle with zero it magically gets fixed due to the two-compliments. But I can be wrong and someone with a bitwise brain has to confirm. :)

推荐答案

简而言之，（高+低）>>> 1 是一种技巧，它使用未使用的符号位来执行非负数的正确平均值。

In short, (high + low) >>> 1 is a trick that uses the unused sign-bit to perform a correct average of non-negative numbers.

假设高且低都是非负数，我们肯定知道最高位（符号位）为零。

Under the assumption that high and low are both non-negative, we know for sure that the upper-most bit (the sign-bit) is zero.

因此高和低实际上是31位整数。

So both high and low are in fact 31-bit integers.

high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824
low  = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

当你将它们加在一起它们可以溢出到顶部位。

When you add them together they may "spill" over into the top-bit.

high + low =       1000 0000 0000 0000 0000 0000 0000 0000
           =  2147483648 as unsigned 32-bit integer
           = -2147483648 as signed   32-bit integer

(high + low) / 2   = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824
(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

• 作为带符号的32位整数，它是溢出并翻转为负。因此（高+低）/ 2 是错误的，因为高+低可能是负数。

  • As a signed 32-bit integer, it is overflow and flips negative. Therefore (high + low) / 2 is wrong because high + low could be negative.

    作为无符号32位整数，总和是正确的。所需要的只是将它除以2.

    As unsigned 32-bit integers, the sum is correct. All that's needed is to divide it by 2.

    当然Java不支持无符号整数，所以最好我们必须除以2（作为无符号整数）是逻辑右移>>> 。

    Of course Java doesn't support unsigned integers, so the best thing we have to divide by 2 (as an unsigned integer) is the logical right-shift >>>.

    在具有无符号整数的语言（例如C和C ++）中，由于输入可以是完整的32位整数，因此它会变得更加棘手。一种解决方案是：低+（（高 - 低）/ 2）

    In languages with unsigned integers (such as C and C++), it gets trickier since your input can be full 32-bit integers. One solution is: low + ((high - low) / 2)

    最后列举>>> ，>> 和<之间的差异code> / ：

    
    
    • >>> 是合乎逻辑的右移。它用零填充高位。
    
    
    • >> 是算术右移。它上面填充了原始顶部位的副本。
    
    
    • / 是分部。
    
    
    • >>> is logical right-shift. It fills the upper bits with zero.
    • >> is arithmetic right-shift. It fills the upper its with copies of the original top bit.
    • / is division.

    数学上：

    
    
    • x>>> ; 1 将 x 视为无符号整数，并将其除以2。它向下舍入。
    
    
    • x>> 1 将 x 视为有符号整数并将其除以2。它朝向负无穷大。
    
    
    • x / 2 将 x 视为有符号整数并将其除以2。它向零舍入。
    
    
    • x >>> 1 treats x as an unsigned integer and divides it by two. It rounds down.
    • x >> 1 treats x as a signed integer and divides it by two. It rounds towards negative infinity.
    • x / 2 treats x as a signed integer and divides it by two. It rounds towards zero.

    这篇关于为什么Java（高+低）/ 2错误但（高+低）&gt;&gt;&gt; 1不是？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！