Битовые манипуляции

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

Исходный код , выполняющий битовые манипуляции, использует побитовые операции : AND, OR, XOR, NOT и, возможно, другие операции, аналогичные логическим операторам; есть также битовые сдвиги и операции для подсчета единиц и нулей, поиска старшей и младшей единицы или нуля, установки, сброса и проверки битов, извлечения и вставки полей, маскировки и нулевых полей, сбора и распределения битов в и из указанных битовых позиций или полей. . Операторы целочисленной арифметики также могут выполнять битовые операции совместно с другими операторами.

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

Терминология

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

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

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

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

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

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

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

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

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

x         == 0...010...0
x-1       == 0...001...1
x & (x-1) == 0...000...0

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

x         == 0...1...010...0
x-1       == 0...1...001...1
x & (x-1) == 0...1...000...0

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

Операции манипуляции с битами

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

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

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

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

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

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

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

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

Маскировка

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

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

См. также

Битовый массив
Бит-бэндинг
Немного стук
Битовое поле
Набор инструкций битовой манипуляции — расширения битовой манипуляции для набора команд x86 .
предикат BIT
Спецификация бита (значения)
Битовый твиддлер (значения)
Полубайт — единица данных, состоящая из 4 бит или полубайта.
Предикация (компьютерная архитектура) используются битовые «маски». , где в векторных процессорах
Однособытие расстройство

Ссылки

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

Дальнейшее чтение

Уоррен, Генри С. (2013). Хакерское наслаждение (2-е изд.). Аддисон-Уэсли Профессионал. п. 512. ИСБН 978-0321842688 .
Кнут, Дональд Э. (2009). Искусство компьютерного программирования , том 4, глава 1: Побитовые трюки и методы; Бинарные диаграммы решений (1-е изд.). Аддисон-Уэсли Профессионал. п. 272. ИСБН 978-0321580504 . ( Черновик главы 1a, заархивированный 16 октября 2019 г. на Wayback Machine, доступен для скачивания)

Внешние ссылки

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

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

[1]