在 C++ 中有效地右移二进制字符串

Question

如果我有一个以二进制形式表示整数的字符串，例如

我想循环右移得到

我能想到的一种方法是将字符串转换为 int 并使用（取自 wikipedia）

// 
template <typename INT>
#if __cplusplus > 201100L // Apply constexpr to C++ 11 to ease optimization
constexpr
#endif // See also 
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)));
}

但是，如果字符串由 10^6 char 组成，那么这将不起作用，因为整数表示甚至超出了 __int64.

的范围

在那种情况下，我可以通过遍历字符串来想出一个解决方案

//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;

由于对字符串长度 n 的循环，此解决方案在 O(n) 中运行。我的问题是，是否有更有效的方法来实现大型二进制字符串的循环移位？

编辑

输入输出都是std::strings

Answer 1

您必须以一种或另一种方式移动内存，因此您提出的解决方案会尽可能快。

您也可以使用标准 std::string 函数：

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

or memmove, or memcpy (我其实不推荐这个, 是为了争论)

char temp = str[n - 1];
memmove(str.data() + 1, str.data(), n - 1);
str[0] = temp;

请注意，memmove 可能看起来更快，但它与您的循环本质上是一样的。它一个一个地移动字节，它只是封装在一个不同的函数中。对于大小为 1000 字节或更大的大得多的数据块，此方法可能更快，因为 CPU 已针对移动大块内存进行了优化。但是您将无法测量 10 或 20 个字节的任何差异。

此外，当编译器看到您的 for 循环时，它很可能会运行进行额外的优化，它意识到您正在移动内存并选择最佳选项。

编译器也擅长处理std::string方法。这些是常见操作，编译器知道处理它的最佳方式。

在 C++ 中有效地右移二进制字符串

Right shift a binary string efficiently in C++

c++

runtime

bit-shift

编辑