循环移位的应用

Question

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

注意:右/左移位的示例是说明该特定运算符的应用.我要求循环移位操作符/功能的类似示例.

Answer 1

圆形变换出现的一个令人惊讶的地方是约瑟夫斯幸存者问题.在这个略带病态的问题中,n个人围成一圈.第一个人杀死第二个,然后第三个人杀死第四个,等等.这个过程重复,一个人杀死下一个人,直到只剩下一个人.问题是n人,哪个人幸存？

令人惊讶的是,通过在n上进行正确的循环移位来给出答案.在Graham,Knuth和Patashnik的书" 混凝土数学"中有很好的证明.

希望这可以帮助!

Answer 2

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