algorithm - 循环移位的应用

Question

我想知道一些应用循环移位的例子。例如，无符号整数的右移将导致除以二。相反，左移将导致乘以 2。二进制数的循环移位是否有任何著名/有趣的属性。

注意：关于右/左移位的示例是为了说明该特定运算符的应用。我要求循环移位运算符/函数的类似示例。

Answer 1

出现循环变化的一个令人惊讶的地方是约瑟夫斯幸存者问题。在这个有点病态的问题中，n 个人围成一圈。第一个人杀死第二个人，然后第三个人杀死第四个人，以此类推。这个过程重复，一个人杀死下一个人，直到只剩下一个人。问题是给 n 个人，哪个人幸存下来？

令人惊讶的是，答案是通过对 n 进行右循环移位一位来给出的。Graham、Knuth 和 Patashnik 的《具体数学》一书很好地证明了这一点。

希望这可以帮助！

Answer 2

• 在 big-endian 和 little-endian 表示之间转换 16 位字：向右或向左循环移位 8。
• 生成具有偶数位集的随机位集：t = rand(); result = t XOR cshift(t,1).
• 就地、稳定和线性时间：将某个数组中偶数位置的所有元素移到开头，将奇数位置的所有元素移到末尾。本文描述了一种可能的算法：“In-Situ, Stable Merging by the Perfect Shuffle”（第 7 节）。它生成所有可能的二进制项链，并将它们用作循环引导算法的起点，其中每个下一个位置都是通过循环移位从前一个位置计算出来的。2 (mod (2^N - 1))这个应用程序与Henrik 的回答中提到的乘法密切相关。
• 微优化。假设您需要从一个字节中解压缩四个 2 位字。您可以通过将每个子词移动到最右边的位置，然后使用适当的掩码应用 AND 操作来做到这一点。（无需移动第一个子词或屏蔽最后一个子词）。这一切都需要 6 条 CPU 指令。如果将字节循环移位 4，则中间的两个子字成为第一个和最后一个，并且每个也只需要一条指令。因此，使用循环移位将所需指令的数量减少到 5。
• 当机器指令集包含旋转指令时，密码学应用程序会获得显着的加速。例如，Twofish Cipher 广泛使用循环移位。

Answer 3

常规左移是乘以 2 (mod 2^N)，其中 N 是整数类型的位数。

循环左移是乘以 2 (mod (2^N - 1))。所以这在做算术 mod (2^N-1) 时会很方便。