Circular shift

<h2 id="implementing-circular-shifts">Implementing circular shifts</h2>
<p>Circular shifts are used often in <a href="/facts/Cryptography/e94PEVau">cryptography</a> in order to permute bit sequences. Unfortunately, many programming languages, including <a href="/facts/C_(programming_language)/Ky2No763">C</a>, do not have operators or standard functions for circular shifting, even though virtually all <a href="/facts/Processor_(computing)/z3wPljrI">processors</a> have <a href="/facts/Bitwise_operation/0gkqnUda">bitwise operation</a> instructions for it (e.g. <a href="/facts/Intel_x86/Kypq5fgu">Intel x86</a> has ROL and ROR).
However, some compilers may provide access to the processor instructions by means of <a href="/facts/Intrinsic_function/r0re5n09">intrinsic functions</a>. In addition, some constructs in standard <a href="/facts/ANSI_C/rPKeEuPm">ANSI C</a> code may be optimized by a compiler to the "rotate" assembly language instruction on CPUs that have such an instruction. Most C compilers recognize the following idiom, and compile it to a single 32-bit rotate instruction.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
/*
 * 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 <stdint.h>  // for uint32_t, to get 32-bit-wide rotates, regardless of the size of int.
#include <limits.h>  // 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) | (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 << (-count & mask));
}

<p>This safe and compiler-friendly implementation was developed by <a href="/facts/John_Regehr/UxM6MIpn">John Regehr</a>,<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> and further polished by Peter Cordes.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p><p>A simpler version is often seen when the count is limited to the range of 1 to 31 bits:
</p>
uint32_t rotl32 (uint32_t value, unsigned int count) {
    return (value << count) | (value >> (32 - count));
}

<p>This version is dangerous because if the count is 0 or 32, it asks for a 32-bit shift, which is <a href="/facts/Undefined_behaviour/awUm2vGd">undefined behaviour</a> 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.
</p>
<h2 id="example">Example</h2>
<p>If the bit sequence 0001 0111 were subjected to a circular shift of one bit position... (see images below)
</p>
<table><tbody><tr><td><ul><li>to the left would yield: 0010 1110</li></ul></td><td><ul><li>to the right would yield: 1000 1011.</li></ul></td></tr></tbody></table>
<p>If the bit sequence 1001 0110 were subjected to the following operations:
</p>
<table><tbody><tr><td>left circular shift by 1 position:</td><td>0010 1101            </td></tr><tr><td>left circular shift by 2 positions:</td><td>0101 1010</td></tr><tr><td>left circular shift by 3 positions:</td><td>1011 0100</td></tr><tr><td>left circular shift by 4 positions:</td><td>0110 1001</td></tr><tr><td>left circular shift by 5 positions:</td><td>1101 0010</td></tr><tr><td>left circular shift by 6 positions:</td><td>1010 0101</td></tr><tr><td>left circular shift by 7 positions:</td><td>0100 1011</td></tr><tr><td>left circular shift by 8 positions:</td><td>1001 0110</td></tr></tbody></table>
<table><tbody><tr><td>right circular shift by 1 position:</td><td>0100 1011</td></tr><tr><td>right circular shift by 2 positions:</td><td>1010 0101</td></tr><tr><td>right circular shift by 3 positions:</td><td>1101 0010</td></tr><tr><td>right circular shift by 4 positions:</td><td>0110 1001</td></tr><tr><td>right circular shift by 5 positions:</td><td>1011 0100</td></tr><tr><td>right circular shift by 6 positions:</td><td>0101 1010</td></tr><tr><td>right circular shift by 7 positions:</td><td>0010 1101</td></tr><tr><td>right circular shift by 8 positions:</td><td>1001 0110</td></tr></tbody></table>

<h2 id="applications">Applications</h2>
<p><a href="/facts/Cyclic_code/LmhezpnR">Cyclic codes</a> are a kind of <a href="/facts/Block_code/QVuqpGga">block code</a> with the property that the circular shift of a codeword will always yield another codeword. This motivates the following general definition: For a <a href="/facts/String_(computer_science)/4ChJu5WS">string</a> <i>s</i> over an alphabet <i>Σ</i>, let <i>shift</i>(<i>s</i>) denote the <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of circular shifts of <i>s</i>,
and for a set <i>L</i> of strings, let <i>shift</i>(<i>L</i>) denote the set of all circular shifts of strings in <i>L</i>. If <i>L</i> is a cyclic code, then <i>shift</i>(<i>L</i>) ⊆ <i>L</i>; this is a necessary condition for <i>L</i> being a <a href="/facts/Cyclic_language/JkK87g6f">cyclic language</a>. The operation <i>shift</i>(<i>L</i>) has been studied in <a href="/facts/Formal_language_theory/crDTyP8q">formal language theory</a>. For instance, if <i>L</i> is a <a href="/facts/Context-free_language/sHDxB5So">context-free language</a>, then <i>shift</i>(<i>L</i>) is again context-free.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> Also, if <i>L</i> is described by a <a href="/facts/Regular_expression/KFL3veHX">regular expression</a> of length <i>n</i>, there is a regular expression of length <a href="/facts/Big_O_notation/weFFjSWg">O</a>(<i>n</i>3) describing <i>shift</i>(<i>L</i>).<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Barrel_shifter/bHuSGHwH">Barrel shifter</a></li>
<li><a href="/facts/Circulant/71ohEKT2">Circulant</a></li>
<li><a href="/facts/Lyndon_word/ckrmLgXQ">Lyndon word</a></li>
<li><a href="/facts/Necklace_(combinatorics)/Qg4AY4Mz">Necklace</a> — an object like a <a href="/facts/Tuple/BI1HIxL8">tuple</a> but for which circular shifts are considered equivalent.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>GCC: "Optimize common rotate constructs" <a href="https://gcc.gnu.org/ml/gcc-patches/2007-11/msg01112.html" target="_blank">https://gcc.gnu.org/ml/gcc-patches/2007-11/msg01112.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"Cleanups in ROTL/ROTR DAG combiner code" mentions that this code supports the "rotate" instruction in the CellSPU <a href="http://www.mail-archive.com/llvm-commits@cs.uiuc.edu/msg17216.html" target="_blank">http://www.mail-archive.com/llvm-commits@cs.uiuc.edu/msg17216.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Safe, Efficient, and Portable Rotate in C/C++ <a href="http://blog.regehr.org/archives/1063" target="_blank">http://blog.regehr.org/archives/1063</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Stackoverflow: Best practices for rotates in C/C++ <a href="https://stackoverflow.com/a/776523/224132" target="_blank">https://stackoverflow.com/a/776523/224132</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Near constant time rotate that does not violate the standards <a href="https://stackoverflow.com/a/31488147/224132" target="_blank">https://stackoverflow.com/a/31488147/224132</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>T. Oshiba, "Closure property of the family of context-free languages under the cyclic shift operation", Transactions of IECE, 55D:119–122, 1972. <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>A. N. Maslov, "Cyclic shift operation for languages", Problems of Information Transmission 9:333–338, 1973. <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Gruber, Hermann; Holzer, Markus (2009). "Language operations with regular expressions of polynomial size". Theoretical Computer Science. 410 (35): 3281–3289. doi:10.1016/j.tcs.2009.04.009. Zbl 1176.68105.. <a href="https://doi.org/10.1016%2Fj.tcs.2009.04.009" target="_blank">https://doi.org/10.1016%2Fj.tcs.2009.04.009</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
</ol>

Circular shift open-in-new

Circular shift