Media di due inte (o long) senza overflow, troncata verso 0

Question

Mi piacerebbe un modo per calcolare (x + y)/2 per qualsiasi due interi x, y in Java. Il modo ingenuo soffre di problemi se x + y> Integer.MAX_VALUE o < Integer.MIN_VALUE.

Guava IntMathuses questa tecnica:

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

... ma questo arrotonda verso l'infinito negativo, il che significa la routine non è d'accordo con il modo ingenuo per i valori come {-1, -2} (dando -2, anziché -1).

C'è qualche routine corrispondente che tronca verso 0?

"Basta usare long" non è la risposta che sto cercando, poiché voglio un metodo che funzioni anche per gli input lunghi. BigInteger non è la risposta che sto cercando. Non voglio una soluzione con nessun ramo.

Answer 1

È necessario aggiungere 1 al risultato se i bit più bassi sono diversi (quindi il risultato non è esatto e occorre arrotondare) e il bit di segno nel risultato è impostato (il risultato è negativo, quindi si desidera per cambiare il round in un round up).

Così dovrebbe fare quanto segue (non testato):

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

Perché non si fa qualcosa come (x-y)/2 + y, che si riduce a x/2 - y/2 + y = x/2 + y/2? Quindi se x+y ti dà un overflow o underflow, lo fai nel modo (x-y)/2 + y.