Почему JDK использует смещение вместо умножения / деления? - PullRequest
7 голосов
/ 12 февраля 2012

У меня следующий вопрос:

Если спросить, использовать ли, например, сдвиг или умножение или деление, ответом будет, дайте оптимизировать JVM.

Пример здесь: is-shifting-bits-быстрее-умножения

Теперь я смотрел на источник jdk, например Priority Queue и код использует только сдвиг для умножения и деления (со знаком и без знака).

Принимая как должное, что сообщение в SO является правильным ответом, мне было интересно, почему в jdk они предпочитают делать это путем сдвига?

Это какие-то тонкие детали, не связанные с производительностью?Я подозреваю, что это как-то связано с умножением и делением переполнения / переполнения, но я не уверен.

У кого-нибудь есть идея?Легко ли решаются проблемы переполнения с помощью сдвига?Или это просто вопрос вкуса?

Ответы [ 4 ]

6 голосов
/ 12 февраля 2012

Я думаю, что они делают это в этом конкретном примере, чтобы использовать бит знака. В Java отсутствуют типы без знака, поэтому невозможно эмулировать a >>> 1 с a /= 2 для чисел, которые используют старший значащий бит. Обратите внимание, что код использует только >>> в вашем примере. Я вполне уверен, что это позволит полностью использовать весь диапазон битов.

5 голосов
/ 12 февраля 2012

Помимо того, что в большинстве систем сдвиг быстрее, чем деление. >>> выполняет операцию без знака, а деление - нет. например если вы хотите среднюю точку двух значений, вам нужно использовать >>>, чтобы избежать переполнения. (См. Arrays.binarySearch для аналогичного кода)

3 голосов
/ 12 февраля 2012

Некоторые веские причины предпочитать переключение в Java:

  • Если есть вероятность, что вы работаете в неоптимизированной среде , и вы не можете гарантировать, что JIT-компилятор проведет необходимую оптимизацию для вас. Это, вероятно, редкость в наше время, но все же может произойти при некоторых обстоятельствах.
  • Если вы действительно выполняете битовые манипуляции , а не числовые операции - в исходном коде более ясно использовать сдвиги напрямую
  • Если вы хотите операции без знака (например, вы можете легко выполнять смены без знака, но без деления без знака)
2 голосов
/ 12 февраля 2012

Это больше вопрос вкуса.Некоторые люди настолько привыкли к бинарным операциям, что они более естественны для них (я лично также использую такие в коде, который я пишу для себя).Однако с точки зрения производительности они ведут себя одинаково (оптимизация происходит во время компиляции, поэтому использование сдвигов улучшит время компиляции, но с небольшой долей, и вы можете пренебречь этим). И, как это часто бывает, из каждого ответа, который я даю, я узнаю что-то новое: рассмотрим это .Это доказывает, почему деление на два не всегда может быть оптимизировано для сдвига.Так что мой вышеупомянутый комментарий почти полностью неверен, если у java нет беззнаковых типов.

...