循环移位的应用 [英] Applications of a circular shift

问题描述

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

I would like to know some examples of application of circular shifts. For example, a right shift on an unsigned integer would result in a division by two. Conversely, a left shift would result in a multiplication by 2. Are there any famous/interesting properties of a circular shift on binary numbers.

注意:关于左右移位的示例是为了说明该特定运算符的应用.我要求提供用于循环移位运算符/功能的相似示例.

Note: The example about the right/left shift is to illustrate an application of that particular operator. I am asking for similar examples for the circular shift operator/function.

推荐答案

• 在big-endian和little-endian表示形式之间转换一个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广泛使用循环移位.
• Convert a 16-bit word between big-endian and little-endian representation: right or left circular shift by 8.
• Generate random bitset with even number of bits set: t = rand(); result = t XOR cshift(t,1).
• In-place, stable, and in linear time: move all elements of some array with even positions to the beginning and all elements with odd positions - to the end. One of possible algorithms is described in this paper: "In-Situ, Stable Merging by way of the Perfect Shuffle" (section 7). It generates all possible binary necklaces and uses them as starting points of cycle-leader algorithm where each next position is computed from previous one by circular shift. This application is closely related to multiplication by 2 (mod (2^N - 1)) mentioned in Henrik's answer.
• Micro-optimization. Suppose you need to unpack four 2-bit words from a single byte. You could do this by shifting each sub-word to rightmost position, then applying AND operation with proper mask. (No need to shift the first sub-word or mask the last one). All this needs 6 CPU instructions. If you circularly shift the byte by 4, two middle sub-words become the first and the last one, and also need only one instruction each. So using circular shift decreases number of needed instructions to 5.
• Cryptography applications receive significant speed-up when machine instruction set contains rotation instructions. For example, Twofish Cipher uses circular shifts extensively.

这篇关于循环移位的应用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！