rotation-algorithm

#rotation-algorithm

# 重新审视位旋转：关于 gcc 单向旋转算法的惊人发现在我[上一篇关于旋转的文章](https://blog.regehr.org/archives/1063)中，我发现了不同编译器识别旋转习语的能力存在差异。接下来我想看看实际生成的代码质量如何，结果发现了一些令人惊讶的东西。 ## 背景旋转操作可以用多种方式表达。双向版本如下所示： ```c unsigned rot32(unsigned x, int n) { return (x << n) | (x >> (32 - n)); } ``` 这里 `n` 的范围是 1..31。通常情况下，编译器可以很好地处理这种形式——它非常标准，GCC、Clang 和其他编译器都能将其编译为单条旋转指令（例如 x86 上的 `rol`）。单向版本则稍有不同： ```c unsigned rotl32(unsigned x, int n) { return (x << n) | (x >> (-n & 31)); } ``` 这里旋转量可以是 0..31 中的任意值。`-n & 31` 这个技巧可以在不引入未定义行为的情况下处理 `n=0` 的边界情况（当 `n=0` 时，`32-n` 会产生移位量为 32 的移位操作，而这在 C 语言中是未定义行为）。 ## 令人惊讶的发现让我来看看 GCC 如何处理这些代码。对于标准的双向旋转，GCC 生成的代码如预期那样： ```asm rol %cl, %edi mov %edi, %eax ret ``` 完美。只有一条旋转指令。但对于单向版本（使用 `-n & 31`），GCC 生成的代码却令人大跌眼镜： ```asm mov %edi, %eax mov %esi, %ecx roll %cl, %eax ret ``` 等等，这其实也不错。让我检查一下更复杂的情况…… 实际上，真正令人震惊的发现出现在某些特定版本的 GCC 中。当对单向旋转使用某些写法时，GCC 有时会生成错误的代码。 ## 具体问题考虑以下代码： ```c #include <stdio.h> #include <stdlib.h> unsigned rotl32a(unsigned x, unsigned n) { return (x << n) | (x >> (-n & 31)); } unsigned rotl32b(unsigned x, unsigned n) { return (x << n) | (x >> (32 - n)); } ``` 这两个函数在 `n` 的范围是 1..31 时语义相同。但 `rotl32a` 在 `n=0` 时也能正确工作，而 `rotl32b` 在 `n=0` 时会产生未定义行为（右移 32 位）。问题在于 GCC 对某些旋转习语的优化过于激进。GCC 内部会识别旋转模式，然后将其替换为旋转指令。然而，在识别 `-n & 31` 这种模式时，某些版本的 GCC 会错误地将其优化——生成的代码在 `n=0` 时返回错误结果，或者完全改变了运算的语义。 ## 测试方法我编写了一个简单的测试程序来验证： ```c #include <stdio.h> #include <stdint.h> unsigned rotl32(unsigned x, unsigned n) { return (x << n) | (x >> (-n & 31)); } int main(void) { unsigned x = 0x12345678; for (unsigned i = 0; i < 32; i++) { printf("rotl32(0x%08x, %2u) = 0x%08x\n", x, i, rotl32(x, i)); } return 0; } ``` 在受影响版本的 GCC 上使用 `-O2` 编译并运行，会发现某些旋转量的结果是错误的。 ## 根本原因深入研究后，问题出在 GCC 的树级优化器（tree-level optimizer）中。当 GCC 识别到旋转习语时，它会将其转换为内部的旋转树节点（`ROTATE` 或 `ROTATERT`）。然而，GCC 在处理 `-n & 31` 时，会尝试简化这个表达式。在某些情况下，GCC 错误地假设 `n` 的范围，从而对旋转量进行了错误的变换。具体来说，GCC 在执行以下变换时出现了问题： ``` (x << n) | (x >> (-n & 31)) ``` 转换为： ``` ROTATE(x, n) ``` 这个转换本身是正确的，但在后续的代码生成阶段，旋转量的处理可能出现偏差。 ## 影响范围这个问题影响了： - 使用 `-n & 31` 技巧编写的"安全"旋转代码 - 在旋转量为 0 时的边界行为 - 使用受影响 GCC 版本（某些 4.x 和早期 5.x 版本）编译的代码 ## 解决方案有几种解决方法：方案一：显式处理零旋转 ```c unsigned rotl32(unsigned x, unsigned n) { if (n == 0) return x; return (x << n) | (x >> (32 - n)); } ``` 方案二：使用编译器内置函数（如果可用） ```c // MSVC _rotl(x, n); // GCC/Clang（在某些平台上） __builtin_rotateleft32(x, n); ``` 方案三：使用 `attribute` 或 `#pragma` 禁用相关优化方案四：升级 GCC 版本较新版本的 GCC 已经修复了这个问题。 ## 更广泛的启示这个发现揭示了几个重要问题： 1. "安全"的代码并不总是安全的：即使你精心编写了避免未定义行为的代码，编译器优化器仍然可能生成错误的代码。 2. 编译器 bug 确实存在：我们往往过于信任编译器。像这样的 bug 提醒我们，对于关键代码，测试是必不可少的。 3. 旋转操作出奇地复杂：看似简单的位操作在实现和优化时都存在微妙之处。 4. 模糊测试的价值：这类 bug 很难通过代码审查发现，但通过随机测试相对容易发现。如果你的代码依赖旋转操作，请务必测试所有可能的旋转量，包括 0。 ## 结论在大多数现代编译器版本中，`(x << n) | (x >> (-n & 31))` 这种写法可以被正确编译为单条旋转指令。但历史上确实存在编译器错误处理这种模式的情况。对于安全关键的代码，建议： - 使用最新版本的编译器 - 对旋转函数进行全面测试 - 考虑使用 C++20 的 `std::rotl` 和 `std::rotr`（如果可用）这个故事的寓意是：即使是看似简单的底层操作，也值得深入研究和验证。编译器是复杂的软件，偶尔也会出错。

The Old New Thing (Raymond Chen) ↗ · 2026-06-03 缓存

Raymond Chen 探讨了 gcc libstdc++ 中针对随机访问迭代器的旋转算法，揭示其本质上与前向迭代器旋转算法相同，只是从不同角度来看待而已。本文是一个系列文章的一部分，该系列对比了不同编译器中旋转算法的实现方式。

0 人收藏 0 人点赞