Почему в Java (высокий + низкий)/2 ошибочен, но (высокий + низкий) >>> 1 нет?

Я понимаю, что >>> исправляет переполнение: при добавлении двух больших положительных длин вы можете получить отрицательное число. Может кто-нибудь объяснить, как этот побитовый сдвиг магически исправляет проблему переполнения? И как он отличается от >>?

Мое подозрение: я думаю, что это связано с тем, что Java использует два комплимента, поэтому переполнение является правильным числом, если у нас есть дополнительное пространство, но потому что мы не делаем его отрицательным. Поэтому, когда вы смещаетесь и гремете ноль, он волшебным образом фиксируется из-за двух комплиментов. Но я могу ошибаться, и кто-то с пораздельным мозгом должен подтвердить.:)

Ответы

Ответ 1

Короче говоря, (high + low) >>> 1 - это трюк, который использует неиспользуемый знаковый бит для выполнения правильного среднего числа неотрицательных чисел.

В предположении, что high и low являются неотрицательными, мы точно знаем, что самый старший бит (знаковый бит) равен нулю.

Таким образом, оба high и low являются 31-битными целыми числами.

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

Когда вы добавляете их вместе, они могут "разливаться" в верхний бит.

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

  • Как подписанное 32-битное целое число, оно переполняется и переворачивается отрицательно. Поэтому (high + low) / 2 неверно, потому что high + low может быть отрицательным.

  • Как беззнаковые 32-битные целые числа, сумма правильная. Все, что нужно, - это разделить его на 2.

Конечно, Java не поддерживает целые числа без знака, поэтому лучшее, что нам нужно разделить на 2 (как целое без знака), - это логический сдвиг вправо >>>.

В языках с целыми числами без знака (такими как C и С++) становится сложнее, так как ваш ввод может быть полным 32-битным целым числом. Одним из решений является: low + ((high - low) / 2)

Наконец, чтобы перечислить различия между >>>, >> и /:

  • >>> - логический сдвиг вправо. Он заполняет верхние биты нулем.
  • >> - арифметический сдвиг вправо. Он заполняет верхнюю часть его копиями исходного верхнего бита.
  • / является делением.

Математически:

  • x >>> 1 рассматривает x как целое число без знака и делит его на два. Он округляется.
  • x >> 1 рассматривает x как целое число со знаком и делит его на два. Он округляется до отрицательной бесконечности.
  • x / 2 рассматривает x как целое число со знаком и делит его на два. Он округляется до нуля.

Ответ 2

Он нуля заполняет самые верхние биты вместо их заполнения значками.

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

Ответ 3

Я предлагаю прочитать Joch Bloch http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html#!/2006/06/extra-extra-read-all-about-it-nearly.html о высоком и низком

"Версия бинарного поиска, которую я написал для JDK, содержала ту же ошибку. Сообщалось Sun недавно, когда она сломала чьи-то программы, после ожидания в течение девяти лет или около того".