Войти
Манипуляции с битами - это действие алгоритмического манипулирования битами или другие фрагменты данных короче слова. Компьютерное программирование задачи, требующие манипуляции с битами, включают низкоуровневое управление устройством, алгоритмы обнаружения ошибок и исправления, сжатие данных, алгоритмы шифрования и оптимизация. Для большинства других задач современные языки программирования позволяют программисту работать напрямую с абстракциями вместо битов, которые представляют эти абстракции. Исходный код, который выполняет битовые манипуляции, использует побитовые операции : AND, OR, XOR, NOT и, возможно, другие операции, аналогичные логическим операторам; есть также битовые сдвиги и операции для подсчета единиц и нулей, поиска старшего и младшего одного или нуля, установки, сброса и проверки битов, извлечения и вставки полей, полей маски и нуля, сбора и разброса битов на и из указанных битовых позиций или полей. Целочисленные арифметические операторы также могут выполнять битовые операции вместе с другими операторами.
Битовые манипуляции в некоторых случаях могут устранить или уменьшить необходимость в цикле по структуре данных и могут дать многократное ускорение, поскольку битовые манипуляции обрабатываются параллельно.
Перестановка битов и битовая обработка часто используются взаимозаменяемо с битовыми манипуляциями, но иногда относятся исключительно к умным или неочевидным способам или использованию битовых манипуляций или утомительным или сложные задачи манипулирования данными.
Термин «бит-тиддлинг» восходит к раннему вычислительному оборудованию, когда операторы компьютеров вносили коррективы, настраивая или изменяя элементы управления компьютером. По мере развития языков компьютерного программирования, программисты стали использовать этот термин для обозначения любой обработки данных, которая включает вычисления на битовом уровне.
Побитовые операции работают с одним или несколькими битовыми шаблонами или двоичные числа на уровне их индивидуальных битов. Это быстрое примитивное действие, которое напрямую поддерживается центральным процессором (CPU) и используется для управления значениями для сравнений и вычислений.
На большинстве процессоров большинство побитовых операций выполняются за один цикл - значительно быстрее, чем деление, умножение и переходы. В то время как современные процессоры обычно выполняют некоторые арифметические и логические операции так же быстро, как и побитовые, из-за более длинных конвейеров команд и других архитектурных решений архитектуры , побитовые операции обычно потребляют меньше энергии из-за снижение использования ресурсов.
Чтобы определить, является ли число степенью двойки, концептуально мы можем многократно выполнять целочисленное деление на два до тех пор, пока число не перестанет делиться на 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
Если используется встроенный код языка ассемблера, то инструкция, которая считает количество единиц или нулей в операнд может быть доступен; операнд с ровно одним битом «1» является степенью 2. Однако такая инструкция может иметь большую задержку, чем побитовый метод, описанный выше.
Процессоры обычно предоставляют только подмножество полезных битовых операторов. Языки программирования не поддерживают напрямую большинство битовых операций, поэтому для их кодирования необходимо использовать идиомы. Например, язык программирования C предоставляет только побитовое И (), ИЛИ (|), XOR (^) и НЕ (~). Fortran предоставляет операции AND (.and.), OR (.or.), XOR (.neqv.) И EQV (.eqv.). Алгол обеспечивает извлечение и вставку синтаксических битовых полей. Когда языки предоставляют битовые операции, которые напрямую не отображаются на аппаратные инструкции, компиляторы должны синтезировать операцию из доступных операторов.
Особенно полезной битовой операцией является подсчет начальных нулей, используемых для поиска старшего бита машинного слова, хотя у него могут быть разные имена на разных архитектурах. Не существует простой идиомы языка программирования, поэтому она должна предоставляться встроенной функцией компилятора или подпрограммой системной библиотеки. Без этого оператора очень дорого (см. Find first set # CLZ ) выполнять какие-либо операции в отношении старшего бита слова из-за асимметричного переноса-распространения арифметических операций. К счастью, с середины 80-х годов прошлого века это было в большинстве архитектур процессоров. Сопутствующие операции подсчета, также называемые POPCOUNT, которые подсчитывают количество установленных битов в машинном слове, также обычно предоставляются в качестве аппаратного оператора. Более простые битовые операции, такие как установка битов, сброс, проверка и переключение, часто предоставляются как аппаратные операторы, но их легко моделировать, если они не выполняются - например (SET R0, 1; LSHFT R0, i; OR x, R0) устанавливает бит i. в операнде x.
Некоторые из наиболее полезных и сложных битовых операций, которые должны быть закодированы как идиомы в языке программирования и синтезированы компиляторами, включают:
Некоторые арифметические операции могут быть сведены к более простым операциям и битовым операциям:
Умножить на 9 например, скопировать операнд, сдвинуть вверх на 3 (умножить на 8) и добавить к исходному операнду.
Маска - это данные, которые используются для побитовых операций, в частности, в битовом поле.
Используя маску, несколько битов в байте, полубайте, слове (и т. Д.) Могут быть включены, выключены или инвертированы с включения на выключение ( или наоборот) в одной побитовой операции.
