Bitwise operation
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral 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 side, advancing left. For example, the binary value 0001 has zeroes at every position but the first 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
= 1000
NOT 10101011
= 01010100
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
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 ; otherwise, the result is 0. For example:0101
AND 0011
= 0001
The operation may be used to determine whether a particular bit is set or cleared. For example, given a bit pattern 0011, to determine whether the second bit is set we use a bitwise AND with a bit pattern containing 1 only in the second bit:
0011
AND 0010
= 0010
Because the result 0010 is non-zero, we know the second bit in the original pattern was set. This is often called bit masking.
The bitwise AND may be used to clear selected bits of a register in which each bit represents an individual Boolean state. This technique is an efficient way to store a number of Boolean values using as little memory as possible.
For example, 0110 can be considered a set of four flags numbered from right to left, where the first and fourth flags are clear, and the second and third flags are set. The third flag may be cleared by using a bitwise AND with the pattern that has a zero only in the third bit:
0110
AND 1011
= 0010
Because of this property, it becomes easy to check the parity of a binary number by checking the value of the lowest valued bit. Using the example above:
0110
AND 0001
= 0000
Because 6 AND 1 is zero, 6 is divisible by two and therefore even.
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
OR 0011
= 0111
The bitwise OR may be used to set to 1 the selected bits of the register described above. For example, the fourth bit of 0010 may be set by performing a bitwise OR with the pattern with only the fourth bit set:
00'10
OR 1'000
= 10'1'0
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
XOR 0011
= 0110
The bitwise XOR may be used to invert selected bits in a register. Any bit may be toggled by XORing it with 1. For example, given the bit pattern 0010 the second and fourth bits may be toggled by a bitwise XOR with a bit pattern containing 1 in the second and fourth positions:
00'10
XOR 1'010
= 10'0'0
This technique may be used to manipulate bit patterns representing sets of Boolean states.
Assembly language programmers and optimizing compilers sometimes use XOR as a short-cut to setting the value of a register to zero. Performing XOR on a value against itself always yields zero, and on many architectures this operation requires fewer clock cycles and less memory than loading a zero value and saving it to the register.
If the set of bit strings of fixed length n is thought of as an n-dimensional vector space over the field GF|, then vector addition corresponds to the bitwise XOR.
Mathematical equivalents
Assuming, for non-negative integers, the bitwise operations can be written as follows:Truth table for all binary logical operators
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. 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, 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 is larger than the number of bits 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, 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 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 LEFT-SHIFT
= 00101110
10010111 RIGHT-SHIFT
= 11001011
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, 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 LEFT-SHIFT-BY-TWO
= 01011100
A left arithmetic shift by n is equivalent to multiplying by 2n, while a right arithmetic shift by n of a two's complement value is equivalent to taking the floor of division by 2n. If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2n and rounding toward zero.
Logical shift
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.