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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Побитовые операции»  -  новости  · газеты  · книги  · ученый  · JSTOR ( август 2018 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

На простых недорогих процессорах побитовые операции обычно выполняются значительно быстрее, чем деление, в несколько раз быстрее, чем умножение, а иногда и значительно быстрее, чем сложение. ^{[ требуется пояснение ]} В то время как современные процессоры обычно выполняют сложение и умножение так же быстро, как и побитовые операции, из-за более длинных конвейеров команд и других архитектурных решений, побитовые операции обычно потребляют меньше энергии из-за меньшего использования ресурсов. ^[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 [ править ]

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

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

Побитовое исключающее ИЛИ можно использовать для инвертирования выбранных битов в регистре (также называемого переключением или переключением). Любой бит может быть переключен с помощью 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.${\displaystyle {\bf {F}}_{2}^{n}}$ F 2 {\displaystyle {\bf {F}}_{2}}

Математические эквиваленты [ править ]

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

${\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(\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]{\bmod {2}}\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) наименьшего адресуемого блока (атомарного элемента), часто называемого байтом, операции сдвига вызывают схему адресации битов. Не обращая внимания на граничные эффекты на обоих концах регистра, операции арифметического и логического сдвига ведут себя одинаково, а сдвиг на 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-семейства операторы логического сдвига - " <<" для сдвига влево и " >>" для сдвига вправо. Число мест, на которые нужно сдвинуть, задается вторым аргументом оператора. Например,

х  =  у  <<  2 ;

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

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

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

Круговые сдвиги [ править ]

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

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

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

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

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

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

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

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

Java [ править ]

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

Дополнительные сведения об операторах сдвига в Java: ^[10]

• Операторы <<(сдвиг влево), >>(сдвиг вправо со знаком) и >>>(сдвиг вправо без знака) называются операторами сдвига .
• Тип выражения сдвига - это расширенный тип левого операнда. Например, aByte >>> 2эквивалентно .((int) aByte) >>> 2
• Если повышенный тип левого операнда - int, только пять младших битов правого операнда используются в качестве расстояния сдвига. Это как если бы правый операнд был подвергнут поразрядному логическому оператору AND & со значением маски 0x1f (0b11111). ^[11] Фактически используемое расстояние сдвига всегда находится в диапазоне от 0 до 31 включительно.
• Если расширенный тип левого операнда длинный, то в качестве расстояния сдвига используются только шесть младших битов правого операнда. Это как если бы правый операнд был подвергнут поразрядному логическому оператору AND & со значением маски 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]

Паскаль [ править ]

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

х  : =  у  шл  2 ;

Другое [ править ]

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

Приложения [ править ]

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

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

гр  ←  0 , а  б  ≠  0 ,  если  ( б  и  1 )  ≠  0  C  ←  C  +  левый сдвиг от 1 правого сдвига б от 1 возврата гр           

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

в то время как  в  ≠  0  гр  ←  б  и  в  б  ←  б  исключающих  в  левом  сдвиге  с  помощью  1  в  ←  гр возврат  б

Булева алгебра [ править ]

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

И [ редактировать ]

• 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]
• << >>
• &
• ^
• |

См. Также [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

• Онлайн-побитовый калькулятор поддерживает побитовое И, ИЛИ и XOR
• Деление с использованием битового сдвига
• " Bitwise Operations Mod N " Энрике Зелени, Демонстрационный проект Вольфрама .
• « Сюжеты композиций побитовых операций » Энрике Зелени, Демонстрационный проект Вольфрама.