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

редактировать
Компьютерная операция, которая работает со значениями на уровне их отдельных битов

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

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

Содержание

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

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

НЕ

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

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

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

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

И

Поразрядное И 4-битного целых чисел

A Поразрядное И - это двоичная операция, которая принимает два двоичных представления одинаковой длины и выполняет операцию логического И для каждой пары соответствующих битов, что эквивалентно их умножению. Таким образом, если оба бита в сравниваемой позиции равны 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 только во втором бите:

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

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

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

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

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

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

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

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

ИЛИ

Поразрядное ИЛИ 4-битных целых чисел

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

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

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

0010 (десятичное 2) ИЛИ 1000 (десятичное 8) = 1010 (десятичное 10)

XOR

Побитовое XOR 4-битных целых чисел

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

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

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

0010 (десятичное число 2) XOR 1010 (десятичное число 10) = 1000 (десятичное число 8)

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

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

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

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

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

НЕ ⁡ x = ∑ n = 0 ⌊ log 2 ⁡ (x) ⌋ 2 n [(⌊ x 2 n ⌋ mod 2 + 1) mod 2] = 2 ⌊ log 2 ⁡ (x) ⌋ + 1 - 1 - xx И ⁡ y = ∑ n = 0 ⌊ log 2 ⁡ (x) ⌋ 2 n (⌊ x 2 n ⌋ mod 2) (⌊ y 2 n ⌋ mod 2) x OR ⁡ y = ∑ n = 0 ⌊ журнал 2 ⁡ (x) ⌋ 2 n ([(⌊ x 2 n ⌋ mod 2) + (⌊ y 2 n ⌋ mod 2) + (⌊ x 2 n ⌋ mod 2) (⌊ y 2 n ⌋ mod 2)] mod 2) x XOR ⁡ y = ∑ n = 0 ⌊ log 2 ⁡ (x) ⌋ 2 n ([(⌊ x 2 n ⌋ mod 2) + (⌊ y 2 n mod 2)] mod 2) = ∑ n Знак равно 0 ⌊ журнал 2 ⁡ (Икс) ⌋ 2 N [(⌊ Икс 2 N ⌋ + ⌊ Y 2 N ⌋) по модулю 2] {\ Displaystyle {\ begin {align} \ 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} \ le ft (\ 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) = \ сумма _ {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 {align}}}{\ displaystyle {\ begin {align} \ 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 {align}}}

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

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

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

pqF NOR Xq ¬p ¬q XOR NAND AND XNOR q If / then p Тогда / если OR T
110000000011111111
100000111100001111
010011001100110011
000101010101010101
Побитовые. эквиваленты0НЕ. (p OR q)(NOT p). AND qNOT. pp AND. (НЕ q)НЕ. qp XOR qНЕ. (p AND q)p AND qНЕ. (p XOR q)q(НЕ p). OR qpp OR. (НЕ q)p OR q1

Битовые сдвиги

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

Битовая адресация

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

сдвиг влево на 8 позиций увеличивает адрес байта на 1.
  • Порядок с прямым порядком байтов:
сдвиг вправо на 8 позиций уменьшает адрес байта на 1
сдвиг влево на 8 позиций уменьшает адрес байта на 1.
  • Порядок прямого байта:
сдвиг вправо на 8 позиций увеличивает адрес байта на 1

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

Арифметический сдвиг влево Арифметический сдвиг вправо

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

В этом примере используется 8-битный регистр:

00010111 (десятичный +23) LEFT-SHIFT = 0010111 0 (десятичный +46)
10010111 (десятичный -23) ПРАВЫЙ-SHIFT = 1 1001011 (десятичный -11)

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

00010111 (десятичный +23) LEFT-SHIFT-BY-TWO = 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-family

В C-family языках операторы логического сдвига: «<<» для сдвига влево и « >>"для сдвига вправо. Число мест, на которые нужно сдвинуть, задается вторым аргументом оператора. Например,

x = y << 2;

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

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

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

Круговые сдвиги

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

uint32_t x =..., n =...; uint32_t y = (x << n) | (x>>(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;

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

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

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

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

Java

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

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

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

JavaScript

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

Паскаль

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

x: = y shl 2;

Другое

Приложения

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

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

c ← 0, а b ≠ 0 if (b и 1) ≠ 0 c ← c + сдвиг влево a на 1 сдвиг вправо b на 1 return c

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

while a ≠ 0 c ← b и ab ← b xor a сдвиг влево c на 1 a ← c return b

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

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

И

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

OR

  • 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 основных операций (AND, ИЛИ, НЕ)

  • 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
    • Повернуть влево
    • Повернуть вправо
  • Без инверсии
    • И
    • OR
    • Сдвиг влево
    • Сдвиг вправо

Порядок операций

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

  • ()
  • ~ -
  • * /%
  • + -
  • <<>>
  • ^
  • |

См. также

Ссылки

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

Последняя правка сделана 2021-05-12 08:33:12
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте