[c++] C ++中循环移位(旋转)操作的最佳实践


Answers

因为它是C ++,所以使用内联函数:

template <typename INT> 
INT rol(INT val) {
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

C ++ 11变体:

template <typename INT> 
constexpr INT rol(INT val) {
    static_assert(std::is_unsigned<INT>::value,
                  "Rotate Left only makes sense for unsigned types");
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}
Question

左右移位运算符(<<和>>)已在C ++中可用。 但是,我无法找到如何执行循环移位或旋转操作。

如何执行“向左旋转”和“向右旋转”等操作?

在这里向右旋转两次

Initial --> 1000 0011 0100 0010

应该导致:

Final   --> 1010 0000 1101 0000

一个例子会有所帮助。

(编者注:如果旋转计数为零,许多常见的表达方式在C中旋转会受到未定义的行为的影响,或者编译为不止一个旋转机器指令。这个问题的答案应记录最佳实践。)




假设你想要向右移位L位,输入x是一个带N位的数字:

unsigned ror(unsigned x, int L, int N) 
{
    unsigned lsbs = x & ((1 << L) - 1);
    return (x >> L) | (lsbs << (N-L));
}



明确:

template<class T>
T ror(T x, unsigned int moves)
{
  return (x >> moves) | (x << sizeof(T)*8 - moves);
}



重载功能:

unsigned int rotate_right(unsigned int x)
{
 return (x>>1 | (x&1?0x80000000:0))
}

unsigned short rotate_right(unsigned short x) { /* etc. */ }



详细信息您可以应用以下逻辑。

如果位模式在整数中是33602

1000 0011 0100 0010

然后你需要翻转2个右边的Shifs:首先制作一个位模式的副本然后左移它:长度 - RightShift即长度是16右移值是2 16 - 2 = 14

经过14次左移后你就得到了。

1000 0000 0000 0000

现在右移33602,根据需要移动2次。 你得到

0010 0000 1101 0000

现在在14次左移位值和2次右移位值之间取一个OR。

1000 0000 0000 0000
0010 0000 1101 0000
===================
1010 0000 1101 0000
===================

并且您获得了转移的翻转价值。 记住,位操作更快,甚至不需要任何循环。




源代码x位号

int x =8;
data =15; //input
unsigned char tmp;
for(int i =0;i<x;i++)
{
printf("Data & 1    %d\n",data&1);
printf("Data Shifted value %d\n",data>>1^(data&1)<<(x-1));
tmp = data>>1|(data&1)<<(x-1);
data = tmp;  
}



下面是DídacPérez答案的略微改进版本,实现了两个方向,并使用unsigned char和unsigned long long值演示了这些函数的用法。 几点说明:

  1. 这些函数内联用于编译器优化
  2. 我使用了一个cout << +value技巧来简洁地输出我在这里找到的无符号字符: https://.com/a/28414758/1599699 : https://.com/a/28414758/1599699
  3. 为了清晰和安全,我建议使用显式的<put the type here>语法。
  4. 我使用unsigned char作为shiftNum参数,因为我在附加详细信息部分中here

如果additive-expression为负或者如果additive-expression大于或等于(提升的) shift-expression中的位数,则移位操作的结果是不确定的。

这是我正在使用的代码:

#include <iostream>

using namespace std;

template <typename T>
inline T rotateAndCarryLeft(T rotateMe, unsigned char shiftNum)
{
    static const unsigned char TBitCount = sizeof(T) * 8U;

    return (rotateMe << shiftNum) | (rotateMe >> (TBitCount - shiftNum));
}

template <typename T>
inline T rotateAndCarryRight(T rotateMe, unsigned char shiftNum)
{
    static const unsigned char TBitCount = sizeof(T) * 8U;

    return (rotateMe >> shiftNum) | (rotateMe << (TBitCount - shiftNum));
}

void main()
{
    //00010100 == (unsigned char)20U
    //00000101 == (unsigned char)5U == rotateAndCarryLeft(20U, 6U)
    //01010000 == (unsigned char)80U == rotateAndCarryRight(20U, 6U)

    cout << "unsigned char " << 20U << " rotated left by 6 bits == " << +rotateAndCarryLeft<unsigned char>(20U, 6U) << "\n";
    cout << "unsigned char " << 20U << " rotated right by 6 bits == " << +rotateAndCarryRight<unsigned char>(20U, 6U) << "\n";

    cout << "\n";


    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
    {
        cout << "unsigned char " << 21U << " rotated left by " << +shiftNum << " bit(s) == " << +rotateAndCarryLeft<unsigned char>(21U, shiftNum) << "\n";
    }

    cout << "\n";

    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
    {
        cout << "unsigned char " << 21U << " rotated right by " << +shiftNum << " bit(s) == " << +rotateAndCarryRight<unsigned char>(21U, shiftNum) << "\n";
    }


    cout << "\n";

    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
    {
        cout << "unsigned long long " << 3457347ULL << " rotated left by " << +shiftNum << " bit(s) == " << rotateAndCarryLeft<unsigned long long>(3457347ULL, shiftNum) << "\n";
    }

    cout << "\n";

    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
    {
        cout << "unsigned long long " << 3457347ULL << " rotated right by " << +shiftNum << " bit(s) == " << rotateAndCarryRight<unsigned long long>(3457347ULL, shiftNum) << "\n";
    }

    cout << "\n\n";
    system("pause");
}





Links