给定一个位数,基于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,加/减等.甚至工作伪 – 代码没问题.或者,位阵列或位域类型结构可能很简单.
除了实际的位移动,我想找到一种方法：
>向上或向下移动任何位.
>以任何方便的格式指定位号源/目的地：例如：6> 2
意味着向下移位,3> 7向上移位或开始位/ – 偏移：6-4或3 4,或位加权：位6 = 64到位3 = 8.
>可能从byte扩展到unsigned int,long等.
>(理想情况下,可以扩展
一次多于一位,如果更容易可能相邻位
性能不是一个主要问题,但优雅的东西可以足够快.
我自己的niaive方法是识别源位和目标位位置,决定是上移还是下移,移位复制,屏蔽静态位并找到源位,合并静态位和移位位并以某种方式设置/清除目标位.然而,虽然理论看起来不错,但优雅的实现却超出了我的范围.
我意识到可以为一个字节构建一个预编译的查找表,但如果要将它扩展为整数/长整数,这对我来说是不切实际的.
任何帮助赞赏.提前致谢.
首先,观察一下原始问题以及您提到的后续扩展：您描述的“移动位”操作实际上是连续位的旋转.在您的示例中,您将位旋转为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 |
+---+---+-|-+---+---+---+-^-+---+ +---+---+---+---+---+---+---+---+
| |
+---------------+
如果您认为此操作的更一般形式是“使用一些数量旋转一系列位”,则使用三个参数：
>要包含在旋转中的最低有效位
>包含在旋转中的最重要的位
>要旋转的位数
然后它成为一个单一的基本原语,可以执行你想要做的所有事情：
>你显然可以移动任何一点(选择适当的最小/最重要的位参数);
>你可以向左或向右旋转,因为如果你正在旋转n位的范围,那么右旋转k位与n-k位左旋转是一回事;
>它简单地推广到任何位宽;
>根据定义,我们可以一次旋转多个位.
所以现在,所需要的就是构建这个原语……
首先,我们几乎肯定需要为我们关心的位掩盖一些掩码.
我们可以通过向左移位1乘n 1位来形成位0-n的掩码,然后减去1.位0-5的掩码将是(二进制)：
00111111
…可以通过1：
00000001
…左移5 1 = 6位：
01000000
…并减去1给出：
00111111
在C中,这将是(1<<<(bit 1)) - 1.但是这里有一个微妙的,至少对于C来说(当你将这个标记为与语言无关时,我为这个题外话道歉,但是这很重要,并且在其他语言中也可能存在类似的问题)：按类型宽度(或更多)的移动会导致未定义的行为.因此,如果我们试图为8位类型的0-7位构造掩码,则计算将是(1 << 8)-1,这将是未定义的. (它可能适用于某些系统和某些编译器,但不可移植.)在最终转移到符号位的情况下,签名类型也存在未定义的行为问题. 幸运的是,在C中,我们可以通过使用无符号类型来避免这些问题,并将表达式写为(1<<< bit<<<<" bit) - 1.具有无符号n位值的算术由下式定义：模数减少的模数为2n,并且所有单独的操作都是明确定义的,因此我们保证得到正确的答案. (离题结束.) 好的,现在我们有一个0位msb的掩码.我们想为比特lsb-msb做一个掩码,我们可以通过减去比特0-(lsb-1)的掩码来做,这是(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);
可以通过与掩码的按位AND选择要旋转的位：
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;
最后的结果可以通过组合来自未触及,左和右的所有位来获得：
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