Должен ли я смещать биты, чтобы разделить на 2 в Java?

Возможные дубликаты:
Сдвиг битов быстрее, чем умножение и деление в Java? .NET?
Быстрый вопрос по оптимизации Java

Много лет назад в колледже я узнал, что сдвиг битов вправо на единицу выполняет то же самое, что и деление на два, но обычно значительно быстрее. Я не уверен, как Java продвинулась в этом отношении с тех пор, как 9-10 лет назад я узнал об этом. Преобразует ли компилятор Java автоматически деление на два в операцию побитового сдвига, или я должен вручную выполнить операцию побитового сдвига в коде самостоятельно?


java performance division bit-manipulation bit-shift
person Matt Huggins    schedule 01.11.2010    source источник
comment
stackoverflow.com/questions/1514949/ Он касается умножения на два, но ответы применимы.   -  person robert_x44    schedule 01.11.2010
comment
Возможный дубликат: stackoverflow.com/questions/1168451/   -  person Galactus    schedule 01.11.2010
comment
В общем, если операция A выполняет точно то же самое, что и операция B, и делает это быстрее, где-то вдоль линии B, вероятно, будет оптимизирована в A. Проблема заключается в том, что существуют пограничные различия, такие что одно не может быть оптимизировано в другое. В этих случаях вы должны 1) оценить, действительно ли разница в производительности имеет значение (без преждевременной оптимизации!), 2) учесть пограничные случаи (запрограммировать их или доказать, что они не будут затронуты, и 3) определить, будут ли выгоды существуют и оправдывают снижение читабельности.   -  person Mark Peters    schedule 01.11.2010
comment
Я глубоко опечален спектром ответов, полученных на этот вопрос. Во-первых, деление на два и сдвиг вправо на единицу не во всех случаях даст одинаковый результат для отрицательных чисел. Во-вторых, там, где достаточно сдвинутого результата, он примерно в 10–20 раз быстрее, чем деление. В-третьих, компилятор не будет оптимизировать это, потому что в любом нетривиальном случае он не сможет доказать, что сдвинутый операнд не является отрицательным. Да, и ответы на вопрос об умножении не распространяются на деление, так как с оптимизаторами дело обстоит иначе xD   -  person Durandal    schedule 02.11.2010
comment
битовый сдвиг — это не то же самое, что деление. Доказательство: утверждение ((-3 ›› 1) == (-3/2))   -  person Nils Pipenbrinck    schedule 02.11.2010
comment
@Pipenbrinck - Извините, я говорил о целых числах и округлении, но забыл уточнить. Спасибо что подметил это.   -  person Matt Huggins    schedule 02.11.2010
comment
Это одна из оптимизаций, выполняемых инструментом Proguard. Так что, если вы используете этот инструмент, вам не нужно будет делать это самостоятельно.   -  person Phantômaxx    schedule 11.04.2014
comment
Вы не должны видеть это в коде. Если вы видите это в коде и недостаточно хорошо знаете сдвиг битов, вам, вероятно, не следует там работать. Он будет МНОГО использоваться в шейдерах и подобном коде, где вы уже должны быть ОЧЕНЬ знакомы с методами низкого уровня. В других типах кода, таких как бизнес-логика, он редко нужен.   -  person Killroy    schedule 18.08.2015
comment
Какой вариант лучше использовать для деления целого числа на 2?   -  person phuclv    schedule 07.06.2017
comment
Я знаю, что это старый вопрос, но: о положительных целых числах. Если вы добавляете числа, чтобы найти середину, даже если это неясный код, этот подход безопасен против числового переполнения: int middle = (Integer.MAX_VALUE + Integer.MAX_VALUE) › ›› 1; возвращает MAX_VALUE, а если вы делаете с / 2: int middle = (Integer.MAX_VALUE + Integer.MAX_VALUE) /2; вызывает переполнение и возвращает -1. Просто кое-что, что нужно иметь в виду.   -  person Brother    schedule 27.09.2019

