平均两个整数（或多头），而不溢出，对0截断 [英] Mean of two ints (or longs) without overflow, truncating towards 0

问题描述

我想一个方法来计算在Java中（X + Y）/ 2 任何两个整数X，Y。天真的方式，从如果X + Y> Integer.MAX_VALUE的，或LT问题的病人; Integer.MIN_VALUE的。

I'd like a way to calculate (x + y)/2 for any two integers x, y in Java. The naive way suffers from issues if x+y > Integer.MAX_VALUE, or < Integer.MIN_VALUE.

番石榴 IntMath uses此技术：

  public static int mean(int x, int y) {
    // Efficient method for computing the arithmetic mean.
    // The alternative (x + y) / 2 fails for large values.
    // The alternative (x + y) >>> 1 fails for negative values.
    return (x & y) + ((x ^ y) >> 1);
  }

...但是这轮朝负无穷大，这意味着该例程不与幼稚方式同意像值{-1，-2}（给予-2，而不是-1）

... but this rounds towards negative infinity, meaning the routine doesn't agree with the naive way for values like {-1, -2} (giving -2, rather than -1).

有哪些截断向0任​​何相应的程序？

Is there any corresponding routine which truncates towards 0?

只要用长是不是我要找的答案，因为我想要一个长期的投入太奏效的方法。 的BigInteger 也没有我要找的答案。我不想与任何分支机构的解决方案。

"Just use long" is not the answer I'm looking for, since I want a method that works for long inputs too. BigInteger is also not the answer I'm looking for. I don't want a solution with any branches.

推荐答案

您需要 1 添加到结果，如果最低位是不同的（所以结果不准确，你需要四舍五入），并在结果的符号位（结果是否定的，所以你要改变下一轮成圆了）。

You need to add 1 to the result if the lowest bits are different (so the result is not exact and you need to round), and the sign bit in the result is set (the result is negative, so you want to change the round down into a round up).

所以下面应该做（未经测试）：

So the following should do (untested):

public static int mean(int x, int y) {
    int xor = x ^ y;
    int roundedDown = (x & y) + (xor >> 1);
    return roundedDown + (1 & xor & (roundedDown >>> 31));
}

这篇关于平均两个整数（或多头），而不溢出，对0截断的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！