问循环移位的应用

EN

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

圆周运动出现的一个令人惊讶的地方是约瑟夫斯幸存者问题。在这个有点病态的问题中，n人站成一个圆圈。第一个人杀死第二个人，然后第三个人杀死第四个人等等。这个过程重复着一个人杀死下一个人，直到只剩下一个人。问题是问n人，哪个人活下来了？

令人惊讶的是，答案是在n上做一个正确的循环移位。在Graham，Knuth和Patashnik的“具体数学”一书中有一个很好的证明。

希望这能有所帮助！

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

一个圆形左移位是2 (mod (2^n-1))的乘积。因此，在执行算术模(2^N-1)时，这是很方便的。