我目前在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位数字，并分别对其进行旋转操作，但有其他有效的方法吗？
您可以在两种模式下使用相同的内存-作为uint_64_t和uint32_t的array[2]。最简单和透明的方式-使用联合：
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位字中的SWAR操作来完成两个32位旋转，使用掩码来避免两个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，它们都生成了基本相同的代码。这种方法很好地推广到对其他子字大小的类似操作(例如，在64位值中移位所有16位字)。如果你想为每个子词使用不同的移位量，这就不太好了(但根据你的例子，你似乎没有这么做)。
让我们将其与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一样，它对较低的DWORD使用rot，但对较高的DWORD使用混合移位，并且在组合结果和保持计算独立方面更聪明。它仍然在做一些愚蠢的事情(缓慢的lea和简单快速的or是怎么回事？)。关键路径(对于上DWORD)是5个周期，我计算了9个uops。
另一方面，icc17也产生了糟糕的代码——相当糟糕的代码：
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个uops。
我手工使用rot的最大努力如下：
mov rax, rdi
shr rax, 32
ror eax, 2
ror edi, 2
sll rax, 32
or rax, rdi
ret
这很简单——使用2条ror指令来旋转顶部和底部DWORD，再加上两次移位来隔离eax中的顶部DWORD并将其向后移动，以及使用or来组合它们。在4个周期时，延迟实际上比shift+mask解决方案更差，但它只有7个uops，比shift和mask少1个。
您也可以尝试组合这些方法，例如，对顶部DWORD使用shift+mask，对底部DWORD使用rot，但我没有得到比上面更好的方法，主要是因为对顶部DWORD执行shift+mask方法并不比对整个事情执行快多少。
总之，假设您实际上不打算编写程序集，我在上面展示的原始C shift+掩码方法具有最短的延迟和最小的uop计数(在手工编译的程序集之外)，并且即使没有ror检测，也应该在各种编译器中都做得很好。它并不取决于编译器对优化联合访问的支持的质量，正如我们在上面看到的那样，这种支持变化很大。
大部分汇编级分析都是以x86为中心的，但大多数分析也适用于其他平台，根据加载大常量的速度和访问64位寄存器的32位子寄存器的能力等，差异较小
1在这个问题中，我在这里和任何地方都做了一个隐含的假设，即旋转两半的量是相同的。这与OP的例子是一致的。如果数量可能不同，则某些解决方案会发生变化。
2特别是插入底部DWORD结果的or rdi, rax使处理高位DWORD的函数的剩余部分取决于前半部分。or实际上是毫无意义的，因为已经有一个最终的or rax, rdx来组合结果。保持结果的独立性，然后在最后将它们组合起来是很容易的——gcc发出的许多掩蔽和组合操作本质上是多余的。