首先,关于原始问题和你提到的后续扩展的观察:
你描述的“移动一点”的操作实际上是一个连续比特范围的旋转。在你的示例中,你将1-5位比特向左旋转了一位:
7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+
| 0 | 1 | 0<
+
| |
+
如果您考虑这个操作的更一般形式是“将一定范围的位向左旋转一定量”,有三个参数:
- 要包括在旋转中的最低有效位
- 要包括在旋转中的最高有效位
- 要旋转的位数
那么它就变成了一个可以执行所有您想做的事情的单个基本原语:
- 您可以显然地移动任何位(选择适当的最低/最高有效位参数);
- 您可以左右旋转,因为如果您旋转n位的范围,则向右旋转k位与向左旋转n - k位相同;
- 它轻松推广到任何位宽度;
- 根据定义,我们可以一次旋转超过一个位。
所以现在,需要做的就是构建这个原语...
首先,我们几乎肯定需要一个位掩码来关心我们关心的位。
我们可以通过将1左移
n+1位,然后减去1来形成0-
n位的掩码。例如,0-5位的掩码将是(二进制):
00111111
...可以通过以下方式来创建:
00000001
将5+1=6位左移:
01000000
...并减去1,得到:
00111111
在 C 语言中,这个表达式是
(1 << (bit + 1)) - 1
。但是这里有一个微妙的问题,至少在 C 语言中存在(尽管你将其标记为与语言无关,我很抱歉会打岔,但这很重要,其他语言可能也存在类似的问题):如果移位的位数等于或超过类型的宽度,则导致未定义的行为。因此,如果我们试图为 8 位类型的位 0-7 构建掩码,则计算结果将为
(1 << 8) - 1
,这将是未定义的。(它可能在某些系统和编译器上有效,但不具备可移植性)。对于带符号类型,在移位到符号位时也存在未定义的行为问题。
幸运的是,在 C 语言中,我们可以通过使用无符号类型,并将表达式写成
(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);
可以通过与掩码进行按位 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;
最终结果可通过组合 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