使用位域或位运算符在一个字节内移动一点
有没有一种在字节（或字/长）内移动一点的优雅方式。 为了简单起见，我们使用一个简单的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被左移到'make room'，位从5移到2.这只是一个例子。
位移动非常重要，不要与其目标交换。 有很多位交换的例子，但这是相当微不足道的。
理想情况下，解决方案将使用简单的位操作和位操作符。 假设语言是不可知的，有点简单AND / OR / XOR，NOT，SHIFT左/右/ ROTATE或类似的指令在任何组合中都可以，加上任何其他基本的算术运算符，例如：mod，加/减等。即使工作psuedo-代码会好的。 或者，位阵列或位域类型结构可能很简单。
除了实际的位移之外，我想找到一种方法来：
性能不是主要问题，但优雅的东西可能足够快。
我自己的方法是识别源位和目标位，决定是否向上或向下移位，取一个移位副本，遮蔽静态位并找到源位，合并静态位和移位位，并以某种方式设置/清除目标位。 但是，虽然理论看起来不错，但优雅的实现是超越我的。
我意识到可以为一个字节构建一个预编译的查找表，但是如果这要扩展为整数/多个，这对我来说是不切实际的。
任何帮助赞赏。 提前致谢。
首先，观察一下原始问题以及您提到的后续扩展：
您所描述的“移动一点点”操作实际上是一个连续范围的位的旋转。 在你的例子中，你正在将位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 + 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位值的算术由标准定义为模2n减少，并且所有单独的操作都是定义良好的，所以我们保证得到正确的答案。
（离题结束。）
好的，现在我们有一个掩码，用于位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位移）位，其中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
这是C中的一个工作实现，它没有高度优化，但至少可以作为任何进一步实现的起点。 它适用于整数，但可以适应任何字大小，或者按原样使用它，并掩盖任何不需要的高位（例如，如果您使用单个字节）。 我将功能分解为两个较低级别的例程，用于提取一点并插入一点 - 我想可能还有其他用途。
//
// bits.c
//
#include <stdio.h>
#include <stdlib.h>
//
// extract_bit
//
// extract bit at given index and move less significant bits left
//
int extract_bit(int *word, int index)
{
int result = (*word & (1 << index)) != 0;
int mask = (1 << index) + (1 << index) - 1;
*word = ((*word << 1) & mask) | (*word & ~mask);
return result;
}
//
// insert_bit
//
// insert bit at given index and move less significant bits right
//
void insert_bit(int *word, int index, int val)
{
int mask1 = (1 << index) + (1 << index) - 1;
int mask2 = (1 << index) - 1;
*word = ((*word >> 1) & mask2) | (*word & ~mask1) | (val << index);
}
//
// move_bit
//
// move bit from given src index to given dest index
//
int move_bit(int *word, int src_index, int dest_index)
{
int val = extract_bit(word, src_index);
insert_bit(word, dest_index, val);
return val;
}
int main(int argc, char * argv[])
{
if (argc > 2)
{
int test = 0x55555555;
int index1 = atoi(argv[1]);
int index2 = atoi(argv[2]);
printf("test (before) = %#xn", test);
printf("index (src) = %dn", index1);
printf("index (dest) = %dn", index2);
move_bit(&test, index1, index2);
printf("test (after) = %#xn", test);
}
return 0;
}
这可能不符合“优雅”的要求，但如果这是你的事情，你可能会把它塞进一行。 这个计划是把这个数字分成四块（不应该用硬块操作，对不对？），对它们做适当的事情，然后把这三块重新放在一起。
Number: 01x1 10y1
P1 (before x): 0100 0000
P2 (just bit x): 00x0 0000
P3 (between x and y): 0001 10y0
P4 (after y): 0000 0001
然后你想要的数字是[P1] + [P3 shifted up by 1] + [P2 shifted down by 4] + [P4] 。
P1: 0100 0000
P2 shifted down by 3: 0000 00x0
P3 shifted up by 1: 0011 0y00
P4: 0000 0001
Sum: 0111 0yx1
上一篇: Moving a bit within a byte using bitfield or bitwise operators