Ответы (4)


arrow_upward
67
arrow_downward

Если вы не работаете в магазине и кодовой базе, где битовый сдвиг является обычным явлением, ИМХО, вы рискуете запутаться. Да, выражения могут быть логически эквивалентны, но:

  • n00b может запутаться из-за альтернативного синтаксиса.
  • Старик, которому не приходилось менять биты со времен колледжа, вроде меня, может запутаться.
  • Если вы немного сдвинетесь и почувствуете необходимость прокомментировать то, что вы только что сделали, то вы определенно не в теме. Простое деление самодокументируется и будет понятно любому, кто знаком с элементарной математикой.
  • Вы не собираетесь перехитрить компилятор для оптимизации чего-то такого простого, так что даже не пытайтесь.
  • В качестве хорошей практики кодирования лучше сделать ваш код простым/ванильным, а не умным (er)

Все это относительно и, опять же, действительно зависит от стандартов вашего магазина. Если ваши коллеги любят сдвигать биты, то обязательно идите вперед и делайте сдвиг битов.

person Paul Sasik    schedule 01.11.2010
comment
Это в глазах смотрящего. Почему x * 2 менее запутан, чем x << 1? Разве x << 1 не означает явно x * 2 ? Это как сказать, что x + 1 понятнее, чем 1 + x. - person Pacerier; 31.01.2012
comment
Многие программисты, особенно младшие разработчики, не знакомы с битовыми сдвигами или не сразу понимают их назначение. По сути, это аргумент удобства использования для программистов, которые могут работать над кодом после вас. - person cacois; 25.10.2012
comment
Вы всегда можете прокомментировать код; и зачем предполагать контекст, в котором это рассматривается, когда ничего не дано? - person Chris2048; 09.08.2013
comment
@Chris2048: Если вам нужно прокомментировать код, потому что ваш выбор оператора может изначально сбить с толку другого программиста, тогда, IMO, вы только что усложнили понимание кода. - person Paul Sasik; 09.08.2013
comment
@Pacerier: x << 1, эквивалентный x * 2, будет понятен только программистам, которым нужно или хочется часто возиться с битами. Мне не приходилось ничего сдвигать по битам с тех пор, как я учился на втором курсе в колледже, много лет назад, и если бы я увидел сдвиг по битам вместо простого символа деления или умножения в коде, это только спровоцировало бы WTF? - person Paul Sasik; 09.08.2013
comment
Другими словами, это утверждение @PaulSasik — это вопрос абстракций. Да, число внутренне представлено в двоичном виде, но когда у программиста есть число x, и он хочет разделить его на число, которое оказывается равным 2 (потому что мы любим половинки), программист находится на уровне абстракции десятичного числа. числа. Сдвиг в этом слое умножается на 10. Чтобы увидеть x >> 1 как x / 2, нужно спуститься на уровень абстракции к двоичному представлению. Сдвиг битов имеет смысл, когда программист уже находится на уровне двоичной абстракции и имеет дело с двоичными числами. - person Dandre Allison; 11.01.2014
comment
Вставьте битовый сдвиг в код. Таким образом, все люди узнают об этой технике. :) - person sjas; 24.08.2014
comment
Да, поставьте битовый сдвиг в код. Таким образом, ваша команда усвоит ценный урок, когда система разрастется, а затем выйдет из строя по странным причинам, вызванным непониманием разницы между умножением на 2 и сдвигом битов. - person John Churchill; 17.12.2018

arrow_upward
22
arrow_downward

Да, это самое первое, что сделает любой, кто попытается выполнить оптимизацию компилятора (и делает уже как минимум 5 десятилетий), это, безусловно, делает JIT-компилятор Java, и вам, вероятно, будет очень трудно найти любой компилятор, который этого не делает.

