Best practices for circular shift (rotate) operations in C++

因为它是 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));
}

假设你想移动 L位，输入 x是一个 N位的数字:

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

过载一个函数:

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


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

大多数编译器都有相应的内部特性。 例如 Visual Studio < a href = “ https://Learn.microsoft.com/en-us/cpp/intrinsics/rotr8-rotr16? view = vs-2019”rel = “ nofollow noReferrer”> _ rotr8，_ rotr16

How abt something like this, using the standard bitset ...

#include <bitset>
#include <iostream>


template <std::size_t N>
inline void
rotate(std::bitset<N>& b, unsigned m)
{
b = b << m | b >> (N-m);
}


int main()
{
std::bitset<8> b(15);
std::cout << b << '\n';
rotate(b, 2);
std::cout << b << '\n';


return 0;
}

HTH,

详细地说，您可以应用以下逻辑。

If Bit Pattern is 33602 in Integer

1000 0011 0100 0010

然后你需要向右转两次: 首先复制一个位模式，然后向左移位: Llength-RightShift 也就是说，长度是16，右移值是2 16-2 = 14

在左移14次之后。

1000 0000 0000 0000

现在向右移动数值33602，按要求移动两倍。 你得到了

0010 0000 1101 0000

现在取14次左移值和2次右移值之间的 OR。

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

记住，位智能操作更快，这甚至不需要任何循环。

If x is an 8 bit value, you can use this:

x=(x>>1 | x<<7);

当然:

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

Source Code 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;
}

另一个建议

template<class T>
inline T rotl(T x, unsigned char moves){
unsigned char temp;
__asm{
mov temp, CL
mov CL, moves
rol x, CL
mov CL, temp
};
return x;
}

The correct answer is following:

#define BitsCount( val ) ( sizeof( val ) * CHAR_BIT )
#define Shift( val, steps ) ( steps % BitsCount( val ) )
#define ROL( val, steps ) ( ( val << Shift( val, steps ) ) | ( val >> ( BitsCount( val ) - Shift( val, steps ) ) ) )
#define ROR( val, steps ) ( ( val >> Shift( val, steps ) ) | ( val << ( BitsCount( val ) - Shift( val, steps ) ) ) )

下面是 Dídac Pérez 的回答的一个稍微改进的版本，实现了两个方向，并演示了使用无符号 char 和无符号长值的这些函数的用法。一些注释:

1. 这些函数是为编译器优化而内联的
2. 我使用了一个 cout << +value技巧，以简洁的方式输出一个无符号字符，我在这里找到了它: https://stackoverflow.com/a/28414758/1599699
3. 为了清晰和安全起见，我建议使用显式的 <put the type here>语法。
4. 我在 shift tNum 参数中使用了 unsignedchar，这是因为我在附加细节部分 给你中发现:

如果 additive-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");
}

--- Substituting RLC in 8051 C for speed --- Rotate left carry
Here is an example using RLC to update a serial 8 bit DAC msb first:
(r=DACVAL, P1.4= SDO, P1.5= SCLK)
MOV     A, r
?1:
MOV     B, #8
RLC     A
MOV     P1.4, C
CLR     P1.5
SETB    P1.5
DJNZ    B, ?1


Here is the code in 8051 C at its fastest:
sbit ACC_7  = ACC ^ 7 ; //define this at the top to access bit 7 of ACC
ACC     =   r;
B       =   8;
do  {
P1_4    =   ACC_7;  // this assembles into mov c, acc.7  mov P1.4, c
ACC     <<= 1;
P1_5    =   0;
P1_5    =   1;
B       --  ;
} while ( B!=0 );
The keil compiler will use DJNZ when a loop is written this way.
I am cheating here by using registers ACC and B in c code.
If you cannot cheat then substitute with:
P1_4    =   ( r & 128 ) ? 1 : 0 ;
r     <<=   1;
This only takes a few extra instructions.
Also, changing B for a local var char n is the same.
Keil does rotate ACC left by ADD A, ACC which is the same as multiply 2.
It only takes one extra opcode i think.
Keeping code entirely in C keeps things simpler sometimes.

C++20 std::rotl and std::rotr

它已经到达! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html，应该添加到 <bit>头。

Cpferences 说 的用法将类似于:

#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';
}

输出:

i          = 00011101
rotl(i,0)  = 00011101
rotl(i,1)  = 00111010
rotl(i,4)  = 11010001
rotl(i,9)  = 00111010
rotl(i,-1) = 10001110

当对 GCC 的支持到来时，我将尝试使用它，使用 g++-9 -std=c++2a的 GCC 9.1.0仍然不支持它。

The proposal says:

标题:

namespace std {
// 25.5.5, rotating
template<class T>
[[nodiscard]] constexpr T rotl(T x, int s) noexcept;
template<class T>
[[nodiscard]] constexpr T rotr(T x, int s) noexcept;

and:

25.5.5旋转[ bitops.rot ]

在下面的描述中，让 N 表示 std::numeric_limits<T>::digits。

template<class T>
[[nodiscard]] constexpr T rotl(T x, int s) noexcept;

约束: T 是一个无符号整数类型(3.9.1[ basic.basic ])。

让我们的 s% N。

Returns: If r is 0, x; if r is positive, (x << r) | (x >> (N - r)); if r is negative, rotr(x, -r).

template<class T>
[[nodiscard]] constexpr T rotr(T x, int s) noexcept;

约束: T 是一个无符号整数类型(3.9.1[ basic.basic ])。 让我们的 s% N。

返回: 如果 r 为0，x; 如果 r 为正，则返回 (x >> r) | (x << (N - r)); 如果 r 为负，则返回 rotl(x, -r)。

还添加了一个 std::popcount来计算1位的数目: 如何计算一个32位整数的集合位数？