说明两个数字的安全平均值 [英] Explanation of the safe average of two numbers

问题描述

每当我需要为二进制搜索等算法平均两个数字时，我总是这样做：

Whenever I need to average two numbers for an algorithm like binary search, I always do something like this:

int mid = low + ((high - low) / 2);

我最近看到了另一种在这篇文章，但我不明白。它说你可以在Java中这样做：

I recently saw another way to do it in this post, but I don't understand it. It says you can do this in Java:

int mid = (low + high) >>> 1;

或在C ++中：

int mid = ((unsigned int)low + (unsigned int)high)) >> 1;

C ++版本本质上使两个操作数无符号，因此做一个移位会导致算术移位，签名移位。我知道这两段代码都在做什么，但是如何解决溢出问题？我认为整个问题是中间值高+低可能溢出？

The C++ version essentially makes both operands unsigned, so doing a shift results in an arithmetic shift instead of a signed shift. I understand what both these pieces of code are doing, but how does this solve the overflow issue? I thought the whole issue was that the intermediate value high + low could overflow?

/ strong>

Oh，duh。所有的答案没有完全回答我的问题，但它是@John Zeringue的答案，使其点击。

Oh, duh. All the answers didn't exactly answer my question, but it was @John Zeringue's answer that made it click. I'll try to explain here.

Java中的（高+低）/ 2 t确切地说，高+低溢出（它确实溢出，因为整数都是有符号的，但所有的位仍然存在，没有信息丢失）。采取这样的平均的问题是分裂。除法运算符号值，因此结果将为负数。

The issue with (high + low)/2 in Java isn't exactly that high + low overflows (it does overflow since the integers are both signed, but all the bits are still there, and no information is lost). The issue with taking the average like this is the division. The division is operating on a signed value, so your result will be negative. Using the shift instead will divide by two but consider the bits instead of the sign (effectively treating it as unsigned).

推荐答案

因此，使用shift将除以2，但考虑位而不是符号让我们考虑字节而不是int。唯一的区别是一个字节是一个8位整数，而一个int有32位。在Java中，两者都是签名的，这意味着前导位表示它们是正（0）还是负（1）。

So let's consider bytes instead of ints. The only difference is that a byte is an 8-bit integer, while an int has 32 bits. In Java, both are always signed, meaning that the leading bit indicates whether they're positive (0) or negative (1).

byte low = Byte.valueOf("01111111", 2); // The maximum byte value
byte high = low; // This copies low.

byte sum = low + high; // The bit representation of this is 11111110, which, having a
                       // leading 1, is negative. Consider this the worst case
                       // overflow, since low and high can't be any larger.

byte mid = sum >>> 1; // This correctly gives us 01111111, fixing the overflow.

对于int，这是一回事。基本上这一切的要点是，在有符号整数上使用无符号位移允许您利用前导位来处理最大可能的低和高值。

For ints, it's the same thing. Basically the gist of all this is that using an unsigned bitshift on signed integers allows you to leverage the leading bit to handle the largest possible values of low and high.

这篇关于说明两个数字的安全平均值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！