Bit Shifts

What are bit shifts?

A bit shift changes the positions of the bits in a number.

There are three types of bit shifts:

1. Logical
2. Arithmetic
3. Circular

The simplest shift type is the logical one. Let’s consider it first.

Any bit shift operation takes two operands. The first one is some integer in which you want to shift some bits. The second operand is the number of bits to move.

Logical bit shift

Here is an algorithm for doing the logical bit shift:

1. Represent the integer in the two’s complement.

2. Discard the required amount of bits on the RHS for the right shift and the LHS for the left shift.

3. Append zeroes on the opposite side of the number. This is LHS for the right shift and RHS for the left shift. The amount of zeroes matches the number of shifted bits.

Logical right shift

To better understand logical bit shifts, let’s consider an example. Imagine that we need to logical right shift the unsigned integer 58 by three bits. The integer occupies one byte of memory.

First, you represent the number in the two’s complement:

58 = 0011 1010

The second step is discarding three bits on the right side of the number this way:

0011 1010 >> 3 = 0011 1

Finally, you add zeros to the left side of the result:

0011 1 = 0000 0111 = 7

The number 7 is the result of the shift.

Logical left shift

Now, let’s left bit shift the number 58 by three bits. We will get the following result:

0011 1010 << 3 = 1 1010 = 1101 0000 = -48

Here, we follow the same algorithm as for the right shift. First, discard the three leftmost bits. Then, we add zeros to the right side of the result.

Arithmetic shift

Now, let’s explore arithmetic shift, the second type of bit shift. When we arithmetic shift to the left side, we follow the logical shift algorithm. The steps are entirely the same.

However, an arithmetic shift to the right side behaves differently from a logical shift. The first two steps are the same. We convert the source integer in the two’s complement and discard the bits on its right side. Then, we append the same amount of bits on the left side. Their value matches the leftmost bit of the original integer. If it equals one, we add ones to the left side. Otherwise, we add zeros. This way, we keep the sign of the integer unchanged after the shifting.

Here is an example. Let’s suppose that we need to do an arithmetic shift of the signed integer -105 to the right by two bits. The integer occupies one byte of memory.

First, we represent the number in the two’s complement like this:

-105 = 1001 0111

Then, we shift it to the right by two bits like this:

1001 0111 >> 2 -> 1001 01 -> 1110 0101

The leftmost bit of the integer equals one in this case. Therefore, we complement the result with ones on the left side.

This way, we get a negative number in the two’s complement representation. We can convert it to decimal like this:

1110 0101 = 1001 1011 = -27

The number -27 is the result of the bit shift operation.

Bash has operators << and >> that are used to perform arithmetic bit shifts. The following commands will check our calculations:

$ echo $((58 >> 3))
7

$ echo $((58 << 3))
464

$ echo $((-105 >> 2))
-27

Run the commands discussed in this lesson in the terminal below.