В компьютерном программировании побитовая операция выполняется над битовой строкой , битовым массивом или двоичным числом (рассматриваемым как битовая строка) на уровне отдельных битов . Это быстрое и простое действие, лежащее в основе арифметических операций более высокого уровня и напрямую поддерживаемое процессором . Большинство побитовых операций представлены в виде инструкций с двумя операндами, результат которых заменяет один из входных операндов.
На простых недорогих процессорах побитовые операции обычно выполняются существенно быстрее, чем деление, в несколько раз быстрее, чем умножение, а иногда и значительно быстрее, чем сложение. Хотя современные процессоры обычно выполняют сложение и умножение так же быстро, как и побитовые операции, из-за более длинных конвейеров команд и других вариантов архитектуры , побитовые операции обычно потребляют меньше энергии из-за меньшего использования ресурсов. [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)
Побитовое исключающее ИЛИ — это двоичная операция , которая принимает два битовых шаблона одинаковой длины и выполняет логическую операцию исключающего ИЛИ для каждой пары соответствующих битов. Результат в каждой позиции равен 1, если только один из битов равен 1, но будет равен 0, если оба равны 0 или оба равны 1. При этом мы выполняем сравнение двух битов, получая 1, если два бита различны, и 0. если они одинаковы. Например:
0 10 1 (десятичное 5)Исключающее ИЛИ 0 01 1 (десятичное 3) = 0 11 0 (десятичное 6)
Побитовое исключающее ИЛИ может использоваться для инвертирования выбранных битов в регистре (также называемое переключением или переключением). Любой бит можно переключить с помощью операции XOR с 1. Например, учитывая битовый шаблон 0010 (десятичное 2), второй и четвертый биты могут быть переключены с помощью побитового исключающего ИЛИ с битовым шаблоном, содержащим 1 во второй и четвертой позициях:
0 0 1 0 (десятичное 2)Исключающее ИЛИ 1 0 1 0 (десятичное 10) = 1 0 0 0 (десятичное 8)
Этот метод можно использовать для управления битовыми шаблонами, представляющими наборы логических состояний.
Программисты на языке ассемблера и оптимизирующие компиляторы иногда используют XOR как ярлык для установки значения регистра в ноль. Выполнение XOR над значением против самого себя всегда дает ноль, и во многих архитектурах эта операция требует меньше тактов и меньше памяти, чем загрузка нулевого значения и сохранение его в регистр.
Если набор битовых строк фиксированной длины n (т.е. машинные слова ) рассматривается как n -мерное векторное пространство над полем , то сложение векторов соответствует побитовому исключающему ИЛИ.
Предполагая , что для неотрицательных целых чисел побитовые операции можно записать следующим образом:
Существует 16 возможных функций истинности двух двоичных переменных ; это определяет таблицу истинности .
Вот побитовые эквивалентные операции двух битов P и Q:
Битовые сдвиги иногда считаются побитовыми операциями, поскольку они рассматривают значение как последовательность битов, а не как числовую величину. В этих операциях цифры перемещаются или смещаются влево или вправо. Регистры в компьютерном процессоре имеют фиксированную ширину, поэтому некоторые биты будут «сдвинуты» из регистра на одном конце, в то время как такое же количество бит «сдвинуто» с другого конца; различия между операторами сдвига битов заключаются в том, как они определяют значения сдвинутых битов.
Если ширина регистра (часто 32 или даже 64) больше количества битов (обычно 8) наименьшей адресуемой единицы, часто называемой байтом, операции сдвига вызывают схему адресации от байтов к битам. Таким образом, ориентации «влево» и «вправо» взяты из стандартного написания чисел в разрядной записи , так что сдвиг влево увеличивает, а сдвиг вправо уменьшает значение числа – если сначала читаются левые цифры, это составляет ориентацию с прямым порядком байтов . Не принимая во внимание граничные эффекты на обоих концах регистра, арифметические и логические операции сдвига ведут себя одинаково, а сдвиг на 8-битные позиции переносит битовую комбинацию на 1-байтовую позицию следующим образом:
При арифметическом сдвиге биты, сдвинутые с любого конца, отбрасываются. При арифметическом сдвиге влево нули сдвигаются вправо; при арифметическом сдвиге вправо знаковый бит (старший бит в дополнении до двух) сдвигается влево, таким образом сохраняя знак операнда.
В этом примере используется 8-битный регистр, интерпретируемый как дополнение до двух:
00010111 (десятичное число +23) СДВИГ ВЛЕВО= 0010111 0 (десятичный +46)
10010111 (десятичное число -105) СДВИГ ВПРАВО= 1 1001011 (десятичное -53)
В первом случае самая левая цифра была сдвинута за конец регистра, а новый 0 был сдвинут в самую правую позицию. Во втором случае крайняя правая 1 была смещена (возможно, во флаг переноса ), а новая 1 скопирована в крайнюю левую позицию, сохраняя знак числа. Несколько смен иногда сокращаются до одной смены на некоторое количество цифр. Например:
00010111 (десятичное число +23) СДВИГ ВЛЕВО-НА ДВА= 010111 00 (десятичный +92)
Арифметический сдвиг влево на n эквивалентен умножению на 2 n (при условии, что значение не переполняется ), тогда как арифметический сдвиг вправо на n значения дополнения до двух эквивалентен взятию нижнего предела деления на 2 n . Если двоичное число рассматривается как дополнение до единиц , то та же операция сдвига вправо приводит к делению на 2 n и округлению в сторону нуля .
При логическом сдвиге нули сдвигаются, чтобы заменить отброшенные биты. Следовательно, логический и арифметический сдвиг влево совершенно одинаковы.
Однако, поскольку логический сдвиг вправо вставляет 0 битов в самый старший бит вместо копирования знакового бита, он идеально подходит для беззнаковых двоичных чисел, в то время как арифметический сдвиг вправо идеально подходит для двоичных чисел со знаком , дополненных до двух .
Другой формой сдвига является круговой сдвиг , побитовое вращение или побитовое вращение .
В этой операции, иногда называемой ротацией без переноса , биты «вращаются», как если бы левый и правый концы регистра были соединены. Значение, которое смещается вправо во время сдвига влево, — это любое значение, которое было сдвинуто влево, и наоборот для операции сдвига вправо. Это полезно, если необходимо сохранить все существующие биты, и часто используется в цифровой криптографии . [ нужны разъяснения ]
Поворот посредством переноса — это вариант операции поворота, при котором сдвигаемый бит (на любом конце) представляет собой старое значение флага переноса, а сдвигаемый бит (на другом конце) становится новым значением флага переноса. флаг переноса.
Один поворот посредством переноса может имитировать логический или арифметический сдвиг на одну позицию, предварительно установив флаг переноса. Например, если флаг переноса содержит 0, то x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEэто логический сдвиг вправо, а если флаг переноса содержит копию знакового бита, то x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEэто арифметический сдвиг вправо. По этой причине некоторые микроконтроллеры, такие как PIC нижнего уровня, просто выполняют вращение и вращение посредством переноса и не беспокоятся об арифметических или логических инструкциях сдвига.
Ротация посредством переноса особенно полезна при выполнении сдвигов чисел, превышающих собственный размер слова процессора , поскольку, если большое число хранится в двух регистрах, бит, сдвинутый с одного конца первого регистра, должен войти в другой конец. второй. При ротационном переносе этот бит «сохраняется» во флаге переноса во время первой смены и готов к смещению во время второй смены без какой-либо дополнительной подготовки.
В языках C и C++ логическими операторами сдвига являются « <<» для сдвига влево и « >>» для сдвига вправо. Количество мест для сдвига задается в качестве второго аргумента оператора. Например,
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b873908a8c81ef7d63805b77756dbcf70a03b39c)
х = у << 2 ; присваивает xрезультат сдвига yвлево на два бита, что эквивалентно умножению на четыре.
Сдвиги могут привести к поведению, определяемому реализацией, или к неопределенному поведению , поэтому при их использовании необходимо соблюдать осторожность. Результатом сдвига на количество битов, большее или равное размеру слова, является неопределенное поведение в C и C++. [2] [3] Сдвиг вправо отрицательного значения определяется реализацией и не рекомендуется хорошей практикой кодирования; [4] результат сдвига влево знакового значения не определен, если результат не может быть представлен в типе результата. [2]
В C# сдвиг вправо — это арифметический сдвиг, когда первый операнд имеет значение int или long. Если первый операнд имеет тип uint или ulong, сдвиг вправо является логическим сдвигом. [5]
В языках семейства C отсутствует оператор поворота (хотя в C++20 предусмотрены std::rotlи std::rotr), но его можно синтезировать из операторов сдвига. Необходимо позаботиться о том, чтобы оператор был правильно сформирован, чтобы избежать атак на неопределенное поведение и время в программном обеспечении с требованиями безопасности. [6] Например, простая реализация, которая поворачивает влево 32-битное беззнаковое значение по позициям, простоxn
uint32_t x = ..., n = ...; uint32_t y = ( x << n ) | ( х >> ( 32 - n )); Однако сдвиг по 0битам приводит к неопределенному поведению в правом выражении , (x >> (32 - n))поскольку 32 - 0is и находится за пределами диапазона 0–31 включительно. Вторая попытка может привести к3232
uint32_t x = ..., n = ...; uint32_t y = n ? ( Икс << п ) | ( Икс >> ( 32 - п )) : Икс ; где величина сдвига проверяется, чтобы убедиться, что она не приводит к неопределенному поведению. Однако эта ветвь добавляет дополнительный путь кода и предоставляет возможность временного анализа и атаки, что часто неприемлемо в программном обеспечении с высокой степенью целостности. [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) >>> 2n >>> sn сдвинутым вправо s битовым позициям с нулевым расширением.byteнеявно преобразуется в int. Если значение байта отрицательное, старший бит равен единице, тогда единицы используются для заполнения дополнительных байтов в int. Так что это приведет к .byte b1 = -5; int i = b1 | 0x0200;i == -5JavaScript использует побитовые операции для оценки каждой из двух или более единиц места в 1 или 0. [12]
В Паскале, а также во всех его диалектах (таких как Object Pascal и Standard Pascal ), логическими операторами сдвига влево и вправо являются " shl" и " shr" соответственно. Даже для целых чисел со знаком shrведет себя как логический сдвиг и не копирует бит знака. В качестве второго аргумента указывается количество мест для сдвига. Например, следующая команда присваивает x результат сдвига y влево на два бита:
х := у шл 2 ; Побитовые операции особенно необходимы в программировании нижнего уровня, таком как драйверы устройств, низкоуровневая графика, сборка пакетов протоколов связи и декодирование.
Хотя машины часто имеют эффективные встроенные инструкции для выполнения арифметических и логических операций, все эти операции могут быть выполнены путем комбинирования побитовых операторов и проверки нуля различными способами. [13] Например, вот реализация древнеегипетского умножения в псевдокоде , показывающая, как умножать два произвольных целых числа и ( больше ), используя только битовые сдвиги и сложение:abab
c ← 0 , пока b ≠ 0 , если ( b и 1 ) ≠ 0 c ← c + сдвиг влево a на 1 сдвиг вправо b на 1 возврат c Другой пример — реализация сложения в псевдокоде, показывающая, как вычислить сумму двух целых чисел aс bиспользованием побитовых операторов и проверки нуля:
в то время как a ≠ 0 c ← b и a b ← b xили сдвиг влево c на 1 a ← c вернуть b Иногда полезно упростить сложные выражения, состоящие из побитовых операций, например при написании компиляторов. Цель компилятора — преобразовать язык программирования высокого уровня в максимально эффективный машинный код . Булева алгебра используется для упрощения сложных поразрядных выражений.
x & y = y & xx & (y & z) = (x & y) & zx & 0xFFFF = x[14]x & 0 = 0x & x = xx | y = y | xx | (y | z) = (x | y) | zx | 0 = xx | 0xFFFF = 0xFFFFx | x = x~(~x) = xx ^ y = y ^ xx ^ (y ^ z) = (x ^ y) ^ zx ^ 0 = xx ^ y ^ y = xx ^ x = 0x ^ 0xFFFF = ~xКроме того, XOR может быть составлен с использованием трех основных операций (И, ИЛИ, НЕ).
a ^ b = (a | b) & (~a | ~b)a ^ b = (a & ~b) | (~a & b)x | (x & y) = xx & (x | y) = x~(x | y) = ~x & ~y~(x & y) = ~x | ~yx | (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)Решить переменные в булевой алгебре может быть сложно, потому что в отличие от обычной алгебры некоторые операции не имеют обратных. При выполнении операций без обратных операций некоторые исходные биты данных теряются, и эту недостающую информацию невозможно восстановить.
Операции, находящиеся вверху этого списка, выполняются первыми. Более полный список смотрите в основной статье.
( )~ -[15]* / %+ -[16]<< >>&^|