4

I would like to know some examples of application of circular shifts. For example, a right shift on an unsigned integer would result in a division by two. Conversely, a left shift would result in a multiplication by 2. Are there any famous/interesting properties of a circular shift on binary numbers.

Note: The example about the right/left shift is to illustrate an application of that particular operator. I am asking for similar examples for the circular shift operator/function.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Mike G
  • 4,829
  • 11
  • 47
  • 76
  • It is part of the best known way (afaik) to [test for divisibility by a constant](http://gmplib.org/~tege/divcnst-pldi94.pdf) (for constants that are not powers of two). – harold Nov 11 '13 at 06:50
  • @HighPerformanceMark The example of the right/left shift is not for the circular shift. I'm just giving an example of that particular operator. I would like to know of any examples for the circular shift operator/function. – Mike G Nov 11 '13 at 07:44

3 Answers3

6

One surprising place where circular shifts show up is in the Josephus survivor problem. In this slightly morbid problem, n people stand in a circle. The first person kills the second, then the third kills the fourth, etc. This process repeats where one person kills the next until only one person is left. The question is given n people, which person survives?

Amazingly, the answer is given by doing a right circular shift on n by one bit. There's a great proof of this in Graham, Knuth, and Patashnik's book Concrete Mathematics.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
5
  • Convert a 16-bit word between big-endian and little-endian representation: right or left circular shift by 8.
  • Generate random bitset with even number of bits set: t = rand(); result = t XOR cshift(t,1).
  • In-place, stable, and in linear time: move all elements of some array with even positions to the beginning and all elements with odd positions - to the end. One of possible algorithms is described in this paper: "In-Situ, Stable Merging by way of the Perfect Shuffle" (section 7). It generates all possible binary necklaces and uses them as starting points of cycle-leader algorithm where each next position is computed from previous one by circular shift. This application is closely related to multiplication by 2 (mod (2^N - 1)) mentioned in Henrik's answer.
  • Micro-optimization. Suppose you need to unpack four 2-bit words from a single byte. You could do this by shifting each sub-word to rightmost position, then applying AND operation with proper mask. (No need to shift the first sub-word or mask the last one). All this needs 6 CPU instructions. If you circularly shift the byte by 4, two middle sub-words become the first and the last one, and also need only one instruction each. So using circular shift decreases number of needed instructions to 5.
  • Cryptography applications receive significant speed-up when machine instruction set contains rotation instructions. For example, Twofish Cipher uses circular shifts extensively.
Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98
2

A regular left shift is a multiplication by 2 (mod 2^N), where N is the number of bits in your integer type.

A circular left shift is a multiplication by 2 (mod (2^N - 1)). So this can be handy when doing arithmetic mod (2^N-1).

Henrik
  • 23,186
  • 6
  • 42
  • 92