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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Побитовые операции»  -  новости  · газеты  · книги  · ученый  · 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:

Bit shifts[edit]

The bit shifts are sometimes considered bitwise operations, because they treat a value as a series of bits rather than as a numerical quantity. In these operations the digits are moved, or shifted, to the left or right. Registers in a computer processor have a fixed width, so some bits will be "shifted out" of the register at one end, while the same number of bits are "shifted in" from the other end; the differences between bit shift operators lie in how they determine the values of the shifted-in bits.

Bit addressing[edit]

If the width of the register (frequently 32 or even 64) is larger than the number of bits (usually 8) of the smallest addressable unit (atomic element), frequently called byte, the shift operations induce an addressing scheme from the bytes to the bits. Thereby the orientations "left" and "right" are taken from the standard writing of numbers in a place-value notation, such that a left shift increases and a right shift decreases the value of the number ― if the left digits are read first this makes up a big-endian orientation. Disregarding the boundary effects at both ends of the register, arithmetic and logical shift operations behave the same, and a shift by 8 bit positions transports the bit pattern by 1 byte position in the following way:

Arithmetic shift[edit]

In an arithmetic shift, the bits that are shifted out of either end are discarded. In a left arithmetic shift, zeros are shifted in on the right; in a right arithmetic shift, the sign bit (the MSB in two's complement) is shifted in on the left, thus preserving the sign of the operand.

This example uses an 8-bit register, interpreted as two's complement:

 00010111 (decimal +23) LEFT-SHIFT
= 00101110 (decimal +46)

 10010111 (decimal −105) RIGHT-SHIFT
= 11001011 (decimal −53)

In the first case, the leftmost digit was shifted past the end of the register, and a new 0 was shifted into the rightmost position. In the second case, the rightmost 1 was shifted out (perhaps into the carry flag), and a new 1 was copied into the leftmost position, preserving the sign of the number. Multiple shifts are sometimes shortened to a single shift by some number of digits. For example:

 00010111 (decimal +23) LEFT-SHIFT-BY-TWO
= 01011100 (decimal +92)

A left arithmetic shift by n is equivalent to multiplying by 2ⁿ (provided the value does not overflow), while a right arithmetic shift by n of a two's complement value is equivalent to dividing by 2ⁿ and rounding toward negative infinity. If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2ⁿ and rounding toward zero.

Logical shift[edit]

In a logical shift, zeros are shifted in to replace the discarded bits. Therefore, the logical and arithmetic left-shifts are exactly the same.

However, as the logical right-shift inserts value 0 bits into the most significant bit, instead of copying the sign bit, it is ideal for unsigned binary numbers, while the arithmetic right-shift is ideal for signed two's complement binary numbers.

Circular shift[edit]

Another form of shift is the circular shift, bitwise rotation or bit rotation.

Rotate[edit]

In this operation, sometimes called rotate no carry, the bits are "rotated" as if the left and right ends of the register were joined. The value that is shifted into the right during a left-shift is whatever value was shifted out on the left, and vice versa for a right-shift operation. This is useful if it is necessary to retain all the existing bits, and is frequently used in digital cryptography.^{[clarification needed]}

Rotate through carry[edit]

Rotate through carry is a variant of the rotate operation, where the bit that is shifted in (on either end) is the old value of the carry flag, and the bit that is shifted out (on the other end) becomes the new value of the carry flag.

A single rotate through carry can simulate a logical or arithmetic shift of one position by setting up the carry flag beforehand. For example, if the carry flag contains 0, then x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE is a logical right-shift, and if the carry flag contains a copy of the sign bit, then x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE is an arithmetic right-shift. For this reason, some microcontrollers such as low end PICs just have rotate and rotate through carry, and don't bother with arithmetic or logical shift instructions.

Rotate through carry is especially useful when performing shifts on numbers larger than the processor's native word size, because if a large number is stored in two registers, the bit that is shifted off one end of the first register must come in at the other end of the second. With rotate-through-carry, that bit is "saved" in the carry flag during the first shift, ready to shift in during the second shift without any extra preparation.

In high-level languages[edit]

C-family[edit]

In C-family languages, the logical shift operators are "<<" for left shift and ">>" for right shift. The number of places to shift is given as the second argument to the operator. For example,

x = y << 2;

assigns x the result of shifting y to the left by two bits, which is equivalent to a multiplication by four.

Shifts can result in implementation-defined behavior or undefined behavior, so care must be taken when using them. The result of shifting by a bit count greater than or equal to the word's size is undefined behavior in C and C++.^[2][3] Right-shifting a negative value is implementation-defined and not recommended by good coding practice;^[4] the result of left-shifting a signed value is undefined if the result cannot be represented in the result type.^[2]

In C#, the right-shift is an arithmetic shift when the first operand is an int or long. If the first operand is of type uint or ulong, the right-shift is a logical shift.^[5]

Circular shifts[edit]

The C-family of languages lack a rotate operator (although C++20 provides std::rotl and std::rotr), but one can be synthesized from the shift operators. Care must be taken to ensure the statement is well formed to avoid undefined behavior and timing attacks in software with security requirements.^[6] For example, a naive implementation that left rotates a 32-bit unsigned value x by n positions is simply:

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

However, a shift by 0 bits results in undefined behavior in the right hand expression (x >> (32 - n)) because 32 - 0 is 32, and 32 is outside the range [0 - 31] inclusive. A second try might result in:

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

where the shift amount is tested to ensure it does not introduce undefined behavior. However, the branch adds an additional code path and presents an opportunity for timing analysis and attack, which is often not acceptable in high integrity software.^[6] In addition, the code compiles to multiple machine instructions, which is often less efficient than the processor's native instruction.

To avoid the undefined behavior and branches under GCC and Clang, the following is recommended. The pattern is recognized by many compilers, and the compiler will emit a single rotate instruction:^[7][8][9]

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

There are also compiler-specific intrinsics implementing circular shifts, like _rotl8, _rotl16, _rotr8, _rotr16 in Microsoft Visual C++. Clang provides some rotate intrinsics for Microsoft compatibility that suffers the problems above.^[9] GCC does not offer rotate intrinsics. Intel also provides x86 Intrinsics.

Java[edit]

In Java, all integer types are signed, so the "<<" and ">>" operators perform arithmetic shifts. Java adds the operator ">>>" to perform logical right shifts, but since the logical and arithmetic left-shift operations are identical for signed integer, there is no "<<<" operator in Java.

More details of Java shift operators:^[10]

• The operators << (left shift), >> (signed right shift), and >>> (unsigned right shift) are called the shift operators.
• The type of the shift expression is the promoted type of the left-hand operand. For example, aByte >>> 2 is equivalent to ((int) aByte) >>> 2.
• If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x1f (0b11111).^[11] The shift distance actually used is therefore always in the range 0 to 31, inclusive.
• If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x3f (0b111111).^[11] The shift distance actually used is therefore always in the range 0 to 63, inclusive.
• The value of n >>> s is n right-shifted s bit positions with zero-extension.
• In bit and shift operations, the type byte is implicitly converted to int. If the byte value is negative, the highest bit is one, then ones are used to fill up the extra bytes in the int. So byte b1 = -5; int i = b1 | 0x0200; will result in i == -5.

JavaScript[edit]

JavaScript uses bitwise operations to evaluate each of two or more units place to 1 or 0.^[12]

Pascal[edit]

In Pascal, as well as in all its dialects (such as Object Pascal and Standard Pascal), the logical left and right shift operators are "shl" and "shr", respectively. Even for signed integers, shr behaves like a logical shift, and does not copy the sign bit. The number of places to shift is given as the second argument. For example, the following assigns x the result of shifting y to the left by two bits:

x := y shl 2;

Other[edit]

• popcount, used in cryptography
• count leading zeros

Applications[edit]

Bitwise operations are necessary particularly in lower-level programming such as device drivers, low-level graphics, communications protocol packet assembly, and decoding.

Although machines often have efficient built-in instructions for performing arithmetic and logical operations, all these operations can be performed by combining the bitwise operators and zero-testing in various ways.^[13] For example, here is a pseudocode implementation of ancient Egyptian multiplication showing how to multiply two arbitrary integers a and b (a greater than b) using only bitshifts and addition:

c ← 0while b ≠ 0 if (b and 1) ≠ 0 c ← c + a left shift a by 1 right shift b by 1return c

Another example is a pseudocode implementation of addition, showing how to calculate a sum of two integers a and b using bitwise operators and zero-testing:

while a ≠ 0 c ← b and a b ← b xor a left shift c by 1 a ← creturn b

Boolean algebra[edit]

Sometimes it is useful to simplify complex expressions made up of bitwise operations. For example, when writing compilers. The goal of a compiler is to translate a high level programming language into the most efficient machine code possible. Boolean algebra is used to simplify complex bitwise expressions.

AND[edit]

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

• x & x = x

OR[edit]

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

NOT[edit]

• ~(~x) = x

XOR[edit]

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

Additionally, XOR can be composed using the 3 basic operations (AND, OR, NOT)

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

Others[edit]

• 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)

Inverses and solving equations[edit]

It can be hard to solve for variables in boolean algebra, because unlike regular algebra, several operations do not have inverses. Operations without inverses lose some of the original data bits when they are performed, and it is not possible to recover this missing information.

• Has Inverse
  • NOT
  • XOR
  • Rotate Left
  • Rotate Right
• No Inverse
  • AND
  • OR
  • Shift Left
  • Shift Right

Order of operations[edit]

Operations at the top of this list are executed first. See the main article for a more complete list.

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

See also[edit]

References[edit]

External links[edit]

• Online Bitwise Calculator supports Bitwise AND, OR and XOR
• Division using bitshifts
• "Bitwise Operations Mod N" by Enrique Zeleny, Wolfram Demonstrations Project.
• "Plots Of Compositions Of Bitwise Operations" by Enrique Zeleny, The Wolfram Demonstrations Project.