Perché in Java (alto + basso)/2 è sbagliato ma (alto + basso) >>> 1 non è?

Question

Capisco che lo >>> corregge l'overflow: quando si aggiungono due lunghi positivi, è possibile che si ottenga un numero negativo. Qualcuno può spiegare come questo spostamento bit-a-bit risolva magicamente il problema dell'overflow? E in che modo è diverso da >>?

---

mio sospetto: Io penso che abbia a che fare con il fatto che Java utilizza due complimenti così l'overflow è il numero giusto se avessimo lo spazio in più, ma perché non lo facciamo diventa negativo. Quindi, quando si sposta e si paga con lo zero, magicamente viene corretto a causa dei due complimenti. Ma posso sbagliarmi e qualcuno con un cervello bit a bit deve confermare. :)

Answer 1

In breve, (high + low) >>> 1 è un trucco che utilizza il segno-bit non utilizzati per eseguire una corretta media di numeri non negativi.

---

Partendo dal presupposto che high e low sono entrambi non negativo, sappiamo per certo che la parte superiore del bit più (il segno-bit) è pari a zero.

Quindi sia high sia low sono in realtà numeri interi a 31 bit.

high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 
low = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 

Quando li si sommano possono "rovesciarsi" nel bit superiore.

high + low =  1000 0000 0000 0000 0000 0000 0000 0000 
      = 2147483648 as unsigned 32-bit integer 
      = -2147483648 as signed 32-bit integer 

(high + low)/2 = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824 
(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 

• Come un intero a 32 bit con segno, è troppo pieno e ribalta negativo. Pertanto (high + low)/2 è errato perché high + low potrebbe essere negativo.

• Come interi a 32 bit senza segno, la somma è corretta. Tutto ciò che serve è quello di dividerlo per 2.

Naturalmente Java non supporta interi senza segno, quindi la cosa migliore che dobbiamo dividere per 2 (come intero senza segno) è la logica destra-shift >>> .

Nelle lingue con interi senza segno (come C e C++), diventa più complicato dal momento che l'input può essere pieno di interi a 32 bit. Una soluzione è: low + ((high - low)/2)

---

fine di enumerare le differenze tra >>>, >> e /:

• >>> è logico shift destro. Riempie i bit superiori con zero.
• >> è aritmetico a destra. Riempie la parte superiore con copie del primo bit originale.
• / è divisione.

Matematicamente:

• x >>> 1 tratta x come intero senza segno e lo divide per due. Arrotonda.
• x >> 1 tratta x come numero intero con segno e lo divide per due. Arrotonda all'infinito negativo.
• x/2 tratta x come numero intero con segno e lo divide per due. Arrotonda verso lo zero.

Answer 2

Riempie a zero i bit più in alto invece di riempirli con il segno.

int a = 0x40000000; 
(a + a)/2 == 0xC0000000; 
(a + a) >>> 1 == 0x40000000; 

Answer 3

io suggerirei di leggere di http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html#!/2006/06/extra-extra-read-all-about-it-nearly.html su alta e bassa Joch Bloch

"La versione di ricerca binaria che ho scritto per il JDK conteneva lo stesso problema. E 'stato riferito al Sun di recente, quando si ha rotto il programma di qualcuno, dopo aver aspettato per nove anni circa. "