使用位域或位操作移动一个字节中的位 [英] Moving a bit within a byte using bitfield or bitwise operators
问题描述
有一个字节（或字/长期）内移动了一点优雅的方式。为简单起见，让我们用一个简单的8位字节，只是一个比特字节内移动。
Is there an elegant way of moving a bit within a byte (or word/long). For simplicity, lets use a simple 8-bit byte and just one bit to move within the byte.
定的位编号，根据0-7最小-SIG位最-SIG位（或1-8位，如果您愿意），我想从一个位置移动了一点到另一
Given a bit number, based on 0-7 Least-sig-bit to most-sig-bit, (or bits 1-8 if you'd rather), I would like to move a bit from one position to another:
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
因此中，x位位置5移动到y在第1位，位0,6,7保持不变。位2,3,4左移，以腾出空间的位5移到2。这仅仅是一个例子。
So, x at bit position 5 moves to y at bit position 1, bits 0,6,7 stay unchanged. Bits 2,3,4 are shifted left to 'make room' for the bit moved from 5 to 2. This is just an example.
重要的是该位移动时，不与目标交换。有迹象表明，比特交换众多exampls，但是那是相当的简单。
It is important that the bit moves, not swapped with its target. There are numerous exampls of bits that swap, but that is quite trivial.
解决方案理想是用简单的位变换和位运算符。假设语言无关的，有点简单AND / OR / XOR，NOT，SHIFT左/右/旋转或类似的指令将任意组合的罚款，以及任何其他基本算术运算符，如：MOD，加/减等。即使工作psuedo- code将是确定的。另外，有点数组或位字段类型的结构很可能是直接的。
The solution ideally would use simple bit-twiddling and bitwise operators. Assume language agnostic, bit simple AND/OR/XOR, NOT, SHIFT Left/Right / ROTATE or similar instructions would be fine in any combination, plus any other basic arithmetic operator, eg: mod, addition/subtraction etc. Even working psuedo-code would be ok. Alternatively, a bit array or bitfield type structure would probably be straightforward.
在除了实际位的举动，我想找到一种方法：
In addition to the actual bit move, I would like to find a way to :
- 上下移动任何位。
- 指定任何方便的格式位号源/目的：例如：6> 2
6 = 64位至第3位= 8：意味着向下移动，3> 7移位或启动位+/-偏移：6-4或3 + 4或位加权。 - 从字节可能扩展到为unsigned int，long等等
- （理想情况下，可扩展的
要一次一个以上的位，大概相邻位，如果更容易）
性能不是一个大问题，但有些事是优雅likley要足够快足够了。
Performance is not a major issue, but something elegant is likley to be plenty fast enough.
我自己niaive的做法是，以确定源和目标位的位置，决定是否或上移下来，采取转移副本，屏蔽掉静态位，找到源头位，合并静态和移位，莫名其妙定置/清除目标位。然而，虽然理论上似乎不错，优雅的实现是超越我。
My own niaive approach would be to identify the source and target bit positions, decide if shift up or down, take a shifted copy, mask off the static bits and find the source bit, merge the static and shifted bits and somehow set/clear the target bit. However, while the theory seems good, an elegant implementation is beyond me.
我认识到，一个precompiled查找表可以以字节为单位建造，但如果这是要延伸到整数/多头，这将是不切实际的我。
I realise that a precompiled lookup table could be built for a byte, but if this is to be extended to integers/longs, this would be impractical for me.
任何帮助AP preciated。先谢谢了。
Any help appreciated. Thanks in advance.
推荐答案
首先，对原问题的观察，你提到后续扩展：
First, an observation about the original problem, and the subsequent extensions that you mention:
这是您所描述的动了一下的操作实在是位连续范围的旋转。在你的榜样，你的旋转位1-5包容性，一个位向左：
The "moving a bit" operation that you describe is really a rotation of a contiguous range of bits. In your example, you are rotating bits 1-5 inclusive, by one bit to the left:
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 |
+---+---+-|-+---+---+---+-^-+---+ +---+---+---+---+---+---+---+---+
| |
+---------------+
如果您认为这是操作的更一般的形式是旋转的范围内一定量左位有三个参数：
If you consider a more general form of this operation to be "rotate a range of bits left by some amount" with three parameters:
- 最低显著位在转动 包括
- 最显著位在旋转包括
- 的位数由旋转
那么它就变成一个基本的原始，能执行的你想要做的事情全部的：
then it becomes a single basic primitive which can perform all of the things you want to do:
- 您可以明显地将任何位（选择合适的最小/最大显著位PARAMATERS）;
- 您可以因为如果你旋转范围旋转左或右，的 N 的位，然后向右旋转的 K 的位是同样的事情作为一个旋转左通过的 N 的 - K 的位;
- 这平凡的可以推广到任何位宽;
- 的定义，我们可以一次旋转超过一位以上。
- you can obviously move any bit (choose appropriate least/most significant bit paramaters);
- you can rotate left or right, because if you are rotating a range of n bits, then a rotation right by k bits is the same thing as a rotation left by n - k bits;
- it trivially generalises to any bit width;
- by definition we can rotate more by more than one bit at a time.
所以，现在，所有需要的是构建这种原始...
So now, all that's needed is to construct this primitive...
要开始，我们几乎肯定会需要我们关心的比特位掩码。
To start with, we're almost certainly going to need a bit mask for the bits we care about.
我们可以形成位0面具 - 的 N 的通过的 N 的+ 1位移位1到左侧，然后减去1。如对于0-5位掩码是（二进制）：
We can form a mask for bits 0 - n by shifting a 1 by n + 1 bits to the left, then subtracting 1. e.g. a mask for bits 0-5 would be (in binary):
00111111
...可以通过采取可形成1：
...which can be formed by taking a 1:
00000001
...移5 + 1 = 6位向左
...shifting 5+1 = 6 bits to the left:
01000000
...并减去1给：
...and subtracting 1 to give:
00111111
在C，这将是（1 LT;≤（位+ 1）） - 1 。但是有一个微妙这里，对于C，至少（我的题外话道歉，当你标记这是语言无关，但是这是非常重要的，而且有可能是类似问题在其他语言太）：由一个转变你的类型（或更多）的宽度会导致不确定的行为。所以，如果我们试图构建0-7位掩码为8位类型，计算将是（1 LT;＆LT; 8） - 1 ，其中将是不确定的。 （它可能在某些系统上和一些编译器的工作，但不会移植。）此外还有一些与在你最终会转移到上述符号位的情况下签署的类型不确定的行为问题。
In C, this would be (1 << (bit + 1)) - 1. But there is a subtlety here, for C at least (and I apologise for the digression when you've tagged this as language-agnostic, but this is important, and there are probably similar issues in other languages too): a shift by the width of your type (or more) leads to undefined behaviour. So if we were trying to construct a mask for bits 0-7 for an 8-bit type, the calculation would be (1 << 8) - 1, which would be undefined. (It might work on some systems and some compilers, but wouldn't be portable.) There are also undefined behaviour issues with signed types in the case where you would end up shifting into the sign bit.
幸运的是，在C，我们可以使用无符号键入和写作的前pression为（1 <<避免这些问题;＆LT;位）+（1＆LT;＆LT;位） - 1 。算术无符号的 N 的比特值由标准定义为减少模2 N ，所有的个人业务都是很好的定义，所以我们保证得到正确的答案。
Fortunately, in C, we can avoid these problems by using an unsigned type, and writing the expression as (1 << bit) + (1 << bit) - 1. Arithmetic with unsigned n-bit values is defined by the standard to be reduced modulo 2n, and all of the individual operations are well-defined, so we're guaranteed to get the right answer.
（题外话结束）
好了，现在我们有位0面具 - MSB 的。我们希望做一个面具位 LSB 的 - MSB 的，我们可以通过减去掩码位做0 - （ LSB 的-1） ，这是（1 LT;＆LT; LSB） - 1 。例如。
OK, so now we have a mask for bits 0 - msb. We want to make a mask for bits lsb - msb, which we can do by subtracting the mask for bits 0 - (lsb-1), which is (1 << lsb) - 1. e.g.
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)
所以掩码的最后EX pression是：
So the final expression for the mask is:
mask = (1 << msb) + (1 << msb) - (1 << lsb);
可通过按位来选择与要被转动的位与掩模
The bits to be rotated can be selected by a bitwise AND with the mask:
to_rotate = value & mask;
...这将保持不变的位可以通过一个与用翻转掩模来选择：
...and the bits that will be left untouched can be selected by a AND with the inverted mask:
untouched = value & ~mask;
旋转本身可以分为两个部分很容易：首先，我们可以通过简单地旋转 to_rotate 左，丢弃落在任何位获得旋转部分的最左边位外面罩：
The rotation itself can be performed easily in two parts: first, we can obtain the leftmost bits of the rotated portion by simply rotating to_rotate left and discarding any bits that fall outside the mask:
left = (to_rotate << shift) & mask;
要获得最右边位，转动 to_rotate 的右键的由（ N 的 - 移）位，其中的 N 的是（我们正在旋转的位数本的 N 的可以计算为 MSB + 1 - LSB ）
To get the rightmost bits, rotate to_rotate right by (n - shift) bits, where n is the number of bits we're rotating (this n can be calculated as msb + 1 - lsb):
right = (to_rotate >> (msb + 1 - lsb - shift)) & mask;
最后的结果可以通过所有位从触及，离开和<$ C $结合来获得C>右：
result = untouched | left | right;
您最初的例子就是这样的工作（ MSB 5 LSB 1和移 1）
Your original example would work like this (msb is 5, lsb is 1, and shift is 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， 移 = 4（它旋转的4位十六进制值的前3位十六进制数字）：
Here's a different example with a 16-bit input value, msb = 15, lsb = 4, and shift = 4 (which rotates the top 3 hex digits of a 4-digit hex value):
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
这篇关于使用位域或位操作移动一个字节中的位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
