CODEWITHSUNDEEP
c++runtimebit-shift
iambrj
iambrj

Reputation: 71

Right shift a binary string efficiently in C++

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

Upvotes: 1

Views: 2958

Answers (1)

Barmak Shemirani
Barmak Shemirani

Reputation: 31599

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.

Upvotes: 2

Related Questions