c++ - 如何高效实现任意序列的按位旋转？

Question

“由索引排列 p(i) = (i + k) mod n 定义的 n 个元素的排列 p 称为 k-旋转。” -- Stepanov & McJones

由于 Sean Parent，

std::rotate 已成为众所周知的算法，但是如何针对任意位序列有效地实现它呢？我所说的高效是指至少减少两件事，i) 写入次数和 ii) 最坏情况下的空间复杂度。

也就是说，输入应该类似于 std::rotate 但按位特定，我想是这样的:

1. 指向位序列开始的内存的指针。
2. 三位索引:first、middle 和last。

指针的类型可以是任何无符号整数，而且应该越大越好。 (Boost.Dynamic Bitset 称之为“ block ”。)

重要的是要注意索引可能都从 block 的开头偏移不同的量。

根据 Stepanov 和 McJones 的说法，随机访问数据的轮换可以在 n + gcd(n, k) 分配中实现。反转每个子范围然后反转整个范围的算法需要 3n 个分配。 (但是，我同意下面的评论，它实际上是 2n 个赋值。)由于数组中的位可以随机访问，我假设适用相同的最佳界限。由于不同的子范围 block 偏移，每个赋值通常需要两次读取，但我更关心读取而不是写入。

这个算法的有效或最佳实现是否已经在开源领域存在？如果没有，怎么办？

我查看了 Hacker's Delight 和 Knuth 的第 4A 卷，但找不到适合它的算法。

Answer 1

使用 vector<uint32_t> ，例如，自己一次完成旋转的小数元素部分 (shift_amount%32)，然后调用 std::rotate 是简单且相当有效的做剩下的事。小数部分很简单，只对相邻元素进行运算，末尾除外，因此您在工作时只需记住一个部分元素。

如果你想自己做整个事情，那么你可以通过颠倒整个 vector 的顺序来进行旋转，然后颠倒前后部分的顺序。有效执行此操作的诀窍是，当您反转整个 vector 时，您实际上并没有对每个元素进行位反转——您只是认为它们的顺序相反。前后部分的反转比较棘手，需要您在工作时记住 4 个部分元素。

在写入内存或缓存方面，以上两种方式都是2N次写入。您在问题中提到的最佳轮换需要 N，但如果您将其扩展为使用小数字轮换，那么每次写入跨越两个字，然后需要 2N写。它没有任何优势，我认为它会变得很复杂。

就是说...我敢肯定，通过一次执行 m 个字，您可以使用固定数量的寄存器存储来接近 N 次写入，但那是虽然有很多用于简单轮换的代码，但您的时间(或者至少是我的时间 :) 最好花在其他地方。