Znaczenie dwóch int (lub longs) bez przepełnienia, obcięcie w kierunku 0

Question

Chciałbym sposób obliczyć (x + y)/2 dla dowolnych dwóch liczb całkowitych x, y w Javie. W naiwny sposób występują problemy, jeśli x + y> Integer.MAX_VALUE lub < Integer.MIN_VALUE.

Guava IntMathuses tej techniki:

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); 
    } 

... ale zaokrągla do minus nieskończoności, to znaczy procedura nie zgadza się z naiwnych sposób jak dla wartości {-1, -2} (dając -2, zamiast -1).

Czy istnieje odpowiednia procedura, która skraca się w kierunku 0?

"Po prostu użyj long" nie jest odpowiedź, której szukam, ponieważ chcę metodę, która działa również dla długich danych wejściowych. BigInteger również nie jest odpowiedzią, której szukam. Nie chcę rozwiązania z żadnymi oddziałami.

Answer 1

Musisz dodać 1 do wyniku, jeśli najniższe bity są różne (więc wynik nie jest dokładny i trzeba zaokrąglić), a bit znaku w wyniku jest ustawiony (wynik jest ujemny, więc chcesz zmienić rundę w rundę w górę).

więc następujące powinien zrobić (niesprawdzone):

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

Answer 2

Dlaczego nie zrobisz czegoś takiego jak (x-y)/2 + y, który redukuje się do x/2 - y/2 + y = x/2 + y/2? Jeśli więc x+y daje przepełnienie lub niedopełnienie, robisz to w sposób (x-y)/2 + y.