C++ 中循环移位（旋转）操作的最佳实践

#define ROTATE_RIGHT(x) ( (x>>1) | (x&1?0x8000:0) )

另请参阅此答案的早期版本，了解另一个轮换问题，其中包含有关 asm gcc/clang 为 x86 生成的内容的更多详细信息。

在 C 和 C++ 中表达避免任何未定义行为的轮换的最编译器友好的方式似乎是 John Regehr 的实现。我已将其调整为按类型的宽度旋转（使用固定宽度的类型，例如）。uint32_t

#include <stdint.h>   // for uint32_t
#include <limits.h>   // for CHAR_BIT
// #define NDEBUG
#include <assert.h>

static inline uint32_t rotl32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);  // assumes width is a power of 2.

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n<<c) | (n>>( (-c)&mask ));
}

static inline uint32_t rotr32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n>>c) | (n<<( (-c)&mask ));
}

适用于任何无符号整数类型，而不仅仅是 ，因此您可以为其他大小创建版本。uint32_t

另请参阅具有大量安全检查的 C++11 模板版本（包括类型宽度为 2 的幂static_assert），例如，在某些 24 位 DSP 或 36 位大型机上并非如此。

我建议仅将模板用作名称明确包含旋转宽度的包装器的后端。整数升级规则意味着 rotl_template（u16 & 0x11UL， 7） 将执行 32 位或 64 位旋转，而不是 16 位（取决于 的宽度）。甚至被 C++ 的整数提升规则提升，除非在宽度不超过 的平台上。unsigned longuint16_t & uint16_tsigned intintuint16_t

---

在 x86 上，此版本内联到单个 rol r32、cl（或）以及编译器来处理它，因为编译器知道 x86 旋转和移位指令以与 C 源代码相同的方式屏蔽移位计数。rol r32, imm8

编译器在 x86 上支持此避免 UB 的习惯用语，用于变量计数偏移：uint32_t xunsigned int n

• clang：识别自 clang3.5 以来的变量计数轮换，在此之前多次移位+或 insns。
• GCC：自 GCC4.9 以来的可变计数轮换、在此之前的多个班次+或 INNS。GCC5 及更高版本也优化了维基百科版本中的分支和掩码，仅使用 OR 指令进行变量计数。rorrol
• ICC：支持自 ICC13 或更早版本以来的变量计数轮换。当 BMI2 不可用于保存 MOV 时，常量计数会轮换使用，这比某些 CPU（尤其是 AMD，但也包括一些 Intel）更慢，占用的字节更多。shld edi,edi,7rol edi,7rorx eax,edi,25
• MSVC：x86-64 CL19：仅识别常量计数旋转。（维基百科习语是公认的，但分支和 AND 没有被优化掉）。使用 x86（包括 x86-64）上的 / 内部函数。_rotl_rotr<intrin.h>

ARM 的 gcc 使用 an 和 r1， r1， #31 进行可变计数旋转，但仍然使用单个指令执行实际旋转：.因此，gcc 没有意识到旋转计数本质上是模块化的。正如 ARM 文档所说，“移位长度为 n 的 ROR 大于 32 与移位长度为 n-32 的 ROR 相同”。 我认为 gcc 在这里会感到困惑，因为 ARM 上的左/右移会使计数饱和，因此偏移 32 或更多将清除寄存器。（与 x86 不同，在 x86 中，移位屏蔽计数与旋转相同）。它可能决定在识别旋转习语之前需要 AND 指令，因为非循环移位在该目标上的工作方式。ror r0, r0, r1

当前的 x86 编译器仍然使用额外的指令来屏蔽 8 位和 16 位旋转的变量计数，这可能与它们不避免 ARM 上的 AND 的原因相同。这是一个错过的优化，因为性能不依赖于任何 x86-64 CPU 上的轮换计数。（出于性能原因，286 引入了计数屏蔽，因为它以迭代方式处理移位，而不是像现代 CPU 那样使用恒定延迟。

顺便说一句，对于变量计数旋转，首选 rotate-right，以避免编译器在仅提供 rotate-right 的 ARM 和 MIPS 等架构上实现左旋转。（这优化了编译时常量计数。32-n

有趣的事实：ARM 实际上并没有专门的移位/旋转指令，它只是 MOV，源操作数在 ROR 模式下通过桶形移位器：.因此，旋转可以折叠成寄存器源操作数，用于 EOR 指令或其他东西。mov r0, r0, ror r1

---

请确保对 n 和返回值使用无符号类型，否则它不会是旋转。（x86 目标的 GCC 会进行算术右移，在符号位的副本中移位而不是零，当您将两个值一起移位时会导致问题。负有符号整数的右移是 C 语言中实现定义的行为。OR

此外，请确保移位计数是无符号类型，因为有符号类型可能是 1 的补码或符号/幅度，与使用无符号或 2 的补码得到的模块化 2^n 不同。（参见 Regehr 博客文章的评论）。 在我看过的每个编译器上都做得很好，对于每个宽度。其他一些类型实际上会破坏某些编译器的惯用语识别，因此不要只使用与 相同的类型。(-n)&31unsigned intxx

