我目前正在使用 C/C++，并且我有一个uint64_t. 我需要分别对顶部 32 位和底部 32 位进行按位旋转。例如，如果我的输入是
| | | |
0000 0000 0000 0000 0000 0000 0000 1101 0000 0000 0000 0000 0000 0000 0000 0111
我需要向右旋转 2 位，正确的输出是
| | | |
0100 0000 0000 0000 0000 0000 0000 0011 1100 0000 0000 0000 0000 0000 0000 0001
显而易见的方法是制作一个临时的 32 位数字并分别对其进行旋转操作，但是有没有一种不同的、有效的方法呢？
您可以在 2 种模式下使用相同的内存 - asuint_64_t和 as array[2]of uint32_t。最简单和透明的方式 - 使用联合：
union U {
uint64_t u64;
uint32_t u32[2];
};
此后，只需使用此联合的字段：
#define ROL(x, n) x = (x << n) | (x >> (32 - n))
U val;
val.u64 = input_val; // Assign 64_bit value to union val
ROL(val.u32[0], 3); // Rotate left by 3 low-part of long int
ROL(val.u32[1], 1); // Rotate left by 1 high-part of long int
当您的语言仅提供移位指令时，执行轮换的规范方法是结合两个移位的结果。例如，要向右旋转 2，您可以使用：
uint32_t y = (x >> 2) | (x << 30);
如果底层平台支持，许多编译器会将此习惯用法识别为旋转，并将发出实际的旋转机器指令（在 x86 上）。ror
您可以以一种直接的方式扩展这个想法，在一个 64 位字内执行两个 32 位旋转SWAR 操作，使用掩码来避免两个 32 位半1之间的污染。
#include <inttypes.h>
const uint64_t leftmask = 0xC0000000C0000000;
const uint64_t rightmask = ~leftmask;
uint64_t rotate2x_32_right_2(uint64_t x) {
uint64_t rightPart = (x >> 2) & rightmask;
uint64_t leftPart = (x << 30) & leftmask;
return rightPart | leftPart;
}
当然，编译器将无法识别这一点并使用旋转，因为 CPU 不提供执行此操作的指令，因此这会产生以下合理的汇编：
rotate2x_32_right_2(unsigned long):
mov rax, rdi
movabs rdx, 4611686015206162431
sal rdi, 30
shr rax, 2
and rax, rdx
movabs rdx, -4611686015206162432
and rdi, rdx
or rax, rdi
ret
我已经针对延迟进行了优化，并且通过完美的调度，在现代 x86 上它可能只需要 3 个周期，它有 4 个不同的关键路径：两个shift -> and -> or和movabs -> and -> or. 在一个循环中，可以提升恒定负载，但延迟仍然是 3（因为其他关键路径仍然存在）。总 uop（不包括ret）计数为 8，现代 x86 上的吞吐量可能高达 2 个周期/迭代，因为所有指令都可以跨多个执行单元发出。
结果并不真正依赖于编译器——我检查了所有的icc，gcc并且clang它们都生成了基本相同的代码。这种方法很好地推广到对其他子字大小的类似操作（例如，将所有 16 位字移动到 64 位值中）。但是，如果您想为每个子词使用不同的移位量，则效果不佳（但根据您的示例，您似乎没有这样做）。
让我们将其与 maxihatop 建议的基于联合的方法进行比较。我稍微修改了该代码以向右旋转而不是向左旋转，并将旋转量固定为 2：
#include <inttypes.h>
union U {
uint64_t u64;
uint32_t u32[2];
};
#define ROR(x, n) x = (x >> n) | (x << (32 - n))
uint64_t rotate2x_32_right_2(uint64_t input_val) {
U val;
val.u64 = input_val; // Assign 64_bit value to union val
ROR(val.u32[0], 2); // Rotate left by 3 low-part of long int
ROR(val.u32[1], 2); // Rotate left by 1 high-part of long int
return val.u64;
}
在 x86 上编译为程序集时它的外观如何？那么现在结果真的取决于编译器。
坚持使用 gcc，我们得到（我的评论）：
rotate2x_32_right_2(unsigned long):
mov eax, edi
movabs rdx, -4294967296
ror eax, 2 ; do the rotate on the bottom half
and rdi, rdx ; mask away the bottom DWORD
or rdi, rax ; insert the bottom DWORD result
mov rax, rdi
shr rax, 32 ; move to top DWORD into the bottom
ror eax, 2 ; do the rotate
sal rax, 32 ; move it back to the top dword
mov rdx, rax ; the next 3 ins awkwardly combine the results
mov eax, edi
or rax, rdx
ret
GCC 已将该ROR操作识别为轮换，并已发出两条ror指令以轮换每一半。不幸的是，还需要十个额外的指令来隔离联合的每一半以准备好ror并将结果移回正确的位置。
此外，它不必要地使底部和顶部旋转相互依赖2。总的来说，据我计算，这导致了一个8 周期的依赖链。延迟比上述解决方案慢得多。我总共计算了 12 个 uops，在一个循环中，这最多可以执行 3 个周期/迭代。
clang 3.9 更智能一些。这是它产生的结果：
rotate2x_32_right_2(unsigned long):
mov eax, edi
rol eax, 30
mov rcx, rdi
shr rcx, 34
shr rdi, 2
and edi, -1073741824
lea ecx, [rcx + rdi]
shl rcx, 32
or rax, rcx
ret
与 gcc 一样，它rot用于较低的 DWORD，但它对较高的 DWORD 使用混合移位，并且在组合结果和保持计算独立方面更聪明。它仍然在做一些愚蠢的事情（慢速lea与简单快速是or怎么回事？）。关键路径（对于上面的 DWORD）是 5 个周期，我数了 9 个微指令。
另一方面，icc 17 也产生了糟糕的代码非常糟糕的代码：
rotate2x_32_right_2(unsigned long):
mov rax, 0xffffffff00000000 #13.3
and rax, rdi #13.3
shld edi, edi, 30 #13.3
or rax, rdi #13.3
mov rdx, rax #12.3
shr rdx, 32 #12.3
mov eax, eax #14.3
shld edx, edx, 30 #14.3
shl rdx, 32 #14.3
or rax, rdx #14.3
ret
出于某种原因，它使用了两个shld reg, reg, i指令，两个 regs 相同，这实际上只是一个rol. 不知道为什么 -shrd说明大多总是较慢或有时与ror. 在 Haswell 和 Skylake 上，它们的延迟为 3，可以在一个端口上发出，而ror延迟为 1，可以在两个端口上发出。在 Sandy Bridge 附近有一段短暂的时间shrd可能会更好 - 它可能会在两个端口上出现延迟 1，而对于ror. 所以也许就是这样。让我们试试 -mtune=haswell：
rotate2x_32_right_2(unsigned long):
mov rax, 0xffffffff00000000 #13.3
and rax, rdi #13.3
rol edi, 30 #13.3
or rax, rdi #13.3
mov rdx, rax #12.3
shr rdx, 32 #12.3
mov eax, eax #14.3
rol edx, 30 #14.3
shl rdx, 32 #14.3
or rax, rdx #14.3
ret #15.10
是的，就是这样。所以英特尔的代码还不错——我的关键路径是 6 条，还有 10 条微指令。
我最好rot的手动使用如下：
mov rax, rdi
shr rax, 32
ror eax, 2
ror edi, 2
sll rax, 32
or rax, rdi
ret
这很简单 - 使用 2ror条指令来旋转顶部和底部 DWORD，加上两个移位来隔离顶部 DWORDeax并将其移回，然后or将它们组合起来。延迟实际上比 4 个周期的 shift+mask 解决方案差，但它只有 7 个 uops，比 shift 和 mask 少 1 个。
您也可以尝试组合这些方法，例如，对顶部的 DWORD 和rot底部的 DWORD 使用 shift+mask，但我没有比上面更好的方法，主要是因为使用 shift+mask 方法top DWORD 并不比整个事情快多少。
总之，假设您实际上不打算编写程序集，我上面展示的原始 C shift+mask 方法具有最短的延迟和最小的 uop 计数（在手动程序集之外），并且应该在各种编译器中表现良好，即使没有被ror发现。它不依赖于编译器对优化联合访问的支持质量，正如我们在上面看到的，差异很大。
大部分汇编级分析都是以 x86 为中心的，但其中大部分也适用于其他平台，根据加载大常量的速度和访问 64 位的 32 位子寄存器的能力存在细微差别位寄存器等。
1在这个问题的各处，我都在隐含假设旋转两半的量是相同的。这与OP的示例一致。如果数量可以不同，则某些解决方案会发生变化。
2特别是or rdi, rax插入底部 DWORD 结果的函数使处理高 DWORD 的函数的其余部分依赖于前半部分。这or实际上是毫无意义的，因为已经有一个决赛or rax, rdx来组合结果。保持结果独立然后在最后将它们组合起来很容易 - gcc 发出的许多屏蔽和组合操作本质上是多余的。