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

Question

左移和右移运算符（<< 和 >>）在 C++ 中已经可用。但是，我不知道如何执行循环移位或旋转操作。

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

在这里向右旋转两次

Initial --> 1000 0011 0100 0010

应该导致：

Final   --> 1010 0000 1101 0000

一个例子会很有帮助。

（编者注：如果旋转计数为零，或者编译为不只是单个旋转机器指令，那么在 C 中表达旋转的许多常见方式都会遭受未定义的行为。这个问题的答案应该记录最佳实践。）

score 124 · Accepted Answer

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

在 C 和 C++ 中表达旋转以避免任何未定义行为的最编译器友好的方式似乎是John Regehr 的 implementation。我已经将它调整为按类型的宽度旋转（使用固定宽度的类型，如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 模板版本static_assert（包括类型宽度是 2 的幂），例如，在某些 24 位 DSP 或 36 位大型机上并非如此。

我建议仅将模板用作名称明确包含旋转宽度的包装器的后端。 整数提升规则意味着rotl_template(u16 & 0x11UL, 7)将执行 32 位或 64 位循环，而不是 16 位（取决于的宽度unsigned long）。Even由 C++ 的整数uint16_t & uint16_t提升signed int规则提升，除非在int不大于uint16_t.

在 x86 上，此版本内联到单个rol r32, cl(or rol r32, imm8) 编译器，因为编译器知道x86 旋转和移位指令以与 C 源代码相同的方式屏蔽移位计数。

编译器支持 x86 上的这种避免 UB 的习惯用法，uint32_t x用于unsigned int n变量计数移位：

clang：从 clang3.5 开始识别为可变计数轮换，在此之前有多个班次+或 insns。
gcc：从 gcc4.9 开始识别为变量计数旋转，在此之前有多个班次+或 insns。gcc5 及更高版本也优化了维基百科版本中的分支和掩码，仅使用变量计数的rororrol指令。
icc：从 ICC13 或更早版本开始支持可变计数轮换。当 BMI2 不能用于保存 MOV时，常量计数会shld edi,edi,7比rol edi,7某些 CPU（尤其是 AMD，还有一些 Intel）更慢并占用更多字节。rorx eax,edi,25
MSVC：x86-64 CL19：仅识别为常量计数旋转。（维基百科成语被识别，但分支和 AND 没有被优化掉）。使用x86（包括 x86-64）上的_rotl/_rotr内在函数。<intrin.h>

ARM 的 gcc 使用and r1, r1, #31for variable-count 旋转，但实际旋转仍然使用一条指令: ror r0, r0, r1。所以 gcc 没有意识到旋转计数本质上是模块化的。正如 ARM 文档所说，“具有移位长度的 ROR n，超过 32 与具有移位长度的 ROR 相同n-32”。我认为 gcc 在这里会感到困惑，因为 ARM 上的左/右移位会使计数饱和，因此移位 32 或更多将清除寄存器。（与 x86 不同，移位掩盖计数与旋转相同）。它可能决定在识别旋转习语之前需要一个 AND 指令，因为非循环移位如何在该目标上起作用。

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

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

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

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

此外，请确保移位计数是无符号类型，因为(-n)&31有符号类型可能是一个补码或符号/大小，而不是与您使用无符号或二进制补码获得的模块化 2^n 不同。（参见 Regehr 博客文章的评论）。 unsigned int在我看过的每个编译器上都做得很好，对于x. 其他一些类型实际上破坏了一些编译器的习惯用法识别，所以不要只使用与x.

一些编译器为 rotates 提供了内在函数，如果可移植版本不能在您的目标编译器上生成好的代码，这比 inline-asm 好得多。我所知道的任何编译器都没有跨平台内在函数。这些是一些 x86 选项：

英特尔文档<immintrin.h>提供_rotl和_rotl64内在函数，右移也是如此。MSVC 需要<intrin.h>，而 gcc 需要<x86intrin.h>。An#ifdef负责处理 gcc 与 icc。Clang 9.0 也有它，但在此之前它似乎没有在任何地方提供它们，除了在 MSVC 兼容模式下与-fms-extensions -fms-compatibility -fms-compatibility-version=17.00. 它为他们发出的 asm 很糟糕（额外的掩蔽和 CMOV）。
MSVC：_rotr8和_rotr16。
gcc 和 icc（不是 clang）： <x86intrin.h>还提供__rolb/__rorb用于 8 位左/右旋转，__rolw/ __rorw（16 位）， __rold/ __rord（32 位），__rolq/ __rorq（64 位，仅针对 64 位目标定义）。对于窄轮换，实现使用__builtin_ia32_rolhior ...qi，但 32 位和 64 位轮换是使用 shift/or 定义的（没有针对 UB 的保护，因为其中的代码ia32intrin.h只需要在 x86 的 gcc 上工作）。GNU C 似乎没有任何跨平台__builtin_rotate功能__builtin_popcount（即使它不是一条指令，它也可以扩展到目标平台上的最佳功能）。大多数时候，您可以从 idiom-recognition 中获得好的代码。

// 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 编译器也具有内在函数，但我们不要扩展这个社区 wiki 答案以包含它们全部。（也许在关于内在函数的现有答案中这样做）。

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

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

score 35 · Accepted Answer

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

score 34 · Accepted Answer

C++20std::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.0g++-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 为正，(x << r) | (x >> (N - r)); 如果 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 为正，(x >> r) | (x << (N - r)); 如果 r 是负数，rotl(x, -r).

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

score 23 · Accepted Answer

23

大多数编译器都有内部函数。Visual Studio 例如_rotr8、_rotr16

于 2009-04-22T10:42:58.360 回答

score 16 · Accepted Answer

明确：

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

score 8 · Accepted Answer

8

如果 x 是 8 位值，则可以使用：

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

于 2010-04-27T11:55:02.130 回答

score 7 · Accepted Answer

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

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

高温下，

score 6 · Accepted Answer

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

如果位模式是整数 33602

1000 0011 0100 0010

然后你需要用 2 个右移位翻转：首先复制位模式，然后左移它：长度 - 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
====================

你得到你的转移翻转价值。请记住，按位操作更快，甚至不需要任何循环。

score 5 · Accepted Answer

假设您想按位右移L，并且输入x是一个带N位的数字：

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

score 3 · Accepted Answer

正确答案如下：

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

score 0 · Accepted Answer

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

score 0 · Accepted Answer

另一个建议

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

score 0 · Accepted Answer

下面是Dídac Pérez 答案的略微改进版本，实现了两个方向，以及使用 unsigned char 和 unsigned long long 值的这些函数用法的演示。几个注意事项：

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

如果附加表达式为负或附加表达式大于或等于（提升的）移位表达式中的位数，则移位运算的结果未定义。

这是我正在使用的代码：

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

score -1 · Accepted Answer

-1

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

于 2009-04-22T10:26:11.693 回答

score -1 · Accepted Answer

重载一个函数：

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

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

score -1 · Accepted Answer

--- 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++ - C++ 中循环移位（旋转）操作的最佳实践

16 回答 16

Related

Reference