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

发布于 2024-11-16 21:43:27 字数 1097 浏览 4 评论 0原文

有没有一种优雅的方式在一个字节（或字/长）内移动一位。为简单起见，我们使用一个简单的 8 位字节，并且仅在字节内移动一位。

给定一个位数，基于 0-7 Least-sig-bit 到most-sig-bit（或者如果您愿意，则为 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 的位“腾出空间”。这只是一个示例。

重要的是该位移动，而不是与其目标交换。有许多交换位的示例，但这非常微不足道。

理想的解决方案将使用简单的位旋转和按位运算符。假设与语言无关、位简单的 AND/OR/XOR、NOT、SHIFT Left/Right/ROTATE 或类似指令的任何组合都可以，加上任何其他基本算术运算符，例如：mod、加法/减法等。代码就可以了。或者，位数组或位域类型结构可能很简单。

除了实际的位移动之外，我还想找到一种方法：

向上或向下移动任何位。
以任何方便的格式指定位数源/目标：例如：6>2 意味着下移、3＞7上移或起始位+/-偏移：6-4或3+4，或位加权：位6＝64到位3＝8。
可能从 byte 扩展到 unsigned int、long 等
（理想情况下，可以扩展一次不止一位，如果更容易的话可能是相邻位）

性能不是主要问题，但优雅的东西可能足够快。

我自己的天真的方法是识别源和目标位位置，决定是否向上或向下移动，获取移位副本，屏蔽静态位并找到源位，合并静态位和移位位并以某种方式设置/清除目标位。然而，虽然理论看起来不错，但优雅的实现却超出了我的能力范围。

我意识到可以为一个字节构建一个预编译的查找表，但如果要将其扩展到整数/长整型，这对我来说是不切实际的。

任何帮助表示赞赏。提前致谢。

原文

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.

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

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.

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.

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 :

Move any bit up or down.
Specify the bit number source/destination in any convenient format: eg: 6>2
implies shift down, 3>7 shift up or start-bit +/- offset: 6-4 or 3+4, or bit weighted: bit 6=64 to bit 3=8.
Possibly extendable from byte to unsigned int, long, etc.
(Ideally, be extendable
to more than one bit at a time, probably adjacent bits if easier)

Performance is not a major issue, but something elegant is likley to be plenty fast enough.

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.

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.

Any help appreciated. Thanks in advance.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

☆獨立☆ 2024-11-23 21:43:27

首先，对原始问题以及您提到的后续扩展进行观察：

您描述的“移动一点”操作实际上是连续位范围的旋转。在您的示例中，您将位 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 位与向左旋转 k 位是一样的>n - k 位；
它可以简单地推广到任何位宽；
根据定义，我们一次可以旋转一位以上。

所以现在，所需要的就是构造这个原语......

首先，我们几乎肯定需要一个我们关心的位的位掩码。

我们可以通过将 1 向左移动 n + 1 位，然后减去 1，来形成位 0 - n 的掩码。例如，位 0-5 的掩码将be（二进制）：

00111111

...可以通过取 1 来形成：

00000001

...向左移动 5+1 = 6 位：

01000000

...并减去 1 得到：

00111111

在 C 中，这将是 (1 << (位 + 1)) - 1。但这里有一个微妙之处，至少对于 C 来说（当你将其标记为与语言无关时，我为离题表示歉意，但这很重要，并且其他语言中也可能存在类似的问题）：您的类型的宽度（或更多）会导致未定义的行为。因此，如果我们尝试为 8 位类型的位 0-7 构造一个掩码，计算结果将为 (1 << 8) - 1，这是未定义的。（它可能适用于某些系统和某些编译器，但不可移植。）在最终转换为符号位的情况下，有符号类型还存在未定义的行为问题。

幸运的是，在 C 中，我们可以通过使用 unsigned 类型来避免这些问题，并将表达式编写为 (1 << bit) + (1 << bit) - 1。标准将无符号 n 位值的算术定义为以 2ⁿ 为模进行缩减，并且所有单独的操作都已明确定义，因此我们保证得到正确的答案。

（题外话结束。）

好的，现在我们有了 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;

...并且可以通过与反转掩码进行与来选择将保持不变的位：

untouched = value & ~mask;

旋转它本身可以轻松地分为两部分执行：首先，我们可以通过简单地向左旋转to_rotate并丢弃落在掩码之外的任何位来获得旋转部分的最左边的位：

left = (to_rotate << shift) & mask;

要获得最右边的位，请旋转to_rotate right by (n - shift) 位，其中 n 是数字我们正在旋转的位数（这个n可以计算为msb + 1 - lsb）：

right = (to_rotate >> (msb + 1 - lsb - shift)) & mask;

可以通过组合来自未触及的所有位来获得最终结果、左和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（循环前 3 位十六进制数字4 位十六进制值）：

    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

First, an observation about the original problem, and the subsequent extensions that you mention:

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:

the least significant bit to include in the rotation
the most significant bit to include in the rotation
the number of bits to rotate by

then it becomes a single basic primitive which can perform all of the things you want to do:

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.

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

...which can be formed by taking a 1:

00000001

...shifting 5+1 = 6 bits to the left:

01000000

...and subtracting 1 to give:

00111111

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.

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 2ⁿ, and all of the individual operations are well-defined, so we're guaranteed to get the right answer.

(End of digression.)

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)

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;

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 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;

The final result can be obtained by combining all the bits from untouched, left, and right:

result = untouched | left | right;

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

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

回复收藏 0 原文

画▽骨i 2024-11-23 21:43:27

这是一个 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) = %#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;
}

Here's a working implementation in C that is not highly optimised but which might at least serve as a starting point for any further implementations. It works with ints but you can adapt it for any word size, or just use it as is and mask out any unwanted high order bits (e.g. if you are working with individual bytes). I broke the functionality down into two lower level routines for extracting a bit and inserting a bit - these may have other uses, I imagine.

//
// 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;
}

回复收藏 0 原文

熟人话多 2024-11-23 21:43:27

这可能不符合“优雅”的条件，但如果你喜欢的话，你也许可以把它塞进一行？计划是将数字分成四部分（位操作应该不难，对吧？），对它们进行适当的操作，然后将三部分重新组合在一起。

              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上移1] + [P2下移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

This likely doesn't qualify as "elegant," but you might be able to cram it into one line if that is your kind of thing? The plan is to split the number into four pieces (shouldn't be hard with bit operations, right?), do the appropriate things to them, and then put the three pieces back together.

              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

Then the number you want is [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

回复收藏 0 原文