In combinatorial

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

 mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a circular shift is the operation of rearranging the entries in a tuple

Tuple

In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...

, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation. Thus, a circular shift is given by the action of a particular permutation

Permutation

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

 σ of the n positions in the tuple, for which modulo n for all i (or modulo n for the inverse operation). This permutation is a (very particular) instance of an n-cycle.

The result of repeatedly applying circular shifts to a given tuple are also called the circular shifts of the tuple.

For example, repeatedly applying circular shifts to the 4-tuple (a, b, a, c) successively gives

• (c, a, b, a),
• (a, c, a, b),
• (b, a, c, a),
• (a, b, a, c) (the original 4-tuple),

and then the sequence repeats; this 4-tuple therefore has 4 circular shifts. However the 4-tuple (a, b, a, b) only has 2 (distinct) circular shifts. In general the number of circular shifts of an n-tuple could be any divisor of n, depending on the entries of the tuple.

In computer programming

Computer programming

Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...

, a circular shift (or bitwise rotation) is a shift operator

Shift operator

In mathematics, and in particular functional analysis, the shift operator or translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag operator....

 that shifts all bits of its operand. Unlike an arithmetic shift

Arithmetic shift

In computer programming, an arithmetic shift is a shift operator, sometimes known as a signed shift . For binary numbers it is a bitwise operation that shifts all of the bits of its operand; every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are...

, a circular shift does not preserve a number's sign bit or distinguish a number's exponent from its mantissa

Mantissa

* The mantissa is the significand in a common logarithm or floating-point number.* Metaphorically, it is the part of the self that eludes conscious awareness or self-understanding.* An addition of little importance.Mantissa may also refer to:...

. Unlike a logical shift

Logical shift

In computer science, a logical shift is a bitwise operation that shifts all the bits of its operand. Unlike an arithmetic shift, a logical shift does not preserve a number's sign bit or distinguish a number's exponent from its mantissa; every bit in the operand is simply moved a given number of bit...

, the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence.

Implementing circular shifts

Circular shifts are used often in cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

 in order to permute bit sequences. Unfortunately, many programming languages, including C

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

, do not have operators or standard functions for circular shifting, even though several processors have bitwise operation

Bitwise operation

A bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...

 instructions for it (e.g. Intel x86 has ROL and ROR).

Some compilers may provide access to the processor instructions by means of intrinsic function

Intrinsic function

In compiler theory, an intrinsic function is a function available for use in a given language whose implementation is handled specially by the compiler. Typically, it substitutes a sequence of automatically generated instructions for the original function call, similar to an inline function...

s.

Contrary to popular belief, it is possible to write standard ANSI C code that compiles down to the "rotate" assembly language instruction (on CPUs that have such an instruction).

Most C compilers recognize this idiom:


unsigned int x;
unsigned int y;
/* ... */
y = (x >> shift) | (x << (sizeof(x)*8 - shift));


and compile it to a single 32 bit rotate instruction.

On some systems, this may be "#define"ed as a macro or defined as an inline function called something like "rightrotate32" or "rotr32" or "ror32" in a standard header file like "bitops.h".
Rotates in the other direction may be "#define"ed as a macro or defined as an inline function called something like "leftrotate32" or "rotl32" in the same "bitops.h" header file.

If necessary, circular shift functions can be defined (here in C):


unsigned int _rotl(const unsigned int value, int shift) {
if ((shift &= sizeof(value)*8 - 1)

0)
return value;
return (value << shift) | (value >> (sizeof(value)*8 - shift));
}

unsigned int _rotr(const unsigned int value, int shift) {
if ((shift &= sizeof(value)*8 - 1)

0)
return value;
return (value >> shift) | (value << (sizeof(value)*8 - shift));
}

Example

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

• 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

Block code

In coding theory, block codes refers to the large and important family of error-correcting codes that encode data in blocks.There is a vast number of examples for block codes, many of which have a wide range of practical applications...

with the property that the circular shift of a codeword will always yield another codeword.