И даже если бы они этого не сделали, это все равно было бы преждевременной микрооптимизацией, которой следует избегать в пользу того, чтобы код был более ясным.

person Michael Borgwardt    schedule 01.11.2010
comment
это должен быть ответ, вместо того, чтобы на самом деле отвечать на вопрос, делает ли это Java или нет, люди танцуют, если это хорошая практика или нет... - person vach; 25.11.2016
comment
Несомненно? Вы тестировали его? Тогда вы будете знать, что это не так и не должно. Потому что они не одинаковы. - person John Churchill; 17.12.2018
comment
@JohnChurchill: у меня есть, и это так. x * 120 компилируется в mov eax,78h; imul edx,eax, а x * 128 компилируется в shl edx,7h - что именно натолкнуло вас на мысль, что это не то же самое? - person Michael Borgwardt; 18.12.2018

arrow_upward
19
arrow_downward

Современные компиляторы достаточно умны, чтобы генерировать самый быстрый код для деления на два. Они сделают смену, если она будет быстрее. Если вы хотите добиться деления на 2, использование деления сделает ваш код более понятным. И вы избежите проблем, когда число, которое нужно разделить, отрицательное.

person Rémi    schedule 01.11.2010
comment
Избежать проблем или вызвать их? Я видел гораздо больше приложений, в которых соблюдение аксиомы (n+d)/d == (n/d)+1 было важно, чем где (-n)/d == -(n=d) имело какое-либо значение. - person supercat; 19.12.2013

arrow_upward
11
arrow_downward

Процедура деления для вашего процессора справится с этим. Вам не нужно это делать.

Это известно как преждевременная оптимизация.

person Malfist    schedule 01.11.2010
comment
Ранняя оптимизация != преждевременная оптимизация. Да, большую часть времени, когда кто-то хочет начать возиться с битами, вероятно, это пример преждевременной оптимизации, но это не всегда так. Я лично видел случаи, когда я получал заметно лучшие результаты, крутя немного, потому что у меня была информация, которой не было у компилятора. Я ненавижу, что все всегда начинают кричать о преждевременной оптимизации!!! всякий раз, когда возникает что-то подобное. - person Michael McGowan; 01.11.2010
comment
Я бы с этим согласился, но по большому счету это была бы преждевременная оптимизация. И часто оптимизация заключается не столько в том, чтобы найти что-то немного более быстрое и использовать его вместо этого, а в том, чтобы найти новый способ решения проблемы, который требует меньше усилий. - person Malfist; 01.11.2010
comment
«Процедура» деления вашего процессора на самом деле является инструкцией, и она всегда будет примерно в 20 раз медленнее, чем битовый сдвиг. «Компилятор» может заменить деление сдвигом, но не более того. - person Nils Pipenbrinck; 02.11.2010
comment
@Nils Pipenbrinck, откуда у вас в 20 раз медленнее? Я бы предположил, что в лучшем случае это будет зависеть от архитектуры. - person Malfist; 03.11.2010
comment
Сдвиг будет инструкцией одного цикла почти на всех архитектурах, в то время как лучшие процессоры могут выполнять только 2 бита деления за цикл (новейший делитель Intel Core RADIX-16). для 32 бит, что составляет 1 цикл для сдвига против 16 циклов для деления в лучшем случае. Добавьте к этому первоначальные затраты и простои конвейера, и вы получите коэффициент около 20. - person Nils Pipenbrinck; 04.11.2010
comment
Это похоже на утвердительный ответ на случай 80%; остальные 20% тоже следует учитывать. - person Chris2048; 09.08.2013
comment
Хорошо, если это опоздание на 3 года, но простое сравнение времени деления и сдвига битов показывает сдвиг битов в ~ 5 раз быстрее при 1 миллиарде вычислений. Не уверен, сколько вычислений вам потребуется, чтобы достичь этой отметки x20, но я предполагаю, что вы все равно будете ждать ее завершения :) - person jason todd; 03.10.2013