Circular shift

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (December 2009)

Left circular shift.

Right circular shift.

In combinatorial mathematics, a circular shift is a permutation of the entries in a tuple where the last element becomes the first element and all the other elements are shifted, or where the first element becomes the last element and all the other are shifted. Equivalently, a circular shift is a permutation with only one cycle.

For example, the circular shifts of the triple (a, b, c) are:

• (a, b, c) (identity);
• (c, a, b);
• (b, c, a).

In computer science, a circular shift (or bitwise rotation) is a shift operator that shifts all bits of its operand. Unlike an arithmetic shift, a circular shift does not preserve a number's sign bit or distinguish a number's exponent from its mantissa. Unlike a logical shift, the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence.

Circular shifts are used often in cryptography as part of the permutation of bit sequences. Unfortunately, many programming languages, including C, do not have operators or standard functions for circular shifting, even though several processors have instructions for it (e.g. Intel x86 has ROL and ROR).

Some compilers may provide access to the processor instructions by means of intrinsic functions. If necessary, circular shift functions can be defined (here in C):

/* assumes number of bits in an unsigned int is 32 */
 
unsigned int _rotl(unsigned int value, int shift) {
    shift &= 31;
    return (value << shift) | (value >> (32 - shift));
}
 
unsigned int _rotr(unsigned int value, int shift) {
    shift &= 31;
    return (value >> shift) | (value << (32 - shift));
}

Example

If the bit sequence 0001 0111 were subjected to a circular shift of one bit position... (see images to the right)

• to the left would yield: 0010 1110
• to the right would yield: 1000 1011.

If the bit sequence 0001 0111 were subjected to a circular shift of three bit positions...

• to the left would yield: 1011 1000
• to the right would yield: 1110 0010.

Applications

Cyclic codes are a kind of block code with the property that the circular shift of a codeword will always yield another codeword.