c语言中的循环移位函数,C ++中循环移位（旋转）操作的最佳实践

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

在C和C ++中表达旋转的最容易编译的方法是避免任何未定义的行为，这似乎是John Regehr的实现。 我已经调整它以按类型的宽度旋转(例如假设unsigned long正好是32位宽，尽管C / C ++只保证它至少是那么宽。我试图通过省略那种检查来保持它的可读性 事情)。

#include // for uint32_t

#include // for CHAR_BIT

// #define NDEBUG

#include

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

}

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

另请参阅具有大量安全检查的C ++ 11模板版本(包括类型宽度为2的幂的unsigned long)，例如，某些24位DSP或36位大型机不是这种情况。

我建议只使用模板作为包装器的后端，其名称包含明确的旋转宽度。 整数提升规则意味着unsigned long将执行32或64位旋转，而不是16(取决于unsigned long的宽度)。 即使uint16_t & uint16_t被C ++的整数提升规则提升为signed int，除了在int不宽于ia32intrin.h的平台上。

在x86上，这个版本内联到单个ia32intrin.h(或ia32intrin.h)，编译器可以使用它，因为编译器知道x86旋转和移位指令以与C源相同的方式屏蔽移位计数。

编译器支持x86上的UB避免习惯用法，ia32intrin.h和__rolb用于变量计数移位：

clang：在clang3.5之后被识别为变量计数旋转，之前是多次移位+或insn。

gcc：自gcc4.9以来可识别的变量计数旋转，在此之前多次移位+或insn。 gcc5和更高版本也在wikipedia版本中优化了分支和掩码，仅使用ia32intrin.h或__rolb指令进行变量计数。

icc：支持自ICC13或更早版本以来的可变计数旋转。 常量计数旋转使用ia32intrin.h，这比某些CPU(特别是AMD，但也有一些Intel)上的速度慢，占用的字节数多于__rolb，当BMI2不可用于__rorb来保存MOV时。

MSVC：x86-64 CL19：仅识别恒定计数旋转。 (维基百科成语被识别，但分支和AND未被优化)。 在x86(包括x86-64)上使用ia32intrin.h/__rolb内部函数来自__rorb。

ARM的gcc使用ia32intrin.h进行可变计数旋转，但仍然使用单个指令进行实际旋转：ia32intrin.h.因此gcc没有意识到旋转计数本质上是模块化的。 正如ARM文档所说，“ROR的移位长度为ia32intrin.h，超过32与ROR相同，移位长度为__rolb”。 我认为gcc在这里很困惑，因为ARM上的左/右移位使计数饱和，因此移位32或更多将清除寄存器。 (与x86不同，其中移位掩盖计数与旋转相同)。 它可能在识别旋转习语之前决定它需要AND指令，因为非循环移位如何对该目标起作用。

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

顺便说一句，更喜欢旋转向右进行可变计数旋转，以避免编译器执行ia32intrin.h以在仅提供旋转右侧的ARM和MIPS等体系结构上实现左旋转。 (这可以通过编译时常量计数来优化。)

有趣的事实：ARM实际上没有专门的移位/旋转指令，它只是MOV，源操作数在ROR模式下通过桶形移位器：ia32intrin.h.因此，旋转可以折叠到EOR指令的寄存器源操作数或一些东西。

确保使用ia32intrin.h的无符号类型和返回值，否则它将不是旋转。 (对于x86目标，gcc会进行算术右移，移位符号位的副本而不是零，当两个移位值一起移位时会导致问题。负有符号整数的右移是C中的实现定义行为。)

此外，确保移位计数是无符号类型，因为带有有符号类型的ia32intrin.h可能是一个补码或符号/幅度，与使用无符号或二进制补码的模块2 ^ n不同。 (参见Regehr博客文章的评论)。 __rolb在我看过的每个编译器上运行良好，每个宽度为__rorb。其他一些类型实际上打败了一些编译器的成语识别，所以不要只使用与__rolw相同的类型。

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

英特尔文件ia32intrin.h提供__rolb和__rorb内在函数，右移也是如此。 MSVC需要ia32intrin.h，而gcc需要__rolb. __rorb处理gcc与icc，但是clang似乎没有提供任何地方，除了在MSVC兼容模式下使用ia32intrin.h.并且它为它们发出的asm很糟糕(额外的屏蔽和 CMOV)。

MSVC：ia32intrin.h和__rolb。

gcc和icc(not clang)：ia32intrin.h还提供__rolb/__rorb，用于向左/向右旋转8位，__rolw/__rorw(16位)，__rold/__rord(32位)，__rolq/__rorq(仅限64位，仅限64位) 为64位目标定义)。 对于窄旋转，实现使用__builtin_ia32_rolhi或…qi，但32位和64位旋转使用shift /或(没有针对UB的保护来定义，因为ia32intrin.h中的代码仅需要在x86上使用gcc)。 GNU C似乎没有像__builtin_popcount那样具有任何跨平台__builtin_rotate功能(它扩展到目标平台上的任何最佳功能，即使它不是单个指令)。 大多数时候，你从成语识别中获得了很好的代码。

// 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

#else

#include // Not just 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代码)，或[http://www.devx.com/tips/Tip/14043]适用于C版本。评论正在回复 那个。)

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