Dlaczego w Javie (wysoki + niski)/2 jest zły, ale (wysoki i niski) >>> 1 nie jest?

Question

Rozumiem, że >>> rozwiązuje problem przepełnienia: podczas dodawania dwóch dużych pozytywnych długich można uzyskać liczbę ujemną. Czy ktoś może wyjaśnić, w jaki sposób to przesunięcie bitowe magicznie rozwiązuje problem przepełnienia? A jak to jest inne niż >>?

---

My podejrzane: Myślę, że ma to związek z faktem, że Java wykorzystuje dwie komplementy więc przelewowy jest właściwa liczba gdybyśmy mieli więcej przestrzeni, ale dlatego, że nie staje się ujemny. Więc kiedy przesuniesz się i wiosłujesz z zerem, magicznie zostaje ustalony dzięki dwóm komplementom. Ale mogę się mylić i ktoś z odrobiną mózgu musi to potwierdzić. :)

Answer 1

W skrócie, (high + low) >>> 1 to trik, który wykorzystuje nieużywane znak-bit do wykonania poprawnego średnią liczb nieujemnych.

---

Przy założeniu, że high i low są zarówno nieujemna, wiemy na pewno, że górny najbardziej bit (znak-bit) wynosi zero.

Tak więc oba high i low są w rzeczywistości 31-bitowymi liczbami całkowitymi.

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

Po dodaniu ich razem mogą "rozlać się" na górny bit.

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 

• W 32-bitowej liczby całkowitej, to przepełnienia i przerzuca ujemny. Dlatego (high + low)/2 jest nieprawidłowy, ponieważ high + low może być ujemny.

• Jako 32-bitowe liczby całkowite bez znaku suma jest prawidłowa. Wszystko, co potrzebne jest, aby podzielić przez 2.

Oczywiście Java nie obsługuje liczb całkowitych, więc najlepsze, co musimy podzielić przez 2 (jako liczba całkowita bez znaku) jest logiczną prawy shift >>> .

W językach z liczb całkowitych bez znaku (takich jak C i C++), staje się trudniejsze, ponieważ dane wejściowe mogą być pełne 32-bitowych liczb całkowitych. Jednym z rozwiązań jest: low + ((high - low)/2)

---

Wreszcie wyliczyć różnice między >>>, >> i /:

• >>> logiczne jest tuż-shift. Wypełnia górne bity wartością zero.
• >> to arytmetyczne przesunięcie w prawo. Wypełnia górną część kopiami oryginalnego bitu górnego.
• / to dział.

matematycznego:

• x >>> 1 traktuje x jako liczba całkowita bez znaku i dzieli się przez dwa. Zaokrągla.
• x >> 1 traktuje x jako liczbę całkowitą ze znakiem i dzieli ją na dwie. Rusza w kierunku ujemnej nieskończoności.
• traktuje x jako liczbę całkowitą ze znakiem i dzieli ją na dwie. Zaokrągla w kierunku zera.

Answer 2

To zero - wypełnia najwyższe bity zamiast wypełniać je znakami.

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

Answer 3

Sugeruję czytać Joch Bloch na http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html#!/2006/06/extra-extra-read-all-about-it-nearly.html o wysokiej i niskiej

„Wersja wyszukiwania binarnego, który napisałem dla JDK zawierał ten sam błąd. Doniesiono Sun niedawno, kiedy to złamał czyjś program , po tym, jak poczekał dziewięć lat.