Алгоритмическое манипулирование данными на битовом уровне.
Bit manipulation
Манипуляции битами: алгоритмы работы с данными на уровне битов для оптимизации, шифрования, сжатия и управления устройствами. Операции AND, OR, XOR и др.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритмическое изменение данных на уровне ниже слова
Algorithmically modifying data below the word level
Битовая манипуляция — это алгоритмическое изменение битов или других фрагментов данных, размер которых меньше машинного слова. Задачи компьютерного программирования, требующие битовой манипуляции, включают управление устройствами низкого уровня, алгоритмы обнаружения и исправления ошибок, сжатие данных, алгоритмы шифрования и оптимизацию. Для большинства других задач современные языки программирования позволяют программисту работать непосредственно с абстракциями, а не с битами, представляющими эти абстракции. Исходный код, выполняющий битовую манипуляцию, использует побитовые операции: И, ИЛИ, Исключающее ИЛИ, НЕ и, возможно, другие операции, аналогичные логическим операторам; также используются битовые сдвиги и операции для подсчета единиц и нулей, поиска старшего и младшего значащего бита, установки, сброса и проверки битов, извлечения и вставки полей, маскирования и обнуления полей, сбора и распределения битов в указанные позиции или поля. Операторы целочисленной арифметики также могут выполнять побитовые операции в сочетании с другими операторами. В некоторых случаях битовая манипуляция может устранить или уменьшить необходимость перебора структуры данных и обеспечить многократное увеличение скорости, поскольку побитовые операции обрабатываются параллельно.
Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Computer programming tasks that require bit manipulation include low level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions. Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and possibly other operations analogous to the boolean operators; there are also bit shifts and operations to count ones and zeros, find high and low one or zero, set, reset and test bits, extract and insert fields, mask and zero fields, gather and scatter bits to and from specified bit positions or fields. Integer arithmetic operators can also effect bit operations in conjunction with the other operators. Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give manyfold speed ups, as bit manipulations are processed in parallel.
Терминология
Манипуляции с битами, "подстройка" битов, "выбивание" битов и "битовая гимнастика" часто используются как синонимы битовых операций, но иногда обозначают именно хитрые или неочевидные способы и приемы битовых операций, либо утомительные и сложные задачи манипулирования данными на низком уровне при управлении устройствами. Термин "подстройка битов" возник в эпоху раннего вычислительного оборудования, когда операторы компьютеров вносили корректировки, регулируя или "подстраивая" элементы управления компьютера. С развитием языков программирования, программисты стали использовать этот термин для обозначения любых операций с данными, включающих вычисления на уровне отдельных битов.
Bit twiddling, bit fiddling, bit bashing, and bit gymnastics are often used interchangeably with bit manipulation, but sometimes exclusively refer to clever or non obvious ways or uses of bit manipulation, or tedious or challenging low level device control data manipulation tasks. The term bit twiddling dates from early computing hardware, where computer operators would make adjustments by tweaking or twiddling computer controls. As computer programming languages evolved, programmers adopted the term to mean any handling of data that involved bit level computation.
Битовая операция
Битовая операция оперирует одним или несколькими битовыми шаблонами или двоичными числами на уровне их отдельных битов. Это быстрая, примитивная операция, напрямую поддерживаемая центральным процессором (CPU), и используется для манипулирования значениями при сравнениях и вычислениях. На большинстве процессоров большинство битовых операций выполняются за один цикл и существенно быстрее, чем деление, умножение и условные переходы. Хотя современные процессоры обычно выполняют некоторые арифметические и логические операции с той же скоростью, что и битовые, благодаря более длинным конвейерам команд и другим архитектурным решениям, битовые операции, как правило, потребляют меньше энергии из-за меньшего использования ресурсов.
A bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. It is a fast, primitive action directly supported by the central processing unit (CPU), and is used to manipulate values for comparisons and calculations. On most processors, the majority of bitwise operations are single cycle substantially faster than division and multiplication and branches. While modern processors usually perform some arithmetic and logical operations just as fast as bitwise operations due to their longer instruction pipelines and other architectural design choices, bitwise operations do commonly use less power because of the reduced use of resources.
Маскировка
Маска – это данные, используемые для побитовых операций, особенно в битовом поле. С помощью маски можно в одном побитовом действии установить, сбросить или инвертировать несколько бит в байте, полубайте, слове (и т.д.). Более сложные применения маскирования, когда они применяются к операциям условно, называются предикацией.
A mask is data that is used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a Byte, nibble, word (etc.) can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation. More comprehensive applications of masking, when applied conditionally to operations, are termed predication.