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

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

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

Побитовые операторы

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

НЕТ

Побитовое НЕ , или побитовое дополнение , является унарным действием , которое выполняет логическое отрицание для каждого бита, формируя дополнение до единиц данного двоичного значения. Биты, которые равны 0, становятся 1, а те, которые равны 1, становятся 0. Например:

НЕ 0 111 (десятичное 7) = 1 000 (десятичное 8)

НЕ 10101011 (десятичное 171) = 01010100 (десятичное 84)

Результат равен дополнению до двух значения минус один. Если используется арифметика дополнения до двух, то NOT x = -x − 1.

Для беззнаковых целых чисел побитовое дополнение числа является «зеркальным отражением» числа посередине диапазона беззнакового целого числа. Например, для 8-битных беззнаковых целых чисел, NOT x = 255 - x, что можно визуализировать на графике как нисходящую линию, которая эффективно «переворачивает» увеличивающийся диапазон от 0 до 255 в уменьшающийся диапазон от 255 до 0. Простой, но наглядный пример использования — инвертирование изображения в оттенках серого, где каждый пиксель хранится как беззнаковое целое число.

И

Побитовое И — это бинарная операция , которая берет два двоичных представления одинаковой длины и выполняет логическую операцию И над каждой парой соответствующих битов. Таким образом, если оба бита в сравниваемой позиции равны 1, бит в полученном двоичном представлении равен 1 (1 × 1 = 1); в противном случае результат равен 0 (1 × 0 = 0 и 0 × 0 = 0). Например:

 010 1 (десятичное 5)И 001 1 (десятичное 3) = 000 1 (десятичная 1)

Операция может использоваться для определения того, установлен ли конкретный бит (1) или очищен (0). Например, если задан битовый шаблон 0011 (десятичная 3), чтобы определить, установлен ли второй бит, мы используем побитовое И с битовым шаблоном, содержащим 1 только во втором бите:

 00 1 1 (десятичное 3)И 00 1 0 (десятичное 2) = 00 1 0 (десятичное 2)

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

Побитовое И может использоваться для очистки выбранных битов (или флагов ) регистра, в котором каждый бит представляет отдельное логическое состояние . Этот метод является эффективным способом хранения ряда логических значений с использованием как можно меньшего объема памяти.

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

 0 1 10 (десятичное 6)И 1 0 11 (десятичное 11) = 0 0 10 (десятичное 2)

Благодаря этому свойству становится легко проверить четность двоичного числа, проверив значение младшего бита. Используя пример выше:

 0110 (десятичное 6)И 0001 (десятичное 1) = 0000 (десятичный 0)

Поскольку 6 И 1 равно нулю, 6 делится на два и, следовательно, четное число.

ИЛИ

Побитовое ИЛИ — это бинарная операция , которая берет два битовых шаблона одинаковой длины и выполняет логическую операцию инклюзивного ИЛИ для каждой пары соответствующих битов. Результат в каждой позиции равен 0, если оба бита равны 0, в противном случае результат равен 1. Например:

 0 101 (десятичное 5)ИЛИ 0 011 (десятичное 3) = 0 111 (десятичное 7)

Побитовое ИЛИ может использоваться для установки в 1 выбранных битов регистра, описанного выше. Например, четвертый бит 0010 (десятичное 2) может быть установлен путем выполнения побитового ИЛИ с шаблоном, в котором установлен только четвертый бит:

 0 0 1 0 (десятичное 2)ИЛИ 1 0 0 0 (десятичное 8) = 1 0 1 0 (десятичное 10)

XOR

Побитовое XOR — это бинарная операция , которая берет два битовых шаблона одинаковой длины и выполняет логическую операцию исключающего ИЛИ для каждой пары соответствующих битов. Результат в каждой позиции равен 1, если только один из битов равен 1, но будет равен 0, если оба равны 0 или оба равны 1. При этом мы выполняем сравнение двух бит, принимая значение 1, если два бита различны, и 0, если они одинаковы. Например:

 0 10 1 (десятичное 5)XOR 0 01 1 (десятичное 3) = 0 11 0 (десятичное 6)

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

 0 0 1 0 (десятичное 2)XOR 1 0 1 0 (десятичное 10) = 1 0 0 0 (десятичное 8)

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

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

Если набор битовых строк фиксированной длины n (т.е. машинных слов ) рассматривать как n -мерное векторное пространство над полем , то сложение векторов соответствует побитовой операции XOR. ${\bf {F}}_{2}^{n}$ ${\bf {F}}_{2}$

Математические эквиваленты

Предполагая , что для $x\geq y$ неотрицательных целых чисел побитовые операции можно записать следующим образом:

