title: Right shift a binary string efficiently in C++
body: <p>If I have a string that represents an integer in binary form such as</p>
  <pre><code>1101101
  </code></pre>
  <p>and I want to circularly right shift it to obtain</p>
  <pre><code>1110110
  </code></pre>
  <p>One way I could think of would be converting the string into an <code>int</code> and use (taken from <a href="https://en.wikipedia.org/wiki/Circular_shift#Implementing_circular_shifts" rel="nofollow noreferrer">wikipedia</a>)</p>
  <pre><code>// https://stackoverflow.com/a/776550/3770260
  template &lt;typename INT&gt;
  #if __cplusplus &gt; 201100L // Apply constexpr to C++ 11 to ease optimization
  constexpr
  #endif // See also https://stackoverflow.com/a/7269693/3770260
  INT rol(INT val, size_t len) {
  #if __cplusplus &gt; 201100L &amp;&amp; _wp_force_unsigned_rotate // Apply unsigned check C++ 11 to make sense
      static_assert(std::is_unsigned&lt;INT&gt;::value,
                    &quot;Rotate Left only makes sense for unsigned types&quot;);
  #endif
      return (val &lt;&lt; len) | ((unsigned) val &gt;&gt; (-len &amp; (sizeof(INT) * CHAR_BIT - 1)));
  }
  </code></pre>
  <p>However, if the string consists of, say, 10^6 <code>char</code> then this does not work as the integer representation exceeds even the range of <code>__int64</code>.</p>
  <p>In that case I could think of a solution by looping over the string</p>
  <pre><code>//let str be a char string of length n
  char temp = str[n - 1];
  for(int i = n - 1; i &gt; 0; i--)
  {
      str[i] = str[i - 1];
  }
  str[0] = temp;
  </code></pre>
  <p>This solution runs in <code>O(n)</code> due the loop over the length of the string, n. My question is, is there much more efficient way to implement circular shifting for large binary strings?</p>
  <h3>EDIT</h3>
  <p>Both input and output are <code>std::string</code>s</p>