Bitwise operation
Deep within the digital world, at the very foundation of how computers understand and manipulate information, lie bitwise operations. These fundamental actions work directly on the individual 'bits'—the zeroes and ones—that form all data. Surprisingly efficient and incredibly versatile, mastering bitwise operations unlocks a deeper understanding of how software truly interacts with hardware, offering powerful tools for optimization and specialized tasks. Bitwise operations manipulate data at the lowest level, working directly on individual binary digits (bits). The core bitwise operators (NOT, AND, OR, XOR) and various shift operations each offer unique ways to transform data, often with surprising efficiency. Beyond simple arithmetic, bitwise operations are crucial in low-level programming, cryptography, and complex algorithmic optimizations.
AI Summary
Deep within the digital world, at the very foundation of how computers understand and manipulate information, lie bitwise operations. These fundamental actions work directly on the individual 'bits'—the zeroes and ones—that form all data. Surprisingly efficient and incredibly versatile, mastering bitwise operations unlocks a deeper understanding of how software truly interacts with hardware, offering powerful tools for optimization and specialized tasks.
- Bitwise operations manipulate data at the lowest level, working directly on individual binary digits (bits).
- The core bitwise operators (NOT, AND, OR, XOR) and various shift operations each offer unique ways to transform data, often with surprising efficiency.
- Beyond simple arithmetic, bitwise operations are crucial in low-level programming, cryptography, and complex algorithmic optimizations.
Unlocking the Smallest Data — What are Bitwise Operations?
Imagine a computer's memory not as complex numbers or words, but as vast sequences of tiny electrical switches, each either 'on' (1) or 'off' (0). A bitwise operation is like manipulating these individual switches directly. These operations are among the fastest a processor can perform, often significantly quicker than even basic arithmetic like multiplication or division, especially on older or simpler hardware.
While modern processors, with their complex designs and instruction pipelines, can perform addition and multiplication almost as fast as bitwise operations, bitwise operations still hold an edge in power efficiency. They demand fewer resources, making them vital for embedded systems, high-performance computing, and anywhere power consumption is critical. They are the fundamental language of the digital world.
The Building Blocks: Bitwise NOT
Our journey begins with the simplest operation: NOT. This is a unary operation, meaning it acts on a single input. It performs a logical negation on each bit: if a bit is 0, it becomes 1; if it's 1, it becomes 0. It's like flipping every switch in a sequence.
Input p Result 0 1 1 0
For example, if we have the binary value 0101 (which is decimal 5), applying NOT would turn it into 1010 (decimal 10). When dealing with signed numbers using a system called two's complement, NOT x is actually equivalent to -x - 1. It offers a fascinating 'mirror reflection' for unsigned integers, where NOT x = (maximum value of type) - x. This is perfect for inverting grayscale images, for instance, turning white pixels black and vice-versa.
\text{NOT } x = \overline{x}The Conditional Connection: Bitwise AND
Next, we have AND, a binary operation that compares two bits at corresponding positions. For the result bit to be 1, both input bits must be 1. Otherwise, the result is 0. Think of it as requiring two conditions to be true simultaneously.
Input p Input q Result 0 0 0 0 1 0 1 0 0 1 1 1
If we AND 0110 (decimal 6) with 0011 (decimal 3): 0110 AND 0011 gives 0010. One of its most powerful applications is 'bit masking.' By ANDing a number with a specific 'mask' value, you can check if a particular bit is set, or even clear unwanted bits, much like using masking tape to protect parts of a surface you don't want painted.
x \text{ AND } y = x \wedge yThe Inclusive Option: Bitwise OR
The OR operator is also a binary operation, but it's more forgiving than AND. For the result bit to be 1, at least one of the input bits must be 1. It only produces 0 if both input bits are 0. It's an 'either-or, or both' scenario.
Input p Input q Result 0 0 0 0 1 1 1 0 1 1 1 1
If we OR 0010 (decimal 2) with 0100 (decimal 4): 0010 OR 0100 gives 0110 (decimal 6). This is incredibly useful for 'setting' specific bits in a number or a register. For example, if you have a set of 'flags' (each bit representing a true/false state), you can activate a specific flag by ORing it with a mask that has a 1 in that flag's position.
x \text{ OR } y = x \vee yThe Exclusive Choice: Bitwise XOR
Then there's XOR, or Exclusive OR. This binary operation produces a 1 if the two input bits are different, and a 0 if they are the same. It's like asking: 'Is one, and only one, of these true?'
Input p Input q Result 0 0 0 0 1 1 1 0 1 1 1 0
If we XOR 0010 (decimal 2) with 0110 (decimal 6): 0010 XOR 0110 gives 0100 (decimal 4). XOR is fantastic for 'toggling' or 'flipping' bits — XORing a bit with 1 will invert it, while XORing with 0 leaves it unchanged. A clever trick assembly language programmers use is XORing a value with itself, which always results in zero, often faster than loading a zero from memory.
x \text{ XOR } y = x \oplus yShifting Gears — Manipulating Bit Positions
Beyond manipulating bits in place, we can also move them! Bit shifts literally slide the bits of a binary number to the left or right. As bits move out of one end of the 'register' (a storage unit in the processor), new bits are shifted in from the other side. How those new bits are determined defines the type of shift.
Arithmetic Shifts: Preserving Value
An arithmetic shift treats the bits as a signed numerical value. A left arithmetic shift fills new positions on the right with zeros. Crucially, a left shift by 'n' positions is equivalent to multiplying the number by 2^n, as long as the result doesn't overflow.
A right arithmetic shift preserves the 'sign' of the number. For positive numbers, zeros are shifted in from the left. But for negative numbers (represented in two's complement), the 'sign bit' (the leftmost bit) is copied into the new positions. This makes a right arithmetic shift by 'n' equivalent to integer division by 2^n, preserving the sign.
Logical Shifts: Pure Bit Movement
In contrast, a logical shift doesn't care about the numerical value's sign; it's purely about moving bits. For a left logical shift, zeros are always shifted in from the right, making it identical to an arithmetic left shift. However, a right logical shift always fills new positions with zeros from the left, regardless of the original number's sign.
This distinction is vital: logical right shifts are ideal for manipulating unsigned binary numbers or arbitrary bit patterns, where you simply want to move bits and fill with zeros. Arithmetic right shifts are designed for signed numbers, ensuring that the sign (positive or negative) of the number remains correct after division.
Circular Shifts: Rotating Data
Imagine a conveyor belt where items shifted off one end reappear on the other. That's a circular shift, also known as a bit rotation! Bits that move out of one end of the register are re-inserted at the other end. No bits are lost, making it incredibly useful in cryptography and scenarios where all data bits must be preserved and simply reordered.
A variant, 'rotate through carry,' involves an extra bit: the 'carry flag.' The bit shifted out goes into the carry flag, and the old value of the carry flag is shifted into the number. This is particularly clever for performing shifts on numbers larger than a single processor register, allowing bits to smoothly 'flow' from one register to the next, through the carry flag.
Bitwise Operations in Code
Most programming languages provide operators for bitwise operations. In C and C++, for instance, '<<' performs a left shift, and '>>' performs a right shift. While handy, you must be careful: shifting by too many bits or right-shifting negative numbers can lead to 'undefined behavior' — a programmer's nightmare where the result is unpredictable across different systems.
Java, recognizing the nuances of signed versus unsigned integers, explicitly provides a '>>>' operator for a logical right shift, ensuring zeros are always filled from the left. Since left logical and arithmetic shifts are identical for signed integers, Java doesn't need a separate '<<<' operator.
Real-World Power: Bitwise Applications
Bitwise operations are the unsung heroes of low-level programming. They are indispensable for tasks like writing device drivers, which directly interact with hardware, creating fast graphics routines, or assembling communication protocol packets bit by bit. They're also vital for optimizing algorithms where every clock cycle counts.
For example, did you know you can multiply two numbers using only bit shifts and addition? This technique, known as ancient Egyptian multiplication, repeatedly shifts and adds. You can even implement basic addition using only XOR and AND operations, mimicking how a computer's adder circuit works!
Boolean Algebra: The Logic Behind the Bits
The underlying mathematical framework for bitwise operations is Boolean algebra. This elegant system helps programmers and compilers simplify complex bitwise expressions, turning convoluted code into the most efficient machine instructions possible. It provides rules for how bits interact, allowing for clever optimizations.
However, Boolean algebra reveals an interesting limitation: not all bitwise operations have an 'inverse.' Operations like AND, OR, and standard shifts can sometimes lose information—once a bit is cleared to 0 or shifted out, that original information is gone forever. This is unlike regular arithmetic where, for instance, subtraction reverses addition.
Only operations like NOT, XOR, and circular shifts (rotations) truly have inverses, meaning you can always revert the operation to recover the original data. Understanding which operations preserve information and which don't is crucial when designing robust and reversible algorithms.
Article
Bitwise operation
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
Bitwise operation
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:
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
Bitwise AND of 4-bit 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:
The operation may be used to determine whether a particular bit is set (1) or cleared (0). For example, given a bit pattern 0011 (decimal 3), to determine whether the second bit is set we use a bitwise AND with a bit pattern containing 1 only in the second bit:
Because the result 0010 is non-zero, we know the second bit in the original pattern was set. This is often called bit masking. (By analogy, the use of masking tape covers, or masks, portions that should not be altered or portions that are not of interest. In this case, the 0 values mask the bits that are not of interest.)
The bitwise AND may be used to clear selected bits (or flags) 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 (decimal 6) can be considered a set of four flags numbered from right to left, where the first and fourth flags are clear (0), and the second and third flags are set (1). The third flag may be cleared by using a bitwise AND with the pattern that has a zero only in the third bit:
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:
Because 6 AND 1 is zero, 6 is divisible by two and therefore even.
OR
Bitwise OR of 4-bit integers
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:
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 (decimal 2) may be set by performing a bitwise OR with the pattern with only the fourth bit set:
XOR
Bitwise XOR of 4-bit integers
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:
The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip). Any bit may be toggled by XORing it with 1. For example, given the bit pattern 0010 (decimal 2) the second and fourth bits may be toggled by a bitwise XOR with a bit pattern containing 1 in the second and fourth positions:
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 (i.e. machine words) is thought of as an n-dimensional vector space ${\displaystyle {\bf {F}}{2}^{n}}$ over the field ${\displaystyle {\bf {F}}{2}}$, then vector addition corresponds to the bitwise XOR.
Mathematical equivalents
Assuming ${\displaystyle x\geq y}$, for non-negative integers, the bitwise operations can be written as follows:
${\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)\\&=\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{aligned}}}$
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.k.a. 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:
<table><thead><tr><th>p</th><th>q</th><th></th><th>F0</th><th>NOR1</th><th>Xq2</th><th>¬p3</th><th>↛4</th><th>¬q5</th><th>XOR6</th><th>NAND7</th><th></th><th>AND8</th><th>XNOR9</th><th>q10</th><th>If/then11</th><th>p12</th><th>Then/if13</th><th>OR14</th><th>T15</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr><tr><td>Bitwise equivalents</td><td></td><td>0</td><td>NOT (p OR q)</td><td>(NOT p) AND q</td><td>NOT p</td><td>p AND (NOT q)</td><td>NOT q</td><td>p XOR q</td><td>NOT (p AND q)</td><td></td><td>p AND q</td><td>NOT (p XOR q)</td><td>q</td><td>(NOT p) OR q</td><td>p</td><td>p OR (NOT q)</td><td>p OR q</td><td>1</td></tr></tbody></table>
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
Bitwise operation
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
Left arithmetic shift
Right 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:
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:
A left arithmetic shift by n is equivalent to multiplying by 2n (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 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 (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.
In C family of languages
In C and C++ 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,
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
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
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:
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 does not offer rotate intrinsics. Intel also provides x86 intrinsics.
Java
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.
• 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). 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). 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
JavaScript uses bitwise operations to evaluate each of two or more units place to 1 or 0.
Pascal
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:
Other
Bitwise operation
• popcount, used in cryptography • count leading zeros • Binary-coded decimal
Applications
Bitwise operation
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:
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:
Boolean algebra
Bitwise operation
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
• x & y = y & x • x & (y & z) = (x & y) & z • x & 0xFFFF = x • x & 0 = 0
OR
• x | y = y | x • x | (y | z) = (x | y) | z • x | 0 = x • x | 0xFFFF = 0xFFFF • 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
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
• 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
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
Operations at the top of this list are executed first. See the main article for a more complete list.