x86中的旋转指令（ROL，RCL）有什么作用？

Question

我一直想知道一些CPU上具有旋转指令（例如x86上的ROL、RCL）的目的是什么。有哪些软件会使用这些指令呢？

起初，我认为它们可能用于加密/计算哈希代码，但这些库通常是用C编写的，而C没有将运算符映射到这些指令中。(编辑说明：请参见C++中循环移位（旋转）操作的最佳实践，了解如何编写可编译为旋转指令的C或C++。此外，优化后的加密库通常确实具有特定平台的汇编代码。)

有人发现过它们的用途吗？它们为什么被添加到指令集中？

- Gratian Lup

---

一个好的C编译器在编译尝试使用C运算符计算旋转的代码（即(x << 12) | (x >> 20)）时，会发出rol操作码。 - Thomas Pornin

@Brian：我写的是rol，我的意思是rol（好吧，也可能是ror）。旋转操作码。 - Thomas Pornin

@Thomas 我的 C 语言有点生疏，我一直以为 << 和 >> 运算符是移位而不是旋转。 - Brian Knoblauch

@Brian说：<< 和 >> 是位移操作。但对于一个32位的值 x，整个表达式 (x << 12) | (x >> 20) 包含两个位移操作（一个左移，一个右移）和一个按位或操作，其效果相当于将一个32位字（在这里向左旋转12位）。C编译器足够聪明，能够注意到这一点，并将整个表达式编译为单个 rol 指令。 - Thomas Pornin

一些库具有位旋转内置函数，但我认为C应该首先具有旋转运算符。这将使代码理解更容易，编译器的工作量也会减少。 - phuclv

Answer 1

对于跨越多个字的位移操作，需要进行旋转操作。当通过SHL移动低位时，高阶位溢出到进位标志CF中。为了完成操作，需要将高位字移位同时将进位带入低位。RCL指令可以完成此操作。

                      高位字            低位字         CF
初始值          0110 1001 1011 1001   1100 0010 0000 1101    ?
SHL低位字     0110 1001 1011 1001   1000 0100 0001 1010    1
RCL高位字    1101 0011 0111 0011   1000 0100 0001 1010    0

ROL和ROR用于以最终非破坏性方式逐位检查值。它们也可用于在不引入垃圾位的情况下移动掩码。

- Nietzche-jou

---

什么情况下应该使用旋转来测试位，而不是使用 BT？ - Gabe

当你想要测试它们全部，可能还是按顺序进行。 - Nietzche-jou

或者，当你一开始就没有BT时。 - Nietzche-jou

旋转只有在移动1位时才有效。 - phuclv

第三步后，CF不会变成0吗？（离开的位被设置为CF，并将CF的先前值插入到最右侧位置） - Assad Ebrahim

在汇编语言中，这些指令由助记符表示，例如ADD / SUB，ADC / SBC（包括进位的ADD / SUB），SHL / SHR（位移），ROL / ROR（位旋转），RCR / RCL（通过进位旋转）等等。[1] 在这种方式下使用进位标志使得多字加法、减法、移位和旋转操作成为可能。 - phuclv

Answer 2

旋转移位指令 ROL、RCL、ROR 和 RCR 几乎完全用于哈希和 CRC 计算。它们相当晦涩，很少使用。

移位操作码（SHL、SHR）用于快速乘以2的幂，或将低字节移动到大寄存器的高字节中。

ROL 和 SHL 的区别在于 ROL 获取高位并将其滚动到低位位置。SHL 放弃高位，并用零填充低位位置。

- dthorpe

---

我不明白你是如何回答这个问题的。 - Gabe

也许你可以在回答中添加ROL/RCL和ROR/RCR之间的区别。 - Jeroen Wiert Pluimers

相当古怪和很少使用？真的吗？旋转在许多地方都非常有用，特别是在哈希和加密中。在许多CPU上，移位量影响时间，实际上旋转和按位与比进行移位更快。 - The Welder

是的，很少使用。哈希和加密是应该从库中使用的东西，而不是每个开发人员都应该自己编写的东西。 - dthorpe

请注意，从 CPU 设计的角度来看（提供哪些指令），相关的衡量标准是它（或将）执行 的频率，而不是包含该指令的软件数量。这并不难模拟（与一些特殊用途指令（如 popcnt 或 crc32 或 SIMD psadbw 不同，后者基本上是为视频编码运动搜索添加的），但另一方面，使旋转位移器能够旋转并不需要太多额外的硬件。 - Peter Cordes

