Hamish Gibbs' Blog

Hamish Gibbs' Blog

Cheatsheet: Bitwise Operators

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.

1. Overview

We will look at three types of bitwise operator:

(1) Logical operators
(2) Shifts
(3) Rotations

(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

3. Shifts

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

4. Rotations

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.

5. Endianness

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: 0001 and 0010 (This is 1 and 2 in decimal).

To perform an addition, we perform the following operations and test for the case where one of our operands equals zero:

(1) AND

(2) XOR

(3) LEFT SHIFT

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 XOR operation:

0010 XOR 0001 = 0011

This is the same as 1 + 2 = 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.

7. Conclusion

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.

Sources

Photo by Gary Aaronson on Unsplash

en.wikipedia.org/wiki/Bitwise_operation
en.wikipedia.org/wiki/Endianness
stackoverflow.com/questions/7184789/does-bi..
stackoverflow.com/questions/3722004/how-to-..

 
Share this