Манипуляция битами
Алгоритмическое изменение данных ниже уровня слова

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

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

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

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

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

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

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

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

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

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

Чтобы определить, является ли число степенью двойки, концептуально мы можем многократно выполнять целочисленное деление на два до тех пор, пока число не будет делиться на 2 без остатка; если единственным оставшимся множителем будет 1, то исходное число было степенью двойки. Используя битовые и логические операторы, есть простое выражение, которое вернет значение true (1) или false (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

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

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

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

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

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

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

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

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

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

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

Маскировка

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

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

Смотрите также

Ссылки

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

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

  • Андерсон, Шон Эрон, ред. (2009-11-26) [1997]. "Bit Twiddling Hacks". Стэнфордский университет . Архивировано из оригинала 2020-06-01 . Получено 2020-06-01 .
  • Трюки с манипуляциями битами с полными объяснениями и исходным кодом
  • Руководство по встроенным функциям Intel
  • xchg rax, rax: x86_64 загадки и хаки
  • Агрегированные магические алгоритмы от Университета Кентукки
Взято с "https://en.wikipedia.org/w/index.php?title=Bit_manipulation&oldid=1180024786"