时间戳

首页 > 解决方案 > 在 C++ 中有效地右移二进制字符串

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

问题描述

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

1101101

我想循环右移它以获得

1110110

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

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

但是，如果字符串由 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;

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

编辑

输入和输出都是std::strings

标签： c++runtimebit-shift

解决方案

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

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

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

或memmove, 或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方法。这些是常见的操作，编译器知道处理它的最佳方法。

推荐阅读