Xtykutl

If I have a string that represents an integer in binary form such as

1101101

and I want to circularly right shift it to obtain

1110110

One way I could think of would be converting the string into an int and use (taken from wikipedia)

// https://stackoverflow.com/a/776550/3770260

template <typename INT>

#if __cplusplus > 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 > 201100L && _wp_force_unsigned_rotate // Apply unsigned check C++ 11 to make sense

    static_assert(std::is_unsigned<INT>::value,

                  "Rotate Left only makes sense for unsigned types");

#endif

    return (val << len) | ((unsigned) val >> (-len & (sizeof(INT) * CHAR_BIT - 1)));

}

However, if the string consists of, say, 10^6 char then this does not work as the integer representation exceeds even the range of __int64.

In that case I could think of a solution by looping over the string

//let str be a char string of length n

char temp = str[n - 1];

for(int i = n - 1; i > 0; i--)

{

    str[i] = str[i - 1];

}

str[0] = temp;

This solution runs in O(n) 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?

EDIT

Both input and output are std::strings

You have to move memory one way or another, so your proposed solution is as fast as it gets.

You might also use standard std::string functions:

str.insert(str.begin(), str[n - 1]);

str.erase(str.end() - 1);

or memmove, or memcpy (I don't actually recommend this, it's for an argument)

char temp = str[n - 1];

memmove(str.data() + 1, str.data(), n - 1);

str[0] = temp;

Note that memmove may look faster, but it's essentially the same thing as your loop. It is moving bytes one by one, it's just encapsulated in a different function. This method might be faster for much larger data blocks, of size 1000 bytes or more, since the CPU is optimized to move large chunks of memory. But you won't be able to measure any difference for 10 or 20 bytes.

Moreover, the compiler will most likely run additional optimizations when it sees your for loop, it realizes that you are moving memory and chooses the best option.

The compiler is also good at dealing with std::string methods. These are common operations and the compiler knows the best way to handle it.