使用位域或按位运算符在一个字节内移动一位

| 是否有一种优雅的方式在一个字节(或字/长)内移动一位。为简单起见,让我们使用一个简单的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,加法/减法等)都可以使用,甚至可以工作。代码就可以了。或者,位数组或位域类型的结构可能很简单。 除了实际的位移动之外,我还想找到一种方法: 向上或向下移动任何一点。 以任何方便的格式指定位数来源/目的地:例如:6> 2 表示向下移位,3> 7向上移位或起始位+/-偏移:6-4或3 + 4,或位加权:位6 = 64到位3 = 8。 可能从字节扩展到无符号的int,long等。 (理想情况下,可扩展 一次超过一个位,如果容易的话,可能是相邻位) 性能不是主要问题,但是优雅是足够快的。 我自己的细微方法是确定源和目标位的位置,决定是上移还是下移,进行移位复制,掩盖静态位并找到源位,合并静态和移位位,然后以某种方式设置/清除目标位。但是,尽管理论看起来不错,但优雅的实现超出了我的范围。 我意识到可以为一个字节建立一个预编译的查找表,但是如果要扩展为整数/长整数,这对我来说是不切实际的。 任何帮助表示赞赏。提前致谢。     
已邀请:
首先,观察一下原始问题以及您提到的后续扩展: 您描述的“移动位”操作实际上是连续位范围的旋转。在您的示例中,您将第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 |
+---+---+-|-+---+---+---+-^-+---+      +---+---+---+---+---+---+---+---+
          |               |
          +---------------+
如果您认为此操作的更一般形式是使用三个参数“将剩余的位范围旋转一些”,则: 轮换中包含的最低有效位 轮换中要包含的最高有效位 旋转的位数 然后它将变成一个单一的基本原语,可以执行您想做的所有事情: 您显然可以移动任何位(选择适当的最低/最高有效位参数); 您可以向左或向右旋转,因为如果要旋转n位范围,则向右旋转k位与向左旋转n-k位是相同的; 它可以概括为任意位宽; 根据定义,我们可以一次旋转多于一个比特。 所以现在,所有需要的就是构造这个原始的... 首先,几乎可以肯定,我们关心的位需要一个位掩码。 我们可以通过将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位值的算术定义为以2n为模减少,并且所有单独的操作都定义明确,因此我们保证将获得正确的答案。 (题外话。) 好,现在我们有了一个掩码,用于位0-msb。我们想要为lsb-msb位做一个掩码,我们可以通过减去0-(lsb-1)位的掩码来完成,即mask10ѭ。例如
  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;
旋转本身可以很容易地分为两个部分:首先,我们可以通过简单地向左旋转and15ѭ并丢弃掉掩码之外的任何位来获得旋转部分的最左边的位:
left = (to_rotate << shift) & mask;
要获得最右边的位,请将(15ѭ向右旋转(n-shift)位,其中n是我们要旋转的位数(该n可计算为
msb + 1 - lsb
):
right = (to_rotate >> (msb + 1 - lsb - shift)) & mask;
可以通过组合
untouched
left
和ѭ22all中的所有位来获得最终结果:
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位,bit24ѭ= 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工作实现,但至少可以作为任何其他实现的起点。它可以与int一起使用,但是您可以将其调整为任何字长,或者直接使用它并屏蔽掉所有不需要的高阶位(例如,如果您使用单个字节)。我将功能分解为两个较低级别的例程,以提取和插入一些位,我想这些可能还有其他用途。
//
// 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) = %#x\\n\", test);
        printf(\"index (src) = %d\\n\", index1);
        printf(\"index (dest) = %d\\n\", index2);

        move_bit(&test, index1, index2);

        printf(\"test (after) = %#x\\n\", 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               
    
您是否正在使用位来节省空间?真的需要吗? 使用允许您在列表中删除和插入项目的列表类,可能会更好。在您的情况下,这些项目将是布尔值。     

要回复问题请先登录注册