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

Question

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

126

C++中已经提供了左移和右移运算符（<<和>>）。但是我找不到如何执行循环移位或旋转操作。

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

这里旋转右两次

Initial --> 1000 0011 0100 0010

应该产生以下结果：

Final   --> 1010 0000 1101 0000

能举个例子会更有帮助。

(编辑注：在C语言中，许多常见的旋转表达方式如果旋转次数为零则存在未定义的行为，或者编译成不止一条旋转的机器指令。这个问题的答案应该记录最佳实践。)

- Elroy

可能是Near constant time rotate that does not violate the standards的重复问题。 - jww

4

它已经在 C++20 中到来了！https://dev59.com/J3RA5IYBdhLWcg3w8SiJ#57285854 - Ciro Santilli OurBigBook.com

16个回答

43

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仍不支持。

提案指出：

Header:

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 Rotating [bitops.rot]

In the following descriptions, let N denote std::numeric_limits<T>::digits.
template<class T>
  [[nodiscard]] constexpr T rotl(T x, int s) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).

Let r be 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;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]). Let r be s % N.

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

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

- Ciro Santilli OurBigBook.com

1

为什么位旋转在现代C++中花费了这么长时间才得以实现？即使在LLVM Clang中，也只有几年前才有了内置函数 => https://reviews.llvm.org/D21457 我认为ARM在2010年之前就已经拥有了旋转功能，因此它们应该已经存在于C++11中。 - sandthorn

2

@sandthorn：我认为C++和C委员会对编译器应该能够识别可移植习惯用语（如(x >> r) | (x << (N-r))）并将其编译为旋转指令的想法非常乐观，因此基本语言不需要包括popcount或rotate。当然，考虑到这种态度，我不知道为什么他们会在整数中包括一个*乘法运算符，当你可以在任何地方编写移位加循环时。看起来C++20是某个人终于讲了一些有意义的话，并添加了大多数CPU都具有的东西，例如popcnt和bit-scan；易于模拟。 - Peter Cordes

35

由于这是C++，所以请使用内联函数：

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

使用C++11的variant类型：

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

- MSalters

7

警告：如果INT是有符号整数并且符号被设置，则此代码将出现错误！例如测试rol<std::int32_t>(1 << 31)应该翻转为1，但实际上变成了-1（因为保留了符号）。 - Nobody moving away from SE

9

@Nobody: 我已经在5年前评论过，你不应该使用带符号整数类型。对于带符号整数类型来说，旋转操作本身就没有意义。 - MSalters

2

你可以使用 std::numeric_limits<INT>::digits 代替 CHAR_BIT * sizeof。我忘记了无符号类型是否允许有未使用的填充（例如在32位中存储的24位整数），但如果是这样，那么 digits 将更好。另请参见 https://gist.github.com/pabigot/7550454，其中包含更多检查变量计数移位的版本。 - Peter Cordes

1

@PeterCordes：是的。我认为Cray的做法是（使用浮点寄存器，在指数字段应该在的位置上填充）。 - MSalters

2

“@fake-name '> 所以C++11版本在Windows上无法运行，除非你将其更改为其他内容...”是的，请将其更改为Linux。 :)” - Slava

显示剩余6条评论

22

大多数编译器都有内置函数来实现这个操作。例如，Visual Studio中有 _rotr8、_rotr16 等。

- VolkerK

哇！比被接受的答案容易多了。顺便说一下，对于DWORD（32位），请使用_rotr和_rotl。 - Gabe Halsmer

16

明确地说：

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

- Didac Perez Parera

8

这个 8 是否拼错了，实际上是指 CHAR_BIT （并非一定为 8）？ - Toby Speight

2

由于这与我的答案相同（只是将右侧交换为左侧），因此Peter Cordes对我的答案的评论在这里也适用：使用std::numeric_limits<T>::digits。 - MSalters

8

如果x是8位值，您可以使用以下方法：

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

- Farhadix

2

如果 x 是有符号的，可能会出现错误行为。 - sam hocevar

7

如何像这样使用标准的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,

- Abhay

需要修改它以考虑大于位集长度的移位。 - H. Green

添加了 m %= N; 来处理位移 >= N 的情况。 - Milania

6

以下是详细步骤：

如果整数中的位模式为33602

1000 0011 0100 0010

并且您需要向右移2位：

首先复制位模式，然后左移：长度-右移值

即长度为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
===================

您就得到了移位后的值。请记住，位运算速度更快，这甚至不需要任何循环。

- S M Kamran

1

类似于上面的子程序...b = b << m | b >> (N-m); - S M Kamran

应该使用异或（XOR），而不是或（OR）吧？1 ^ 0 = 1，0 ^ 0 = 0等。如果使用OR，它就不是排他的，因此结果总是为1。 - B.K.

5

假设您想通过L位向右移动，并且输入的x是具有N位的数字：

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

- nimrodm

3

正确答案如下：

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

- user3102555

如果 val 是有符号的，可能会出现问题。 - sam hocevar

使用宏来完成此任务的答案根本不能被视为正确。 - spectras

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AndreasT · Accepted Answer

