Объяснение безопасного среднего из двух чисел
Всякий раз, когда мне нужно усреднить два числа для алгоритма, такого как двоичный поиск, я всегда делаю что-то вроде этого:
int mid = low + ((high - low) / 2);
Недавно я видел другой способ сделать это в этом посте, но я не понимаю этого. Он говорит, что вы можете сделать это на Java:
int mid = (low + high) >>> 1;
или это в C++:
int mid = ((unsigned int)low + (unsigned int)high)) >> 1;
Версия C++ по существу делает оба операнда беззнаковыми, поэтому выполнение сдвига приводит к арифметическому сдвигу вместо знакового сдвига. Я понимаю, что делают обе эти части кода, но как это решает проблему переполнения? Я думал, что вся проблема заключалась в том, что промежуточное значение high + low может переполниться?
Редактировать:
О, да. Все ответы не совсем отвечали на мой вопрос, но это был ответ @John Zeringue, который заставил его щелкнуть. Я постараюсь объяснить здесь.
Вопрос с (high + low)/2 в Java не совсем так high + low переполнение (переполнение происходит, поскольку целые числа оба подписаны, но все биты все еще там, и информация не теряется). Проблема с принятием среднего, как это является делением. Подразделение работает со значением со знаком, поэтому ваш результат будет отрицательным. Использование сдвига вместо этого делит на два, но учитывает биты вместо знака (фактически рассматривая его как беззнаковый).
6 ответов
Итак, давайте рассмотрим байты вместо целых. Единственное отличие состоит в том, что байт представляет собой 8-битное целое число, а int имеет 32 бита. В Java оба всегда подписаны, это означает, что ведущий бит указывает, являются ли они положительными (0) или отрицательными (1).
byte low = Byte.valueOf("01111111", 2); // The maximum byte value
byte high = low; // This copies low.
byte sum = low + high; // The bit representation of this is 11111110, which, having a
// leading 1, is negative. Consider this the worst case
// overflow, since low and high can't be any larger.
byte mid = sum >>> 1; // This correctly gives us 01111111, fixing the overflow.
Для целых это одно и то же. По сути, суть всего этого заключается в том, что использование битового смещения без знака для целых чисел со знаком позволяет использовать ведущий бит для обработки максимально возможных значений низких и высоких значений.
Код, который вы видели, не работает: он неправильно вычисляет среднее число отрицательных чисел. Если вы работаете только с неотрицательными значениями, такими как индексы, это нормально, но это не является обычной заменой. Код у вас изначально,
int mid = low + ((high - low) / 2);
не безопасен от переполнения либо потому, что разница high - low может переполнить диапазон для целых чисел со знаком. Опять же, если вы работаете только с неотрицательными целыми числами, это нормально.
Используя тот факт, что A+B = 2*(A&B) + A^B мы можем вычислить среднее из двух целых чисел без переполнения следующим образом:
int mid = (high&low) + (high^low)/2;
Вы можете вычислить деление на 2, используя сдвиг битов, но имейте в виду, что они не одинаковы: деление округляется до 0, тогда как сдвиг битов всегда округляется вниз.
int mid = (high&low) + ((high^low)>>1);
Версия C++ имеет скрытый чит: low а также high являются intно они никогда не бывают негативными. Когда вы бросаете их unsigned int Ваш знаковый бит становится битом дополнительной точности, который не может переполнить одно добавление.
Это не очень хороший чит, потому что индексы массива должны быть unsigned тем не мение.
Как было сказано в другом месте, i >> 1 средства /2 для целых чисел без знака.
Версия C++ не решает проблему переполнения. Это только решает проблему успешного деления на 2, используя сдвиг вместо /Оптимизация, которую ваш компилятор сможет сделать сам, если это приведет к улучшению производительности.
С другой стороны, переполнение может не быть реальной проблемой, если ваши целочисленные типы достаточно велики, чтобы содержать разумный диапазон индексов.
Вы не можете использовать неподписанный int в Java. В случае переполнения учитываются младшие 32 бита, а старшие биты отбрасываются. Смещение вправо без знака поможет вам рассматривать int как неподписанное int. Однако в C++ у вас не будет переполнения.
Вы защищены от целочисленных переполнений, используя способ, который, как вы сказали, уже используете, а именно:
int mid = low + ((high - low) / 2);
Пусть ваш компилятор выполнит свою работу, чтобы оптимизировать это, если это необходимо.
Похоже, что методы синтеза программ решают такие проблемы.
В этом видео программист задает ограничения а) без переполнения, б) без деления и в) без "если-то-еще". Синтезатор автоматически придумал что-то очень приятное.