{\begin{aligned}\operatorname {NOT} x&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+1\right){\bmod {2}}\right]=2^{\left\lfloor \log _{2}(x)\right\rfloor +1}-1-x\\x\operatorname {AND} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\\x\operatorname {OR} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)-\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right)\\x\operatorname {XOR} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right]{\bmod {2}}\right)=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor +\left\lfloor {\frac {y}{2^{n}}}\right\rfloor \right){\bmod {2}}\right]\end{aligned}}

Таблица истинности для всех бинарных логических операторов

Существует 16 возможных функций истинности двух двоичных переменных ; это определяет таблицу истинности .

Вот побитовые эквивалентные операции двух битов P и Q:

Сдвиги битов

Битовые сдвиги иногда считаются побитовыми операциями, поскольку они обрабатывают значение как ряд битов, а не как численное количество. В этих операциях цифры перемещаются или сдвигаются влево или вправо. Регистры в процессоре компьютера имеют фиксированную ширину, поэтому некоторые биты будут «сдвинуты» из регистра на одном конце, в то время как такое же количество бит будет «сдвинуто» с другого конца; различия между операторами битового сдвига заключаются в том, как они определяют значения сдвинутых битов.

Адресация битов

Если ширина регистра (часто 32 или даже 64) больше, чем число бит (обычно 8) наименьшей адресуемой единицы, часто называемой байтом, операции сдвига вызывают схему адресации от байтов к битам. Таким образом, ориентации «влево» и «вправо» берутся из стандартной записи чисел в позиционной нотации , так что сдвиг влево увеличивает, а сдвиг вправо уменьшает значение числа ― если левые цифры считываются первыми, это составляет ориентацию big-endian . Игнорируя граничные эффекты на обоих концах регистра, арифметические и логические операции сдвига ведут себя одинаково, и сдвиг на 8 позиций бит переносит битовую комбинацию на 1 позицию байта следующим образом:

Арифметический сдвиг

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

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

 00010111 (десятичное +23) СДВИГ ВЛЕВО= 0010111 0 (десятичное +46)

 10010111 (десятичное -105) СДВИГ ВПРАВО= 1 1001011 (десятичное -53)

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

 00010111 (десятичное +23) СДВИГ-ВЛЕВО-НА-ДВА= 010111 00 (десятичное +92)

Левый арифметический сдвиг на n эквивалентен умножению на 2 ⁿ (при условии, что значение не переполняется ), тогда как правый арифметический сдвиг на n значения дополнения до двух эквивалентен взятию нижнего предела деления на 2 ⁿ . Если двоичное число рассматривается как дополнение до единиц , то та же операция сдвига вправо приводит к делению на 2 ⁿ и округлению до нуля .

Логический сдвиг

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

Однако, поскольку логический сдвиг вправо вставляет биты со значением 0 в самый старший бит, а не копирует знаковый бит, он идеально подходит для беззнаковых двоичных чисел, в то время как арифметический сдвиг вправо идеально подходит для двоичных чисел со знаком в дополнительном коде .

Круговой сдвиг

Другой формой сдвига является циклический сдвиг , побитовое вращение или битовый поворот .

Повернуть

В этой операции, иногда называемой вращением без переноса , биты «вращаются», как если бы левый и правый концы регистра были соединены. Значение, которое сдвигается вправо во время сдвига влево, — это любое значение, которое было сдвинуто влево, и наоборот для операции сдвига вправо. Это полезно, если необходимо сохранить все существующие биты, и часто используется в цифровой криптографии . ^{[ требуется пояснение ]}

Поворот через перенос

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

Одиночный поворот через перенос может имитировать логический или арифметический сдвиг на одну позицию, заранее установив флаг переноса. Например, если флаг переноса содержит 0, то x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEэто логический сдвиг вправо, а если флаг переноса содержит копию знакового бита, то x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEэто арифметический сдвиг вправо. По этой причине некоторые микроконтроллеры, такие как младшие PIC, просто имеют поворот и поворот через перенос и не беспокоятся об арифметических или логических инструкциях сдвига.

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

На языках высокого уровня

В семье языков C

В языках C и C++ логические операторы сдвига — это " <<" для сдвига влево и " >>" для сдвига вправо. Количество позиций для сдвига указывается как второй аргумент оператора. Например,

х = у << 2 ;

присваивает xрезультат сдвига yвлево на два бита, что эквивалентно умножению на четыре.

Сдвиги могут привести к поведению, определяемому реализацией, или неопределенному поведению , поэтому при их использовании следует соблюдать осторожность. Результат сдвига на число бит, большее или равное размеру слова, является неопределенным поведением в C и C++. ^[2]^[3] Сдвиг вправо отрицательного значения определяется реализацией и не рекомендуется хорошей практикой кодирования; ^[4] результат сдвига влево знакового значения является неопределенным, если результат не может быть представлен в типе результата. ^[2]

