仅使用整数求两个数字的平均值

Question

我需要仅使用 int 作为数据类型来计算两个数字的平均值。我不能使用公式 (x1+x2)/2 = mean，因为如果数字足够大，这会导致溢出。

我找到了这个公式

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

来自此线程 Explanation of the safe average of two numbers。

但是，当涉及负数时，此公式不起作用。有没有人对如何解决这个问题有任何想法？谢谢

编辑 - Java

Answer 1

像这样的东西应该可以工作

private int findAverage(int lower, int higher) {
    int lowerCopy = lower;
    int higherCopy = higher;
    boolean averageFound = false;
    while (!averageFound) {
        lowerCopy++;
        higherCopy--;
        averageFound = isAverageFound(lowerCopy, higherCopy);
    }
    return getAverage(lowerCopy, higherCopy);
}

其中 isAverageFound 将通过检查值是否彼此相等或彼此相差来实现。

这应该适用于所有数字范围，无论是正数还是负数

Answer 2

private void findAverage(int lower, int higher) {
    int lowerCopy = lower;
    int higherCopy = higher;
    int cnt = 1;
    boolean averageFound = false;
    while (!averageFound) {
        lowerCopy++;
        higherCopy--;
        ++cnt;
        averageFound = isAverageFound(lowerCopy, higherCopy);
    }
}


private boolean isAverageFound(int l, int h){
  if(l < h)
     return false;
   else if(l == h){
     System.out.print("average:" + l);
     return true;
   }else{
     System.out.print("average:" + (h/2));  
     return true;       
   }
}

是的。它被留下来改变。对于大的负值和大的正值范围，它会起作用。但是，我同意这需要 O(high + low) 时间。

Answer 3

您说您不能使用 μ=(x+y)/2 形式，但这基本上是唯一有意义的计算方法。你确实提出了一个关于溢出的好点，但只需要一点非常基本的代数就可以找到它。还记得分配式属性吗？

μ = (x + y) / 2 = x/2 + y/2

通过在将两个整数相加之前将它们除以 2，可以降低溢出的风险。尝试将两个值都设置为 Integer.MAX_VALUE（尽管首先阅读整个 post）。所以...

int avg(int x, int y) {
    return x/2 + y/2;
}

...应该为您完成。请记住，您只使用 ints 吗？当涉及到奇数时，您将需要担心一些精度问题……例如，如果您执行 avg(1, 1)，您将得到 0 的结果。我会考虑并解决这个问题对你来说是个问题，但这应该会让你走上正确的道路。

Answer 4

这应该适用于负值和正值，因为在这种情况下符号位没有移动：

// Convert the add operation as long to prevent overflow in case you use big
// integers
long total = (long) low + (long) high;
// Convert the mid value back to an int
int mid = (int) (total >> 1);

注意： 当且仅当 low 和 high 都是 int 这似乎是这种情况你的问题。

仅使用整数求两个数字的平均值

Finding average of two numbers using only ints

java

int

overflow