---

一些编译器为旋转提供了内部函数，如果可移植版本不能在目标编译器上生成良好的代码，则这比内联 asm 要好得多。据我所知，任何编译器都没有跨平台内部函数。以下是一些 x86 选项：

• 英特尔文档显示 <immintrin.h> 提供了_rotl和_rotl64内部函数，右移也是如此。MSVC 需要 ，而 gcc 需要 。An 负责 gcc 与 icc。Clang 9.0 也有它，但在此之前它似乎没有在任何地方提供它们，除了在 MSVC 兼容模式下使用 -fms-extensions -fms-compatibility -fms-compatibility-version=17.00。它为他们发出的 asm 很糟糕（额外的掩蔽和 CMOV）。<intrin.h><x86intrin.h>#ifdef
• MSVC：_rotr8和_rotr16。
• GCC 和 ICC（不是 CLANG）：还提供 / for 8 位左/右旋转、/（16 位）、/（32 位）、/（64 位，仅为 64 位目标定义）。对于窄旋转，实现使用 或 ，但 32 位和 64 位旋转是使用 shift/or 定义的（没有针对 UB 的保护，因为 ia32intrin.h 中的代码只需要在 x86 的 gcc 上工作）。GNU C 似乎没有像它那样具有任何跨平台功能（它扩展到目标平台上的任何最佳功能，即使它不是单个指令）。大多数时候，你从成语识别中获得好的代码。<x86intrin.h>__rolb__rorb__rolw__rorw__rold__rord__rolq__rorq__builtin_ia32_rolhi...qi__builtin_rotate__builtin_popcount
• Clang 具有 、 和类似的宽度。请参阅 Clang 的语言扩展文档。还有其他位操作的内置/内部函数，例如（可以在 ARM / AArch64 上编译）。您可以使用 进行测试。__builtin_rotateleft8__builtin_rotateright8__builtin_bitreverse32rbit__has_builtin

// For real use, probably use a rotate intrinsic for MSVC, or this idiom for other compilers.  This pattern of #ifdefs may be helpful
#if defined(__x86_64__) || defined(__i386__)

#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>  // Not just <immintrin.h> for compilers other than icc
#endif

uint32_t rotl32_x86_intrinsic(rotwidth_t x, unsigned n) {
  //return __builtin_ia32_rorhi(x, 7);  // 16-bit rotate, GNU C
  return _rotl(x, n);  // gcc, icc, msvc.  Intel-defined.
  //return __rold(x, n);  // gcc, icc.
  // can't find anything for clang
}
#endif

据推测，一些非 x86 编译器也有内部函数，但我们不要扩展这个 community-wiki 答案以包括它们。（也许在关于内在的现有答案中这样做）。

---

（此答案的旧版本建议使用 MSVC 特定的内联 asm（仅适用于 32 位 x86 代码），或 http://www.devx.com/tips/Tip/14043 用于 C 版本。评论正在对此做出回应。

内联 asm 会破坏许多优化，尤其是 MSVC 样式，因为它会强制存储/重新加载输入。一个精心编写的 GNU C inline-asm rotate 将允许计数成为编译时常量移位计数的直接操作数，但如果要移位的值也是内联后的编译时常数，它仍然无法完全优化。https://gcc.gnu.org/wiki/DontUseInlineAsm。

由于它是 C++，因此请使用内联函数：

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

C++ 变体：

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

假设您要向右移动位，并且输入是带位的数字：LxN

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 _rotr8、_rotr16

像这样的东西，使用标准位集......

#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，

具体而言，您可以应用以下逻辑。

如果位模式为整数 33602

1000 0011 0100 0010

然后，您需要用 2 个正确的 shif 翻身： 首先复制位模式，然后左移它： 长度 - 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 是 8 位值，则可以使用以下值：

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

明确：

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

源代码 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;
}

正确答案如下：

#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. 我使用了一个技巧来简洁地输出一个无符号的字符，我在这里找到了它：https://stackoverflow.com/a/28414758/1599699cout << +value
3. 为了清晰和安全起见，我建议使用显式语法。<put the type here>
4. 我使用了 unsigned char 作为 shiftNum 参数，因为我在下面的“其他详细信息”部分中找到了什么：

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

--- 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 和 std：：rotr

它来了！http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html，应将其添加到标题中。<bit>

cppreference 表示，用法将是这样的：

#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 获得支持时，我会尝试一下，GCC 9.1.0 仍然不支持它。g++-9 -std=c++2a

该提案说：

页眉：

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;

和：

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.fundamental]）。

设 r 为 s % N。

返回值：如果 r 为 0，则 x;如果 r 为正数，则 ;如果 r 为负数，则 .(x << r) | (x >> (N - r))rotr(x, -r)

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

约束：T 是无符号整数类型 （3.9.1 [basic.fundamental]）。 设 r 为 s % N。

返回值：如果 r 为 0，则 x;如果 r 为正数，则 ;如果 r 为负数，则 .(x >> r) | (x << (N - r))rotl(x, -r)

还添加了 A 来计算 1 位的数量：如何计算 32 位整数中的设置位数？std::popcount