Right shift a binary string efficiently in C++

Question

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

and I want to circularly right shift it to obtain

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

Ever think of using [std::rotate](https://en.cppreference.com/w/cpp/algorithm/rotate)? — PaulMcKenzie, Nov 10 '18 at 00:51
[Use a `std::deque` instead of a `string`](https://en.cppreference.com/w/cpp/container/deque) if you can. `deque` has zounds-fast insert and removal from both ends while still allowing iterating and indexing. — user4581301, Nov 10 '18 at 00:52
Do you need contiguous container ? Else a (circular) string + index should do the job. — Jarod42, Nov 10 '18 at 00:55
If you can afford double the space, you can copy the entire string side by side first...for example, if your string is "abc" then make it "abcabc". Then keep a pointer to the start and just consider the substring of length 3 starting from the pointer as your rotated string. This obviously has some limitations, so I'd need to get more information about the various other requirements you may have, but it is one potential solution if you want to rotate many times. — ComputerNerd, Nov 10 '18 at 01:03
Does it have to be a `std::string`? What are your input and output *format* requirements? Can you create your own data structure for this? — Galik, Nov 10 '18 at 01:09
If output has to be `std::string`, you have to create/fill it, which is `O(N)` anyway.. — Jarod42, Nov 10 '18 at 01:13
Then I don't think you have a choice but to shift the intermediate characters. Aka `std::rotate` as previously suggested. — Galik, Nov 10 '18 at 01:15
@Jarod42 std::string is not immutable, so perhaps your first solution should work (using `std::string` with a variable to keep track of increment (for example, increment = 1 after one right shift operation) and using `mod`) — iambrj, Nov 10 '18 at 01:19
@iambrj But what will you use the rotated string for? Some other entity is going to use this "rotated string" in some way, no? If so it has to figure out what the real string if you're faking the rotation by using indices instead of truly rotating the string. Sounds like it boils down to `O(n)` -- either pay me now or pay me later type of a scenario. — PaulMcKenzie, Nov 10 '18 at 02:05
You could *encode* the position of the shift in the string itself behind a *null terminator* at the end... — Galik, Nov 10 '18 at 03:08

Barmak Shemirani · Accepted Answer · 2018-11-10T07:41:02.490

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.

Right shift a binary string efficiently in C++

EDIT

1 Answers1