Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Не путать с Bit banging .

Битовая манипуляция - это акт алгоритмического манипулирования битами или другими частями данных короче слова . Задачи компьютерного программирования , требующие обработки битов, включают низкоуровневое управление устройством, алгоритмы обнаружения и исправления ошибок , сжатие данных , алгоритмы шифрования и оптимизацию . Для большинства других задач современные языки программирования позволяют программисту работать напрямую с абстракциями, а не с битами, которые представляют эти абстракции. Исходный кодкоторая выполняет битовые манипуляции, использует побитовые операции : И, ИЛИ, ИСКЛЮЧАЮЩЕЕ ИЛИ, НЕ и, возможно, другие операции, аналогичные логическим операторам; есть также битовые сдвиги и операции для подсчета единиц и нулей, поиска старших и младших единиц или нуля, установки, сброса и проверки битов, извлечения и вставки полей, масок и нулевых полей, сбора и разброса битов в заданные битовые позиции или поля и из них . Целочисленные арифметические операторы также могут выполнять битовые операции вместе с другими операторами.

Битовые манипуляции в некоторых случаях могут устранить или уменьшить необходимость в цикле по структуре данных и могут дать многократное ускорение, поскольку битовые манипуляции обрабатываются параллельно.

Терминология [ править ]

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

Термин « битовое вращение» восходит к раннему компьютерному оборудованию , когда операторы компьютеров вносили коррективы, настраивая или перекручивая компьютерные элементы управления. По мере развития языков компьютерного программирования программисты использовали этот термин для обозначения любой обработки данных, включающей вычисления на битовом уровне .

Побитовая операция [ править ]

Основная статья: побитовая операция

Поразрядная операция работает с одним или несколькими битовыми комбинациями или двоичными числами на уровне их отдельных битов . Это быстрое примитивное действие, которое напрямую поддерживается центральным процессором (ЦП) и используется для управления значениями для сравнений и вычислений.

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

Пример битовой манипуляции [ править ]

Чтобы определить, является ли число степенью двойки, концептуально мы можем многократно выполнять целочисленное деление на два до тех пор, пока число не перестанет делиться на 2 поровну; если единственный оставшийся множитель равен 1, исходное число было степенью 2. Используя битовые и логические операторы, существует простое выражение, которое вернет истину (1) или ложь (0):

 bool  isPowerOfTwo  =  ( x  ! =  0 )  &&  (( x  &  ( x  -  1 ))  ==  0 );

Второй метод использует тот факт, что степени двойки имеют один и только один бит, установленный в их двоичном представлении:

х == 0 ... 0 1 0 ... 0х-1 == 0 ... 001 ... 1х & (х-1) == 0 ... 000 ... 0

Если число не равно нулю и не является степенью двойки, оно будет иметь «1» более чем в одном месте:

х == 0 ... 1 ... 0 1 0 ... 0х-1 == 0 ... 1 ... 001 ... 1х & (х-1) == 0 ... 1 ... 000 ... 0

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

Операции битовых манипуляций [ править ]

См. Также: Наборы инструкций по манипулированию битами

Процессоры обычно предоставляют только подмножество полезных битовых операторов. Языки программирования не поддерживают напрямую большинство битовых операций, поэтому для их кодирования необходимо использовать идиомы. Например, язык программирования C предоставляет только побитовое И (&), ИЛИ (|), XOR (^) и НЕ (~). Fortran предоставляет операции AND (.and.), OR (.or.), XOR (.neqv.) И EQV (.eqv.). Алгол обеспечивает извлечение и вставку синтаксических битовых полей. Когда языки предоставляют битовые операции, которые напрямую не отображаются на аппаратные инструкции, компиляторы должны синтезировать операцию из доступных операторов.