ROR 可以在某些排序过程中用于交换相邻内存中的值。效果非常好。 - JeffW

Answer 3

ROR和ROL是“历史悠久”的指令，但在许多方面仍然很有用。

在80386（和操作码BT）之前，ROL经常用于测试一个位（SHL不会传播到进位标志）- 实际上，在8088中，ROR/ROL每次只能移动1个位！

此外，如果您想要先向一侧移位，然后再向另一侧移位而不失去已超出范围的位，则应使用ROR/ROL，而不是SHR/SHL。

- Alain Pannetier

---

而且8080甚至没有移位指令——旋转就是你所拥有的全部！ - Gabe

如果您使用立即旋转计数，则在8088上只能旋转一个。但是，8088也支持通过寄存器cl中给定的计数进行旋转。（除1以外的立即字节移位/旋转计数是在186指令集中添加的。） - ecm

ROL和SHL一样，根据移出高位的最后一位来设置CF。唯一的区别是ROL会将底部的位移进来，而不是移入0。与旋转指令不同，SHL像普通ALU指令一样设置SF、ZF和PF。 - Peter Cordes

Answer 4

如果我理解正确，你的问题是：“考虑到旋转指令似乎非常专用且不被编译器发出，那么它们实际上何时使用以及为什么包含在CPU中？”回答有两个方面：

1. CPU并非专门设计用于执行C程序。相反，它们被设计为通用机器，旨在使用各种不同的工具和语言解决各种问题。

2. 语言的设计者没有义务使用CPU中的每个操作码。事实上，大多数情况下，他们不会这样做，因为某些CPU指令非常专业化，而语言设计者没有迫切需要使用它们。

有关位运算符（以及它们与C编程的关系）的更多信息可以在此处找到：http://en.wikipedia.org/wiki/Bitwise_operation

- Robert Harvey

Answer 5

早期的微处理器时代，大部分程序都是采用汇编语言编写而非编译。大多数CPU指令可能并不是由编译器发出（这也是创建RISC的动力所在），但通常相对容易在硬件中实现。

图形学和密码学中的许多算法使用旋转，它们被包括在CPU中，可以在汇编中编写非常快速的算法。

- Gabe

Answer 6

我认为很多答案都有些颠倒了，包括目前被接受的答案。最大的应用是在跨字节/字边界移动数据中，这在以下方面得到广泛应用：

- 提取和插入位模式 - 协议（从第6位开始插入5位） - 压缩方案（LZW77等） - 数据传输（300波特调制解调器？7位数据+奇偶校验） - 任意精度算术 - 乘以/除以2使用旋转进位 - 乘以/除以其他2的幂需要ROL（或ROR） - 水平滚动1位图形 - 小众应用： - crc16/32 - 密码 - 非破坏性地将位移动到符号位或进位进行测试

历史背景是移位操作很耗费资源：当需要将16位左移3位时，以8位（或64位）为一组，一个ROL执行两次昂贵的移位操作。

rotate all bits left by 3
      hi       lo
src = fedcba98|76543210
dst = cba98765|43210---

注意，位“765”需要向右移动5位，而位“43210”需要向左移动3位。这可以通过一个旋转来完成，将所有正确的位放到正确的位置，即使它们与错误的位一起出现，也可以通过掩码重新组合，这是一种廉价的操作：

dst_lo = ((src_lo ROL 3) & 0b11111000)
dst_hi = ((src_lo ROL 3) & 0b00000111) | (src_hi << 3)

这也适用于大整数移位，或通过任意数量的像素水平滚动单色图形平面。

这个算法非常重要，以至于80386为此包含了一个双旋转指令。

- Aki Suihkonen

---

许多CPU都有一个通过Carry标志旋转的功能，如果您只能一次移动1位，则可以用于等效目的。这也使得使用循环跨寄存器边界进行可变计数移位成为可能，而使用ROL则需要另一个移位（和NOT）来创建这些掩码。尽管如此，在具有比循环更快但仍然缓慢的多位移位的机器上，对于常量移位计数，这仍然是一个有趣的观点（例如8086）。但是，您应该优化为src_hi << 3而不是ROL + mask，因为在那里移出的位没有被移入任何东西中。 - Peter Cordes

是的，拥有破坏性变体（算术和逻辑右移/逻辑左移）对于需要它们的情况绝对值得；而且最后一个字会受益于这些指令。我想在编辑之前将该概念扩展到真正的多字移位。 - Aki Suihkonen