Bitwise operation

Uses your system voice; voice and rate in settings.

Snapshot

≈ 14 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor.

Most architectures provide only a few high value bitwise operations, presented as two-operand instructions where the result replaces one of the input operands. On simple low-cost processors, typically, bitwise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition.

While modern processors usually perform addition and multiplication just as fast as bitwise operations due to their longer instruction pipelines and other architectural design choices, bitwise operations do commonly use less power because of the reduced use of resources.

In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor.

Most architectures provide only a few high value bitwise operations, presented as two-operand instructions where the result replaces one of the input operands. On simple low-cost processors, typically, bitwise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition.

While modern processors usually perform addition and multiplication just as fast as bitwise operations due to their longer instruction pipelines and other architectural design choices, bitwise operations do commonly use less power because of the reduced use of resources.

Bitwise operators

In the explanations below, any indication of a bit's position is counted from the right (least significant) side, advancing left. For example, the binary value 0001 (decimal 1) has zeroes at every position but the first (i.e., the rightmost) one.

NOT

The bitwise NOT, or bitwise complement, is a unary operation that performs logical negation on each bit, forming the ones' complement of the given binary value. Bits that are 0 become 1, and those that are 1 become 0. For example: NOT 0111 (decimal 7) The result is equal to the two's complement of the value minus one.

If two's complement arithmetic is used, then NOT x = -x − 1 . For unsigned integers, the bitwise complement of a number is the "mirror reflection" of the number across the half-way point of the unsigned integer's range.

For example, for 8-bit unsigned integers, NOT x = 255 - x , which can be visualized on a graph as a downward line that effectively "flips" an increasing range from 0 to 255, to a decreasing range from 255 to 0. A simple but illustrative example use is to invert a grayscale image where each pixel is stored as an unsigned integer.

AND

integers A bitwise AND is a binary operation that takes two equal-length binary representations and performs the logical AND operation on each pair of the corresponding bits. Thus, if both bits in the compared position are 1, the bit in the resulting binary representation is 1 (1 × 1 = 1); otherwise, the result is 0 (1 × 0 = 0 and 0 × 0 = 0). For example: 0101 (decimal 5) AND 0011 (decimal 3)

OR

A bitwise OR is a binary operation that takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, while otherwise the result is 1. For example: 0101 (decimal 5) OR 0011 (decimal 3)

XOR

A bitwise XOR is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only one of the bits is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same.

For example: 0101 (decimal 5) XOR 0011 (decimal 3) &= \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) \\ &= \left(2^{\lfloor \log_2 x \rfloor + 1} - 1\right) - x \\[10pt] 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) \\[10pt] x \operatorname{OR} y &= \sum_{n=0}^{\lfloor \log_2 x \rfloor} 2^n \Bigg( \left\lfloor \frac{x}{2^n} \right\rfloor \bmod 2 + \left\lfloor \frac{y}{2^n} \right\rfloor \bmod 2 \\ &\qquad\qquad - \left( \left\lfloor \frac{x}{2^n} \right\rfloor \bmod 2 \right) \left( \left\lfloor \frac{y}{2^n} \right\rfloor \bmod 2 \right) \Bigg) \\[10pt] x \operatorname{XOR} y &= \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} There are 16 possible truth functions of two binary variables; this defines a truth table, termed a LUT2 lookup table, a Boolean function order k=2 (2 inputs). Some vendors use the term connective for instructions with a 4-bit field identifying the specific binary connective; some vendors use the term Boolean operation for 16 distinct opcodes.

Here are the bitwise equivalent operations of two bits P and Q: The ternary equivalent is a LUT3 boolean function of order k=3 (three inputs), resulting in a table of 256 operations, and in computing is termed a Bitwise ternary logic instruction.

Bit shifts

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

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, 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

In an arithmetic shift (sticky 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 = 01011100 (decimal +92) A left arithmetic shift by n is equivalent to multiplying by 2 n (provided the value does not overflow), while a right arithmetic shift by n of a two's complement value is equivalent to taking the floor of division by 2 n . If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2 n and rounding toward zero.

Logical shift

In a logical shift (zero fill 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

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

Rotate

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.

Rotate through carry

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. x = y 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++.

Right-shifting a negative value is implementation-defined and not recommended by good coding practice; the result of left-shifting a signed value is undefined if the result cannot be represented in the result type. 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.

Circular shifts

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.

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 > (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 > (32 - n)) : x; where the shift amount is tested to ensure that 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. 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: uint32_t x = ..., n = ...; uint32_t y = (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. GCC 15 introduced the __builtin_stdc_rotate_left and __builtin_stdc_rotate_right intrinsics, but fails to optimize them properly. Intel also provides x86 intrinsics. x := y shl 2;

Applications

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.

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 ← 0 while b ≠ 0 if (b and 1) ≠ 0 c ← c + a left shift a by 1 right shift b by 1 return 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 ← c return b x & y = y & x x & (y & z) = (x & y) & z x & 0xFFFF = x 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 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) 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) x - y = ~(~x + y)

See also

Arithmetic logic unit Bit manipulation Bitboard Bitwise operations in C Double dabble Find first set Karnaugh map Logic gate Logical operator Primitive data type

Online Bitwise Calculator supports Bitwise AND, OR and XOR XORcat, a tool for bitwise-XOR files/streams 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373670512 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

15 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.