circular shift

In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, 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. A circular shift is a special kind of cyclic permutation, which in turn is a special kind of permutation. Formally, a circular shift is a permutation σ of the n entries in the tuple such that either : \sigma(i)\equiv (i+1) modulo n, for all entries i = 1, ..., n or : \sigma(i)\equiv (i-1) modulo n, for all entries i = 1, ..., n. 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 four-tuple (a, b, c, d) successively gives * (d, a, b, c), * (c, d, a, b), * (b, c, d, a), * (a, b, c, d) (the original four-tuple), and then the sequence repeats; this four-tuple therefore has four distinct circular shifts. However, not all n-tuples have n distinct circular shifts. For instance, the 4-tuple (a, b, a, b) only has 2 distinct circular shifts. The number of distinct circular shifts of an n-tuple is \frac{n}{k} , where is a divisor of , indicating the maximal number of repeats over all subpatterns.…

In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, 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. A circular shift is a special kind of cyclic permutation, which in turn is a special kind of permutation. Formally, a circular shift is a permutation σ of the n entries in the tuple such that either \sigma(i)\equiv (i+1) modulo n, for all entries i = 1, ..., n or \sigma(i)\equiv (i-1) modulo n, for all entries i = 1, ..., n. 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 four-tuple (a, b, c, d) successively gives (d, a, b, c), (c, d, a, b), (b, c, d, a), (a, b, c, d) (the original four-tuple), and then the sequence repeats; this four-tuple therefore has four distinct circular shifts. However, not all n-tuples have n distinct circular shifts. For instance, the 4-tuple (a, b, a, b) only has 2 distinct circular shifts. The number of distinct circular shifts of an n-tuple is \frac{n}{k} , where is a divisor of , indicating the maximal number of repeats over all subpatterns. In computer programming, a bitwise rotation, also known as a circular shift, is a bitwise operation 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 floating-point number's exponent from its significand. 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. /* * Shift operations in C are only defined for shift values which are * not negative and smaller than sizeof(value) * CHAR_BIT. * The mask, used with bitwise-and (&), prevents undefined behaviour * when the shift count is 0 or >= the width of unsigned int. */ include // for uint32_t, to get 32-bit-wide rotates, regardless of the size of int. include // for CHAR_BIT uint32_t rotl32 (uint32_t value, unsigned int count) { const unsigned int mask = CHAR_BIT * sizeof(value) - 1; count &= mask; return (value > (-count & mask)); } uint32_t rotr32 (uint32_t value, unsigned int count) { const unsigned int mask = CHAR_BIT * sizeof(value) - 1; count &= mask; return (value >> count) | (value This safe and compiler-friendly implementation was developed by John Regehr, and further polished by Peter Cordes. A simpler version is often seen when the count is limited to the range of 1 to 31 bits: uint32_t rotl32 (uint32_t value, unsigned int count) { return (value > (32 - count)); } This version is dangerous because if the count is 0 or 32, it asks for a 32-bit shift, which is undefined behaviour in the C language standard. However, it tends to work anyway, because most microprocessors implement value >> 32 as either a 32-bit shift (producing 0) or a 0-bit shift (producing the original value ), and either one produces the correct result in this application. ==Example== If the bit sequence were subjected to a circular shift of one bit position... (see images below) If the bit sequence were subjected to the following operations: ==See also== Barrel shifter Circulant Lyndon word Necklace — an object like a tuple but for which circular shifts are considered equivalent. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1356598930 under CC BY-SA 4.0; modifications have been made.