位旋转（循环移位）

Question

我正在尝试使用C ++编写“位旋转”代码，并希望通过左移来实现。 我不知道如何编写此代码，但是我在维基百科上找到了一小段代码，类似于：

unsigned int rotl(unsigned int value, int shift) {
    return (value << shift) | (value >> (sizeof(value) * CHAR_BIT - shift));
}

然后我尝试让它工作，但这段代码没有给我期望的输出。比如，我有数字unsigned int 12，在二进制中是1100，当我想使用上面的代码进行位旋转时，通过左移位，输出结果是unsigned int 24(11000)，实际结果应该是unsigned int 9，因为如果我进行位旋转(左移位)，第一个MSB位现在必须成为第一个位，所有其他位都必须向左移动一位。

您能帮忙理解问题所在吗？或者说我做错了什么。

谢谢。

- user3721105

---

你的函数是正确的。一个整数有32位，而不是4位。 - chuck1

你对CHAR_BIT的定义是什么？我用8进行测试，输出结果为24。 - michaeltang

如果您使用初始输入（12）递归调用rotl，您期望得到什么？经典旋转会得到12->24->48->...->3221225472->2147483649->3->6->12...。您所假设的答案的一种解释可能是12->9->3->6->12...，但另一种可能是12->9->3->3->3...。 - MooseBoys

我加入了一个可行的实现，它也有一个展示它良好运作的测试，并且完全没有分支 :) - CoffeDeveloper

在C/C++中，没有小于8位的类型，如果您想旋转仅4位，则必须明确处理该情况。CPU中的旋转指令始终旋转整个寄存器，而不是其中的一部分。 - phuclv

Answer 1

以下代码运行良好

#include <cstdint>

std::uint32_t rotl(std::uint32_t v, std::int32_t shift) {
    std::int32_t s =  shift>=0? shift%32 : -((-shift)%32);
    return (v<<s) | (v>>(32-s));
}

std::uint32_t rotr(std::uint32_t v, std::int32_t shift) {
    std::int32_t s =  shift>=0? shift%32 : -((-shift)%32);
    return (v>>s) | (v<<(32-s));
}

当然还有与之相关的测试。

#include <iostream>

int main(){
   using namespace std;
   cout<<rotr(8,1)<<endl; // 4
   cout<<rotr(8,-1)<<endl;  //16
   cout<<rotl(8,1)<<endl;  //16
   cout<<rotl(8,-1)<<endl;  //4
   cout<<rotr(4,60)<<endl;  //64
   cout<<rotr(4,61)<<endl; //32
   cout<<rotl(4,3)<<endl;  //32
   cout<<rotl(4,4)<<endl;  //64
   return 0;
}

也许我没有提供最快的实现方式，但肯定提供了一种可移植且稳定的方法。

通用版本

#include <cstdint>

template< class T>
inline T rotl( T v, std::int32_t shift){
    std::size_t m = sizeof(v)*std::numeric_limits<T>::digits;
    T s = shift>=0? shift%m: -((-shift)%m)
    return (v<<s) | (v>>(m-s));
}

template< class T>
inline T rotr( T v, std::int32_t shift){
    std::size_t m = sizeof(v)*std::numeric_limits<T>::digits;
    T s = shift>=0? shift%m: -((-shift)%m)
    return (v>>s) | (v<<(m-s));
}

干杯 :)

- CoffeDeveloper

---

忘记了“#include <limits>”并且必须在通用版本的代码中删除“sizeof(v)”（原本使用CHAR_BITS）。任何编辑器都可以获得免费积分。我几乎无法想象一种不使用汇编指令的更快的版本。 - CoffeDeveloper

Answer 2

C++20在<bit>头文件中提供了std::rotl和std::rotr。以下是来自cppreference.com的示例：

#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t i = 0b00011101;
    std::cout << "i          = " << std::bitset<8>(i) << '\n';
    std::cout << "rotl(i,0)  = " << std::bitset<8>(std::rotl(i,0)) << '\n';
    std::cout << "rotl(i,1)  = " << std::bitset<8>(std::rotl(i,1)) << '\n';
    std::cout << "rotl(i,4)  = " << std::bitset<8>(std::rotl(i,4)) << '\n';
    std::cout << "rotl(i,9)  = " << std::bitset<8>(std::rotl(i,9)) << '\n';
    std::cout << "rotl(i,-1) = " << std::bitset<8>(std::rotl(i,-1)) << '\n';
}

我相信std::bitset在这个例子中只是用于其流格式。

- leo60228

Answer 3

如果您想要对任意位数（例如4）进行按位旋转，只需在函数中添加一个参数即可：

unsigned int rotl(unsigned int value, int shift, unsigned int width) {
    return ((value << shift) & (UINT_MAX >> (sizeof(int) * CHAR_BIT - width))) | (value >> (width - shift));
}

- chuck1

---

你还需要将答案掩码为正确数量的位数。而且我认为你的公式也略有偏差。 - Mark Ransom

这里的 * CHAR_BIT 是错误的，假设 width 是以位为单位而不是字节。你的意思是：return ((1U << width) - 1) & ((value << shift) | (value >> (width - shift)));。 - Carlo Wood

if测试应该是if (width > sizeof(value) * CHAR_BIT)，但似乎这是暗示的。不需要在那里添加该分支，否则会使其比必要的慢得多。 - Carlo Wood

Answer 4

这是因为您正在使用一个32位的int，所以它按预期工作，将最高有效位包装到前面。使用更小的数据结构，如unsigned char，可以使其更易于管理。

- Dan

Answer 5

你的整数有超过4位，很可能是32位，但理论上也可以是64位或16位。因此，值12的位数为00000000000000000000000000001100。将其左旋转1位自然会得到值00000000000000000000000000011000（=24）。

- youdontneedtothankme

Answer 6

如果您不使用C++20，您可能需要两个辅助函数，如下：

template< std::size_t N >
[[ nodiscard ]] std::bitset< N > rotl( std::bitset< N > b, std::size_t const n ) noexcept
{
    return b << n | b >> ( N - n );
}

template< std::size_t N >
[[ nodiscard ]] std::bitset< N > rotr( std::bitset< N > b, std::size_t const n ) noexcept
{
    return b >> n | b << ( N - n );
}

并且你可以像使用 C++20 的 std::rotl 和 std::rotr 一样使用它们。

- NutCracker