Есть ли веские причины для использования сдвига бит, кроме быстрой математики? - PullRequest
8 голосов
/ 12 сентября 2010

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

Ответы [ 4 ]

11 голосов
/ 12 сентября 2010

Есть много причин, вот некоторые из них:

  1. Допустим, вы представляете черно-белое изображение в виде последовательности битов и хотите в общем случае задать один пиксель в этом изображении. Например, ваше байтовое смещение может быть x >> 3, а ваше битовое смещение может быть x & 0x7, и вы можете установить этот бит: byte = byte | (1 << (x & 0x7)); </li>
  2. Реализация алгоритмов сжатия данных, когда вы имеете дело с битовыми последовательностями переменной длины, например, кодирование Хаффмана.
  3. Вы взаимодействуете с некоторым оборудованием, например, устройство последовательной связи, и вам нужно прочитать или установить некоторые биты управления.

По этим и другим причинам большинство процессоров имеют команды сдвига и / или вращения, а также другие логические инструкции (и / или / xor / нет).

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

Также смотрите здесь: Вам когда-нибудь приходилось использовать сдвиг битов в реальных проектах?

6 голосов
/ 12 сентября 2010

Как вы указали, сдвиг влево - это то же самое, что и умножение на два.По крайней мере, это когда мы говорим о неподписанных количествах.Значение «сдвига влево» количества со знаком ... зависит от языка.

В современных компиляторах нет никакой разницы между написанием «i = x * 2;»и "i = x << 1;"Компилятор сгенерирует наиболее эффективный код.Так что в этом смысле нет причин предпочитать сдвиг умножению. </p>

Некоторые алгоритмы работают, сдвигая величину влево на один бит, а затем устанавливая младший бит равным 0 или 1. Некоторые простые алгоритмы сжатия работают таким образом.Например, если ваше накопленное значение находится в переменной x, а текущее значение (0 или 1) - в y, то имеет смысл написать «x = (x << 1) | y», а не «x= (x * 2) + y ".Оба делают одно и то же, но первое более правильное <em>обозначено .Вам не нужно думать: «О, да, умножение на два - это то же самое, что и сдвиг влево».

Кроме того, когда вы говорите об алгоритмах, которые сдвигают биты, удобнее сдвигать влевоили прямо на конкретное число битов, чтобы выяснить, какое кратное 2 вы хотите умножить или разделить на.

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

4 голосов
/ 12 сентября 2010

Есть много мест, где операции сдвига битов регулярно используются вне их использования в численных вычислениях.Например, Bitboard - это структура данных, которая обычно используется в настольных играх для представления на доске.Некоторые из самых сильных шахматных движков используют эту структуру данных в основном для скорости и простоты генерации и оценки хода.Эти программы интенсивно используют битовые операции, а операции битового сдвига, в частности, используются во многих контекстах - таких как поиск битовых масок, генерация новых движений на доске, очень быстрый расчет логарифма и т. Д. Существуют даже очень сложные численные вычисления,сделано элегантно с помощью умного использования битовых операций.Проверьте этот сайт на предмет взлома бит-твидлинга - многие из этих алгоритмов используют операторы сдвига.Операции сдвига битов регулярно используются при программировании драйверов устройств, разработке кодеков, программировании встроенных систем и т. Д.

1 голос
/ 12 сентября 2010

Shifting позволяет получить доступ к определенным битам в переменной.Выражение (n >> p) & ((1 << m) - 1) извлекает m -битную часть переменной n со смещением p битов справа.

Это позволяет вашей программе использовать целые числа, которые не кратны8 бит, что полезно для сжатия данных.

Например, я использовал его в своих программах Netflix Prize для упаковки записей (22-битный идентификатор пользователя + 15-битный идентификатор фильма + 12-битная дата + 3-разрядный рейтинг) в uint64_t (с резервированием 12 битов).

Очень частый особый случай - упаковка 8 bool переменных в каждый байт.(Права доступа к файлам Unix, черно-белые растровые изображения, регистры флагов ЦП и т.очень популярная кодировка символов.Символы Unicode представляются путем распределения их битов по 1, 2, 3 или 4 байтам.

...