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

Question

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

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

在这里向右旋转两次

Initial --> 1000 0011 0100 0010

应该导致：

 Final   --> 1010 0000 1101 0000

一个例子会很有帮助。

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

原文由 Elroy 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

另请参阅 另一个旋转问题的此答案 的早期版本，其中包含有关 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 uint16_t & uint16_t is promoted to signed int by C++’s integer-promotion rules, except on platforms where int is no wider than uint16_t .

---

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

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

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

ARM 的 gcc 使用 and r1, r1, #31 进行可变计数旋转，但实际旋转仍然使用一条指令： 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> 。一个 #ifdef 负责处理 gcc 与 icc。 Clang 9.0 也有它，但在此之前它似乎没有在任何地方提供它们， 除了在 MSVC 兼容模式下与 -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 。它为他们发出的 asm 很糟糕（额外的掩蔽和 CMOV）。
• MSVC： _rotr8 和 _rotr16 。
• gcc and icc (not clang): <x86intrin.h> also provides __rolb / __rorb for 8-bit rotate left/right, __rolw / __rorw (16-bit), __rold / __rord (32-bit), __rolq / __rorq (64 -bit，仅针对 64 位目标定义）。对于窄轮换，实现使用 __builtin_ia32_rolhi 或 ...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 。

原文由 AndreasT 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

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

该提案说：

标题：

 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 位整数中设置的位数？

原文由 Ciro Santilli OurBigBook.com 发布，翻译遵循 CC BY-SA 4.0 许可协议