and*_*ora 5 language-agnostic puzzle bit-manipulation bit
是否有一种优雅的方式在一个字节(或字/长)内移动一点.为简单起见,我们使用一个简单的8位字节,只需一位在字节内移动.
给定一个位数,基于0-7最小sig位到大多数sig位(或者如果你更愿意位1-8位),我想从一个位置移动到另一个位置:
7654 3210 <bit position
0101 1010 <some binary value
--x- --y- <move bit from x to y
0111 0100 <new value with x moved to y and intervening bits shifted left
因此,位位置5处的x在位位置1处移动到y,位0,6,7保持不变.位2,3,4向左移动到"腾出空间",位数从5移动到2.这只是一个例子.
该位移动非常重要,而不是与其目标交换.有许多比特的例子可以互换,但这非常简单.
理想情况下,该解决方案将使用简单的bit-twiddling和bitwise运算符.假设语言不可知,位简单AND/OR/XOR,NOT,SHIFT左/右/ ROTATE或类似指令在任何组合中都可以,加上任何其他基本算术运算符,例如:mod,加/减等.甚至工作伪 - 代码没问题.或者,位阵列或位域类型结构可能很简单.
除了实际的位移动,我想找到一种方法:
性能不是一个主要问题,但优雅的东西可以足够快.
我自己的niaive方法是识别源位和目标位位置,决定是上移还是下移,移位复制,屏蔽静态位并找到源位,合并静态位和移位位并以某种方式设置/清除目标位.然而,虽然理论看起来不错,但优雅的实现却超出了我的范围.
我意识到可以为一个字节构建一个预编译的查找表,但如果要将它扩展为整数/长整数,这对我来说是不切实际的.
任何帮助赞赏.提前致谢.
首先，观察原始问题，以及您提到的后续扩展：
您描述的“移动一点”操作实际上是连续位范围的旋转。在您的示例中，您将 1-5 位（包括 1-5 位）向左旋转一位：
7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| 0 | 1 | 0<--1<--1<--0<--1 | 0 | -> | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
+---+---+-|-+---+---+---+-^-+---+ +---+---+---+---+---+---+---+---+
| |
+---------------+
如果您认为此操作的更一般形式是使用三个参数“旋转一定数量的剩余位范围”：
那么它就变成了一个基本的原语，可以执行你想做的所有事情：
所以现在，所需要的就是构建这个原语......
首先，我们几乎肯定需要为我们关心的位设置位掩码。
我们可以通过将 1向左移动n + 1 位，然后减去 1来形成位 0 - n的掩码。例如，位 0-5 的掩码将是（二进制）：
00111111
...可以通过取 1 来形成：
00000001
...左移 5+1 = 6 位：
01000000
...并减去 1 给出：
00111111
在 C 中，这将是(1 << (bit + 1)) - 1. 但是这里有一个微妙之处，至少对于 C 来说（当你将它标记为与语言无关时，我为离题而道歉，但这很重要，其他语言中也可能存在类似的问题）：您类型（或更多）的宽度会导致未定义的行为。因此，如果我们尝试为 8 位类型的 0-7 位构建掩码，则计算结果将为(1 << 8) - 1，这将是未定义的。（它可能适用于某些系统和某些编译器，但不可移植。）在最终转移到符号位的情况下，签名类型也存在未定义的行为问题。
幸运的是，在 C 中，我们可以通过使用unsigned类型并将表达式编写为来避免这些问题(1 << bit) + (1 << bit) - 1。具有无符号n位值的算术由标准定义为以 2 n为模约简，并且所有单独的运算都是明确定义的，因此我们保证得到正确的答案。
（题外话结束。）
好的，现在我们有了位 0 - msb的掩码。我们想为位lsb - msb制作一个掩码，我们可以通过减去位 0 - ( lsb -1)的掩码来实现，即(1 << lsb) - 1。例如
00111111 mask for bits 0-5: (1 << 5) + (1 << 5) - 1
- 00000001 mask for bits 0-0: (1 << 1) - 1
-------- -------------------------------
00111110 mask for bits 1-5: (1 << 5) + (1 << 5) - (1 << 1)
所以掩码的最终表达式是：
mask = (1 << msb) + (1 << msb) - (1 << lsb);
可以通过位与掩码选择要旋转的位：
to_rotate = value & mask;
...并且可以通过带有反转掩码的 AND 选择将保持不变的位：
untouched = value & ~mask;
旋转本身可以很容易地分为两部分进行：首先，我们可以通过简单地to_rotate向左旋转并丢弃任何落在掩码之外的位来获得旋转部分的最左边的位：
left = (to_rotate << shift) & mask;
要获得最右边的位，请to_rotate 向右旋转( n - shift ) 位，其中n是我们旋转的位数（此n可以计算为msb + 1 - lsb）：
right = (to_rotate >> (msb + 1 - lsb - shift)) & mask;
最终结果可以由所有的位从组合而得到untouched，left和right：
result = untouched | left | right;
您的原始示例将像这样工作（msb是 5，lsb是 1，shift是 1）：
value = 01011010
mask = 00111110 from (1 << 5) + (1 << 5) - (1 << 1)
01011010 value
& 00111110 mask
----------
to_rotate = 00011010
01011010 value
& 11000001 ~mask (i.e. inverted mask)
----------
untouched = 01000000
00110100 to_rotate << 1
& 00111110 mask
----------
left = 00110100
00000001 to_rotate >> 4 (5 + 1 - 1 - 1 = 4)
& 00111110 mask
----------
right = 00000000
01000000 untouched
00110100 left
| 00000000 right
----------
result = 01110100
这是一个不同的示例，其中包含 16 位输入值，msb= 15、lsb= 4 和shift= 4（旋转 4 位十六进制值的前 3 个十六进制数字）：
value = 0101011001111000 (0x5678)
mask = 1111111111110000 from (1 << 15) + (1 << 15) - (1 << 4)
0101011001111000 value
& 1111111111110000 mask
------------------
to_rotate = 0101011001110000
0101011001111000 value
& 0000000000001111 ~mask
------------------
untouched = 0000000000001000
0110011100000000 to_rotate << 4
& 1111111111110000 mask
------------------
left = 0110011100000000
0000000001010110 to_rotate >> 8 (15 + 1 - 4 - 4 = 8)
& 1111111111110000 mask
------------------
right = 0000000001010000
0000000000001000 untouched
0110011100000000 left
| 0000000001010000 right
------------------
result = 0110011101011000 = 0x6758