Cheatsheet: Bitwise Operators
A quick reference for bitwise operators. These operators define the way that computers rearrange bits to perform calculations and represent data. Bitwise operators are supported directly by computer processors to perform calculations and store information in memory.
These operators are the basis for higher level mathematical operations. It is helpful to have an understanding of binary to understand these operations, see here for an introduction. Understanding the basics of bitwise operators will help you understand the way that your computer actually performs computations using collections of bits.
We will look at three types of bitwise operator:
(1) Logical operators
(1) People familiar with basic programming should be comfortable with logical operations (AND, NOT, OR) in their own computer programs. These operations are also relevant to combining bit arrays. (2) Shifts are used to change the position of bits in a bit array (replacing bits on one side of the array). (3) Rotations move bits around an array without discarding them.
Note: we will refer to a bit as “set” - 1, or “clear” - 0.
2. Logical operators
AND: identifies the set bits that are shared between operands.
0010 AND 1110 = 0010
OR: identifies any set bits in either operand.
0010 OR 1110 = 1110
XOR: sets bits only if they are different between operands.
0010 XOR 1110 = 1100
NOT: Also known as the “complement,” reverses the bits in an operand.
NOT 0010 = 1101
Bit shifts rearrange bits by shifting them some number of positions. Shifts remove and replace bits, in this case, we replace bits with zeros.
LEFT SHIFT: Shifts bits left by some number of positions.
Shifting bits left by 1 place:
LEFT SHIFT 1101 BY 1 = 1010
Shifting bits left by 3 places:
LEFT SHIFT 1101 BY 3 = 1000
RIGHT SHIFT: Shifts bits right by some number of positions.
Shifting bits right by 1 place:
RIGHT SHIFT 1101 BY 1 = 0110
Shifting bits right by 3 places:
RIGHT SHIFT 1101 BY 3 = 0001
Rotations are similar to shifts but do not discard bits from the end of an array. They are also called “circular shifts” because they shift bits in a circle from the front to the end of a bit array.
LEFT CIRCULAR SHIFT: Performs a left shift by some number of positions and adds the shifted bits to the end of the array, rather than discarding them.
Rotating bits left by 1 place:
LEFT CIRCULAR SHIFT 1101 BY 1 = 1011
RIGHT CIRCULAR SHIFT: Performs a right shift by some number of positions and adds the shifted bits to the end of the array.
Rotating bits right by 1 place:
RIGHT CIRCULAR SHIFT 1101 BY 1 = 1110
Rotations do not remove and replace information in the same way that shifts do.
For our bitwise operations to work correctly, we need to know which way bits will be processed in our computer. The way that we refer to this is “endianness,” a term that describes which position in a bit array is the starting position. This will be the position where the computer starts writing or reading when it is processing a bit array.
There are two types of endianness: “Big-endian” and “Little-endian.” In “Big-endian” systems, bits are processed starting from the smallest memory address while in “Little-endian” systems, they are processed from the largest memory address. Shifts and rotations will produce different results depending on the endianness of a system.
6. Use for mathematical operations
Why are bitwise operators important? They form the core operations that allow a computer to perform mathematical calculations on bits. To illustrate, we will use binary operators to perform an addition of two integers:
0010 (This is
2 in decimal).
To perform an addition, we perform the following operations and test for the case where one of our operands equals zero:
See the full pseudocode here.
Using our example operands, there is only one iteration needed to perform an addition.
Therefore, we can reduce the required steps to a single
0010 XOR 0001 = 0011
This is the same as
3 in decimal. Using a single operator is a bit of a fluke, a more complex addition would require multiple iterations. Still, recognise how we performed a mathematical operation using a binary operator. The core mathematical operations that your processor performs are constructed this way.
This is a quick reference for the basic bitwise operators. While it is almost certainly unnecessary for most people to understand bitwise operators in depth, it is worth understanding how your computer uses them to represent data and perform computations. Hopefully this helps you develop an intuitive connection between the operations performed on bits at the processor level, and the higher level the computations your computer performs.