参见这个关于另一个旋转问题的答案的早期版本，其中有关于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`，因此您可以为其他大小创建版本。

请参阅{{link1：也是C++11模板版本}}，其中包含许多安全检查（包括`static_assert`断言类型宽度为2的幂），这在某些24位DSP或36位大型机上不适用。

我建议仅将模板用作包含显式旋转宽度的包装器的后端。整数提升规则意味着`rotl_template(u16 & 0x11UL, 7)`将执行32位或64位旋转，而不是16位（取决于`unsigned long`的宽度）。即使是`uint16_t & uint16_t`也会根据C++的整数提升规则提升为`signed int`，除非在`int`不比`uint16_t`宽的平台上。

On x86, this version inlines to a single rol r32, cl (or rol r32, imm8) with compilers that grok it, because the compiler knows that x86 rotate and shift instructions mask the shift-count the same way the C source does.

编译器对于在x86上避免未定义行为的习惯用法提供支持，适用于变量计数的移位操作，例如uint32_t x和unsigned int n。

clang: 自clang3.5以来，因为可变计数的旋转而被认可，之前是多个移位+或指令。
gcc: 自gcc4.9以来，因为可变计数的旋转而被认可，之前是多个移位+或指令。gcc5及更高版本也优化了维基百科版本中的分支和掩码，只使用ror或rol指令进行可变计数。
icc: 自ICC13或更早版本以来，因为可变计数的旋转而被支持。常数计数的旋转使用shld edi,edi,7，在某些CPU上（尤其是AMD，但也包括一些Intel）比rol edi,7更慢且占用更多字节，当无法使用rorx eax,edi,25来保存MOV时。
MSVC: x86-64 CL19：仅被认可为常数计数的旋转。（维基百科的习语被认可，但分支和AND没有被优化掉）。在x86（包括x86-64）上使用<intrin.h>中的_rotl / _rotr内嵌函数。

gcc for ARM在变量计数旋转时使用and r1, r1, #31，但仍然通过一条指令执行实际旋转：ror r0, r0, r1。因此，gcc没有意识到旋转计数本质上是模数运算。正如ARM文档所说，"带有移位长度n大于32的ROR与带有移位长度n-32的ROR相同"。我认为gcc在这里会感到困惑，因为ARM上的左/右移操作会饱和计数，所以移位32或更多会清除寄存器。（与x86不同，x86的移位与旋转一样，会屏蔽计数）。它可能会在识别旋转习惯用法之前决定需要一个AND指令，因为非循环移位在该目标上的工作方式不同。

当前的x86编译器仍然使用额外的指令来屏蔽8位和16位旋转的变量计数，可能是因为它们不避免在ARM上进行AND操作的同样原因。这是一个被忽视的优化，因为在任何x86-64 CPU上，性能并不取决于旋转计数。（计数的屏蔽是为了性能原因而引入的，因为它以迭代方式处理移位，而不是像现代CPU那样具有恒定延迟。）

顺便说一下，对于可变计数旋转，最好使用右旋转，以避免让编译器执行32-n来实现左旋转，因为像ARM和MIPS这样只提供右旋转的架构。（这在编译时常量计数中优化消除。）

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

确保你在使用无符号类型的时候，对于变量 n 和返回值都使用无符号类型，否则它将不会是一个旋转操作。在 x86 目标上，gcc 会进行算术右移，即将符号位复制到右移后的位置，而不是补零，这会导致当你将两个右移后的值进行或操作时出现问题。在 C 语言中，对于负数的右移是实现定义的行为。

此外，确保移位计数是无符号类型，因为使用带符号类型的 (-n)&31 可能是按位取反或者符号/幅度表示法，而不同于使用无符号或二进制补码得到的模 2^n。对于每个宽度的 x，我在每个编译器上都测试过无符号整数类型，效果良好。其他一些类型实际上会破坏某些编译器对于这种惯用法的识别，所以不要仅仅使用与 x 相同的类型。

一些编译器提供了旋转操作的内置函数，这比起使用内联汇编要好得多，尤其是当可移植版本在目标编译器上生成的代码不够优化时。据我所知，目前还没有跨平台的内置函数。以下是一些x86选项：

英特尔文档显示，<immintrin.h>提供了_rotl和_rotl64内嵌函数，右移同理。MSVC需要<intrin.h>，而gcc需要<x86intrin.h>。通过#ifdef来处理gcc与icc的问题。Clang 9.0也有这些函数，但在此之前似乎没有提供，除非使用MSVC兼容模式，使用-fms-extensions -fms-compatibility -fms-compatibility-version=17.00。而且它们生成的汇编代码很糟糕（额外的掩码和一个CMOV指令）。
MSVC：_rotr8和_rotr16。
gcc和icc（不包括Clang）：<x86intrin.h>还提供了__rolb/__rorb用于8位左/右旋转，__rolw/__rorw（16位），__rold/__rord（32位），__rolq/__rorq（64位，仅对64位目标定义）。对于窄旋转，实现使用__builtin_ia32_rolhi或...qi，但32位和64位旋转使用移位/或运算（没有保护不确定行为，因为ia32intrin.h中的代码只需要在gcc上针对x86工作）。GNU C似乎没有任何跨平台的__builtin_rotate函数，就像它对__builtin_popcount所做的那样（它会展开为目标平台上最优的代码，即使它不是一个单一指令）。大多数情况下，通过惯用识别可以得到良好的代码。
Clang具有__builtin_rotateleft8，__builtin_rotateright8，以及其他宽度的类似函数。请参阅Clang的语言扩展文档。还有其他位操作的内建函数/内嵌函数，例如__builtin_bitreverse32（在ARM / AArch64上可以编译为rbit）。您可以使用__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编译器也有内嵌函数，但我们不要在这个社区维基回答中包含它们所有的内容。（或许可以在关于内嵌函数的现有回答中添加这些内容）。

（这个回答的旧版本建议使用MSVC特定的内联汇编（仅适用于32位x86代码），或者使用C版本的http://www.devx.com/tips/Tip/14043。评论是对此的回复。） 内联汇编会破坏许多优化，特别是MSVC风格，因为它会强制输入值被存储和重新加载。精心编写的GNU C内联汇编旋转操作可以允许计数成为编译时常量移位计数的立即操作数，但是如果在内联之后要移位的值也是编译时常量，它仍然无法完全优化掉。请参考https://gcc.gnu.org/wiki/DontUseInlineAsm。