В C# сдвиг вправо является арифметическим сдвигом, когда первый операнд — int или long. Если первый операнд имеет тип uint или ulong, сдвиг вправо является логическим сдвигом. ^[5]

Круговые смены

В семействе языков C отсутствует оператор поворота (хотя C++20 предоставляет std::rotlи std::rotr), но его можно синтезировать из операторов сдвига. Необходимо позаботиться о том, чтобы оператор был правильно сформирован, чтобы избежать неопределенного поведения и атак по времени в программном обеспечении с требованиями безопасности. ^[6] Например, наивная реализация, которая выполняет левый поворот 32-битного беззнакового значения xпо nпозициям, просто

uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( х >> ( 32 - n ));

Однако сдвиг по 0битам приводит к неопределенному поведению в правом выражении , (x >> (32 - n))поскольку 32 - 0это 32, и 32находится вне диапазона 0–31 включительно. Вторая попытка может привести к

uint32_t x = ..., n = ...; uint32_t y = n ? ( x << n ) | ( x >> ( 32 - n )) : x ;

где проверяется величина сдвига, чтобы убедиться, что она не вносит неопределенное поведение. Однако ветвь добавляет дополнительный путь кода и предоставляет возможность для анализа времени и атаки, что часто неприемлемо в программном обеспечении с высокой степенью целостности. ^[6] Кроме того, код компилируется в несколько машинных инструкций, что часто менее эффективно, чем собственные инструкции процессора.

Чтобы избежать неопределенного поведения и ветвлений в GCC и Clang , рекомендуется следующее. Шаблон распознается многими компиляторами, и компилятор выдаст одну инструкцию поворота: ^[7]^[8]^[9]

uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( х >> ( - n & 31 ));

Существуют также встроенные функции , специфичные для компилятора, реализующие циклические сдвиги , например _rotl8, _rotl16, _rotr8, _rotr16 в Microsoft Visual C++ . Clang предоставляет некоторые встроенные функции поворота для совместимости с Microsoft, которая страдает от проблем, описанных выше. ^[9] GCC не предлагает встроенные функции поворота. Intel также предоставляет встроенные функции x86.

Ява

В Java все целочисленные типы являются знаковыми, поэтому операторы " <<" и " >>" выполняют арифметические сдвиги. Java добавляет оператор " >>>" для выполнения логических сдвигов вправо, но поскольку логические и арифметические операции сдвига влево идентичны для знаковых целых чисел, в Java нет <<<оператора " ".

Более подробная информация об операторах сдвига Java: ^[10]

Операторы <<(сдвиг влево), >>(знаковый сдвиг вправо) и >>>(беззнаковый сдвиг вправо) называются операторами сдвига .
Тип выражения сдвига — это повышенный тип левого операнда. Например, aByte >>> 2эквивалентно .((int) aByte) >>> 2
Если типом левого операнда является int, то в качестве расстояния сдвига используются только пять младших бит правого операнда. Это как если бы правый операнд подвергался побитовому логическому оператору И & со значением маски 0x1f (0b11111). ^[11] Фактически используемое расстояние сдвига, таким образом, всегда находится в диапазоне от 0 до 31 включительно.
Если тип левого операнда повышен до длинного, то в качестве расстояния сдвига используются только шесть младших бит правого операнда. Это как если бы правый операнд подвергался побитовому логическому оператору И & со значением маски 0x3f (0b111111). ^[11] Фактически используемое расстояние сдвига, таким образом, всегда находится в диапазоне от 0 до 63 включительно.
Значение n >>> sравно n сдвинутым вправо на s битовых позиций с нулевым расширением.
В битовых операциях и операциях сдвига тип byteнеявно преобразуется в int. Если значение байта отрицательное, старший бит равен единице, затем единицы используются для заполнения дополнительных байтов в int. Таким образом, результатом будет .byte b1 = -5; int i = b1 | 0x0200;i == -5

JavaScript

JavaScript использует побитовые операции для оценки каждого из двух или более единиц как 1 или 0. ^[12]

Паскаль

В Pascal, а также во всех его диалектах (таких как Object Pascal и Standard Pascal ), логическими операторами сдвига влево и вправо являются " shl" и " shr" соответственно. Даже для знаковых целых чисел shrведет себя как логический сдвиг и не копирует знаковый бит. Количество позиций для сдвига указывается как второй аргумент. Например, следующее присваивает x результат сдвига y влево на два бита:

x := y shl 2 ;

Другой

