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

Question

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

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

在这里向右旋转两次

Initial --> 1000 0011 0100 0010

应该导致:

Final   --> 1010 0000 1101 0000

一个例子会有所帮助.

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

Answer 1

另请参阅另一个旋转问题的此答案的早期版本,其中包含有关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模板版本(包括static_assert类型宽度为2的幂),例如,某些24位DSP或36位大型机不是这种情况.

我建议只使用模板作为包装器的后端,其名称包含明确的旋转宽度. 整数提升规则意味着rotl_template(u16 & 0x11UL, 7)将执行32或64位旋转,而不是16(取决于宽度unsigned long).甚至uint16_t & uint16_t是signed int通过C++的整数提升规则来提升,除了在int不宽于的平台上uint16_t.

在x86上,这个版本内联到单个rol r32, cl(或rol r32, imm8)编译程序,因为编译器知道x86旋转和移位指令掩盖移位计数与C源相同.

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

• clang:在clang3.5之后被识别为变量计数旋转,之前是多次移位+或insn.
• gcc:自gcc4.9以来可识别的变量计数旋转,在此之前多次移位+或insn.gcc5和更高版本也使用一个ror或rol变量计数指令来优化维基百科版本中的分支和掩码.
• icc:支持自ICC13或更早版本以来的可变计数旋转.当BMI2不可用于保存MOV 时,常数计数旋转使用shld edi,edi,7比rol edi,7一些CPU(特别是AMD,但也有一些Intel)更慢并占用更多字节rorx eax,edi,25.
• MSVC:x86-64 CL19:仅识别恒定计数旋转.(维基百科成语被识别,但分支和AND未被优化).使用x86上的_rotl/ _rotrintrinsics <intrin.h>(包括x86-64).

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和返回值,否则它将不是旋转.(对于x86目标,gcc会进行算术右移,移位符号位的副本而不是零,当OR两个移位值一起时会导致问题.负有符号整数的右移是C中的实现定义行为.)

此外,确保移位计数是无符号类型,因为(-n)&31带符号类型可以是一个补码或符号/幅度,而不是与无符号或二进制补码的模块2 ^ n相同.(参见Regehr博客文章的评论). unsigned int对于我看过的每个编译器,每个宽度都很好x.其他一些类型实际上打败了一些编译器的习语识别,所以不要只使用相同的类型x.

有些编译器提供了旋转的内在函数,如果可移植版本没有在您要定位的编译器上生成良好的代码,那么它比内联asm好得多.对于我所知道的任何编译器,没有跨平台的内在函数.以下是一些x86选项:

• 英特尔<immintrin.h>提供_rotl和_rotl64内在的文档,右移也是如此.MSVC需要<intrin.h>,而gcc需要<x86intrin.h>.一个#ifdef需要照顾的gcc与国际刑事法院,但铛似乎并没有在任何地方提供给他们,除非与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_rolhi或...qi,但是32和64位旋转是使用shift /或(没有针对UB的保护来定义的,因为代码ia32intrin.h只需要在x86上使用gcc).GNU C似乎没有任何跨平台__builtin_rotate功能__builtin_popcount(它扩展到目标平台上的任何最佳功能,即使它不是单个指令).大多数时候,你从成语识别中获得了很好的代码.

// 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特定的内联asm(仅适用于32位x86代码),或者适用于C版本的http://www.devx.com/tips/Tip/14043.评论回复.)

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

Answer 2

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

Answer 3

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

阿std::popcount也加入到计数的1个比特的数量：如何计算在一个32位的整数组的位的数目？

Answer 4

大多数编译器都有内在函数.Visual Studio例如_rotr8,_rotr16

Answer 5

明确:

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

Answer 6

如何使用标准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,

Answer 7

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

如果位模式在整数中是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
===================

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

Answer 8

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

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

Answer 9

如果x是8位值,则可以使用:

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