Особенно полезной битовой операцией является подсчет начальных нулей, используемых для поиска старшего бита машинного слова, хотя на разных архитектурах у него могут быть разные имена. [1] Не существует простой идиомы языка программирования, поэтому она должна предоставляться встроенной функцией компилятора или подпрограммой системной библиотеки. Без этого оператора очень дорого (см. Найти первый набор # CLZ ) любые операции со старшим битом слова из-за асимметричного переноса-распространения арифметических операций. К счастью, с середины 80-х годов прошлого века это было в большинстве архитектур процессоров. Сопутствующая операция засчитывается, также называемый POPCOUNT, который подсчитывает количество установленных битов в машинном слове, также обычно предоставляется как аппаратный оператор. Более простые битовые операции, такие как установка битов, сброс, проверка и переключение, часто предоставляются как аппаратные операторы, но их легко моделировать, если они не являются - например (SET R0, 1; LSHFT R0, i; OR x, R0) устанавливает бит i. в операнде x.

Некоторые из наиболее полезных и сложных битовых операций, которые должны быть закодированы как идиомы в языке программирования и синтезированы компиляторами, включают:

  • очистить от указанной битовой позиции вверх (оставить нижнюю часть слова)
  • очистить от указанной битовой позиции вниз (оставить верхнюю часть слова)
  • маска от младшего бита вниз (чистое младшее слово)
  • маска от старшего бита вверх (убрать младшее слово)
  • извлечение битового поля
  • вставка битового поля
  • операции разброса / сбора битового поля, которые распределяют непрерывные части битового поля по машинному слову или собирают разрозненные битовые поля в слове в непрерывную часть битового поля (см. последние операторы Intel PEXT / PDEP). Используется криптографией и кодированием видео.
  • инверсия матриц

Некоторые арифметические операции можно свести к более простым операциям и битовым операциям:

  • уменьшить умножение на константу до последовательности сдвиг-сложение

Например, умножение на 9 - это копирование операнда, сдвиг вверх на 3 (умножение на 8) и прибавление к исходному операнду.

  • уменьшить деление на константу до последовательности сдвиг-вычитание

Маскировка [ править ]

Основная статья: маска (вычисление)

Маска - это данные, которые используются для побитовых операций , особенно в битовом поле .

Используя маску, несколько битов в байтах , полубайтах , словах (и т. Д.) Могут быть включены, выключены или инвертированы с включения на выключение (или наоборот) с помощью одной побитовой операции.

См. Также [ править ]

  • Bit Twiddler (значения)
  • Битовая спецификация (значения)
  • Найти первый набор
  • Флаг (вычисление) - бит, представляющий логическое значение
  • Полубайт - единица данных, состоящая из 4 бит или полбайта
  • бит-стук
  • Битовый массив
  • Предикат BIT
  • Наборы инструкций битовых манипуляций - расширения битовых манипуляций для набора инструкций x86 .

Ссылки [ править ]

  1. ^ На большинстве чипов Intel это BSR (реверс битового сканирования), хотя более новые SoC также имеют LZCNT (подсчет ведущих нулей)

Дальнейшее чтение [ править ]

  • Уоррен, Генри С. (2012). Восторг хакера (2-е изд.). Эддисон – Уэсли Профессионал. п. 512. ISBN 978-0321842688.
  • Кнут, Дональд Э. (2009). Искусство программирования, Том 4, Часть 1: Побитовые приемы и методы; Диаграммы двоичных решений (1-е изд.). Эддисон – Уэсли Профессионал. п. 272. ISBN. 978-0321580504.( Черновик Fascicle 1a доступен для загрузки)

Внешние ссылки [ править ]

  • Андерсон, Шон Эрон, изд. (2009-11-26) [1997]. "Bit Twiddling Hacks" . Стэнфордский университет . Архивировано 01 июня 2020 года . Проверено 1 июня 2020 .
  • Трюки с битовыми манипуляциями с полными пояснениями и исходным кодом
  • Руководство Intel по внутренним функциям
  • xchg rax, rax : загадки и хаки для x86_64
  • Агрегированные магические алгоритмы от Университета Кентукки.