popcount , используется в криптографии
подсчет начальных нулей

Приложения

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

Хотя машины часто имеют эффективные встроенные инструкции для выполнения арифметических и логических операций, все эти операции можно выполнить, комбинируя побитовые операторы и проверку на ноль различными способами. ^[13] Например, вот псевдокодовая реализация древнеегипетского умножения, показывающая, как умножить два произвольных целых числа aи b( aбольше, чем b), используя только сдвиги битов и сложение:

c ← 0 пока b ≠ 0 если ( b и 1 ) ≠ 0 c ← c + a сдвиг влево a на 1 сдвиг вправо b на 1 возврат c

Другим примером является реализация сложения на псевдокоде, показывающая, как вычислить сумму двух целых чисел aс bиспользованием побитовых операторов и проверки на ноль:

в то время как a ≠ 0 c ← b и a b ← b xor a сдвиг c влево на 1 a ← c возврат b

Булева алгебра

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

И

x & y = y & x
x & (y & z) = (x & y) & z
x & 0xFFFF = x^[14]
x & 0 = 0

x & x = x

ИЛИ

x | y = y | x
x | (y | z) = (x | y) | z
x | 0 = x
x | 0xFFFF = 0xFFFF
x | x = x

НЕТ

~(~x) = x

XOR

x ^ y = y ^ x
x ^ (y ^ z) = (x ^ y) ^ z
x ^ 0 = x
x ^ y ^ y = x
x ^ x = 0
x ^ 0xFFFF = ~x

Кроме того, XOR можно составить, используя 3 основные операции (И, ИЛИ, НЕ).

a ^ b = (a | b) & (~a | ~b)
a ^ b = (a & ~b) | (~a & b)

Другие

x | (x & y) = x
x & (x | y) = x
~(x | y) = ~x & ~y
~(x & y) = ~x | ~y
x | (y & z) = (x | y) & (x | z)
x & (y | z) = (x & y) | (x & z)
x & (y ^ z) = (x & y) ^ (x & z)
x + y = (x ^ y) + ((x & y) << 1)
x - y = ~(~x + y)

Обратные уравнения и решение уравнений

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

Имеет обратный
- НЕТ
- XOR
- Повернуть влево
- Повернуть вправо
Нет обратного
- И
- ИЛИ
- Сдвиг влево
- Сдвиг вправо

Порядок действий

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

( )
~ -^[15]
* / %
+ -^[16]
<< >>
&
^
|

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

Ссылки

^ "Блог о маломощных конструкциях CMicrotek". CMicrotek . Получено 12 августа 2015 г.
^ ab JTC1/SC22/WG14 N843 "Язык программирования C", раздел 6.5.7
^ "Арифметические операторы - cppreference.com". en.cppreference.com . Получено 2016-07-06 .
^ "INT13-C. Используйте побитовые операторы только для беззнаковых операндов". CERT: Secure Coding Standards . Software Engineering Institute, Carnegie Mellon University . Получено 2015-09-07 .
^ "Оператор (Справочник по C#)". Microsoft . Получено 2013-07-14 .
^ ab "Почти постоянное время вращения, которое не нарушает стандарты?". Stack Exchange Network . Получено 2015-08-12 .
^ "Плохая оптимизация переносимой идиомы поворота". Проект GNU GCC . Получено 11 августа 2015 г.
^ "Круговой поворот, который не нарушает стандарт C/C++?". Форумы разработчиков Intel . Получено 12 августа 2015 г.
^ ab "Константа не распространяется во встроенный ассемблер, приводит к "ограничение 'I' ожидает целочисленное константное выражение"". Проект LLVM . Получено 2015-08-11 .
^ Спецификация языка Java, раздел 15.19. Операторы сдвига
^ ab "Глава 15. Выражения". oracle.com .
^ "JavaScript Bitwise". W3Schools.com .
^ "Синтез арифметических операций с использованием трюков со сдвигом битов". Bisqwit.iki.fi. 2014-02-15 . Получено 2014-03-08 .
^ В этой статье 0xFFFF означает, что все биты в вашем типе данных должны быть установлены в 1. Точное количество бит зависит от ширины типа данных.
^ - здесь отрицание, а не вычитание
^ - здесь вычитание, а не отрицание

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

Онлайн-калькулятор побитовых операций поддерживает побитовые операции И, ИЛИ и исключающее ИЛИ.
XORcat, инструмент для побитового XOR-файлов/потоков
Деление с использованием битовых сдвигов
«Побитовые операции по модулю N» Энрике Зелени, Wolfram Demonstrations Project .
«Сюжеты композиций побитовых операций» Энрике Зелени, Проект демонстраций Вольфрама.