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

Не путать с Бит стучать.

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

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

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

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

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

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

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

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

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

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

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

 bool isPowerOfTwo = (Икс != 0) && ((Икс & (Икс - 1)) == 0);

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

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

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

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

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

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

Смотрите также: Наборы команд обработки битов

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

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

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

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

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

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

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

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

Маскировка

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

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

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

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

использованная литература

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

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

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

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