Bit Rotation

Learn about Bit Rotation

Bit rotation is the process of shifting the digits of a binary number to the left or right. However, unlike a standard shift, where extra bits get discarded and are lost, bit rotation preserves those bits by appending them onto the front or back of the binary string depending on the direction being rotated.

Bit rotation is often used in cryptography as a method to increase the diffusion of a cipher, which is to say increase the difference between different encrypted texts even when the original unencrypted messages are quite alike. Bit rotation is employed widely in modern encryption algorithms, and is a good concept to understand if you are interested in cryptography!

To see how bit rotations work, we can practice rotating the following binary string to the left by 4 bits.

111001100

We can imagine this number as having each index labeled, starting from 0 on the rightmost bit.

\begin{matrix} 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \end{matrix}

A rotation left by 4 bits means every bit moves left 4 places. Index 0 becomes index 4, index 1 becomes index 5, and so on.

\begin{matrix} 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{matrix}

As you surely noticed, if every letter is shifted left 4 digits then the leading 4 digits of the number, in this case 1110, are shifted out of the word. If this were a standard arithmetic shift, these bits would be discarded. However, for this bit rotation they will be appended onto the back of the binary string, to keep the length the same. This means that the digit in index 8 becomes the digit in index 3, the digit from index 7 becomes the digit in index 2, and so on.

\begin{matrix} 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \end{matrix}

We have now found the complete left bit rotation of 4 for the binary string 111001100.

011001110

1) Problem: 101001, right rotation 2

Highlight the rightmost 2 digits. $101001$

Move these two bits to the front of the string to find the answer.

Answer: 011010

2) Problem: 11111111, left rotation 5

This example shows how sometimes it is worth examining the binary string before performing the rotation. In this case, a quick review will show us that the binary string is all 1s, which means that the resulting string will be the same regardless of the rotation.

Answer: 11111111

3) Problem: 101001011, right rotation 10

This example again proves that a little reconnaissance can save you problem-solving time. The binary string provided is 9 digits long, which means a rotation of 10 will bring each bit back to its original position, leaving the resulting string unchanged from the original.

Answer: 101001011