C/C++：动态分配内存的位运算符

Question

在C/C++中，是否有一种简便的方法可以对动态分配的内存应用按位运算符（特别是左/右移）？

例如，假设我做了这个：

unsigned char * bytes=new unsigned char[3];
bytes[0]=1;
bytes[1]=1;
bytes[2]=1;

我希望有一种方法来实现这个目标：

我想要的是：

bytes>>=2;

（然后“bytes”将具有以下值）：

bytes[0]==0
bytes[1]==64
bytes[2]==64

为什么值应该是这样的：

分配后，字节看起来像这样：

[00000001][00000001][00000001]

但我希望将字节视为一长串位，就像这样：

[000000010000000100000001]

右移两位会使位数如下所示：

[000000000100000001000000]

当将其分解回3个字节时，最终看起来像这样（因此为0、64、64）：

[00000000][01000000][01000000]

有什么想法吗？我是否应该创建一个结构体/类并重载适当的运算符？编辑：如果是这样，如何继续？注意：我正在寻找一种自己实现（在一些指导下）作为学习经验的方式。

任何想法？我是否应该创建一个结构体/类并重载适当的运算符？如果是这样，如何继续？请注意，我正在寻找一种自己实现（在一些指导下）作为学习经验的方式。

- Cam

---

你认为这个操作会单独地移动每个位吗？还是会将位从一个字节传递到下一个字节？ - John Knoeller

你的意思是你希望移位跨越你正在访问的字节的边界吗？我猜你也想能够在超过4个字节的情况下进行移位，这可能对于int转换和移位来说是安全的。 - Ben Zotto

我编辑了我的帖子，以展示移位后应该是什么值。对于最初的不清晰，我很抱歉。（@John，我希望这可以将位从一个字节传递到下一个。） - Cam

为什么右移后，bytes[1]和bytes[2]的值相同？你能进一步解释一下吗？ - dirkgently

@dirkgently，我已经编辑了主贴来回答你的问题。 - Cam

Answer 1

• 将分配与访问器/修改器分离
• 接下来，看看是否可以使用像bitset这样的标准容器完成任务
• 否则，请查看boost::dynamic_bitset
• 如果所有尝试都失败了，请自己编写类

粗略示例：

typedef unsigned char byte;

byte extract(byte value, int startbit, int bitcount)
{
   byte result;
   result = (byte)(value << (startbit - 1));
   result = (byte)(result >> (CHAR_BITS - bitcount));
   return result;
}

byte *right_shift(byte *bytes, size_t nbytes, size_t n) {
   byte rollover = 0;
   for (int i = 0; i < nbytes; ++i) {
     bytes[ i ] = (bytes[ i ] >> n) | (rollover < n);
     byte rollover = extract(bytes[ i ], 0, n);
   }
   return &bytes[ 0 ];
}

- dirkgently

---

这看起来非常酷。然而，作为一次学习经历，我有点想自己制作一个。此外，我特别希望它能够根据需求扩展（大小）。 - Cam

请注意，可以在运行时指定 boost::dynamic_bitset 对象的大小。如果您有兴趣学习，我建议查看它们的实现并自己编写（只编写所需功能）。 - dirkgently

Answer 2

我假设你想要将位从一个字节传递到另一个字节，就像John Knoeller所建议的那样。

这里的要求不充分。您需要指定位的顺序相对于字节的顺序-当最低有效位从一个字节中掉出时，它会进入下一个更高还是更低的字节。

不过，您所描述的在图形编程中曾经非常常见。您基本上描述了一种单色位图水平滚动算法。

假设“右边”意味着更高的地址但不太重要的位（即匹配常规写作约定），单位位移将是以下内容之一...

void scroll_right (unsigned char* p_Array, int p_Size)
{
  unsigned char orig_l = 0;
  unsigned char orig_r;

  unsigned char* dest = p_Array;

  while (p_Size > 0)
  {
    p_Size--;

    orig_r  = *p_Array++;
    *dest++ = (orig_l << 7) + (orig_r >> 1);

    orig_l = orig_r;
  }
}

适应变量移位大小的代码不应该是一个大问题。有明显的优化机会（例如，一次处理2、4或8个字节），但我会把这部分留给你。

要进行左移，请使用一个单独的循环，该循环应该从最高地址开始向下工作。

如果你想按需扩展，请注意orig_l变量包含上面的最后一个字节。要检查是否溢出，请检查(orig_l << 7)是否非零。如果你的字节存储在std::vector中，在任何一端插入都不应该是问题。

编辑：我应该说-优化以处理2、4或8个字节将创建对齐问题。例如，从未对齐的char数组中读取2字节的单词时，最好先读取奇数字节，以便后续的单词读取都是偶地址，直到循环结束。

在x86上，这是不必要的，但速度非常快。在某些处理器上是必需的。只需根据基址（address＆1）、（address＆3）或（address＆7）执行切换即可处理开始前的前几个字节。你还需要特别处理主循环后的尾字节。

- user180247

---

太好了，谢谢！我会把它们放在一个向量中；不确定为什么我没有想到这个 :) 非常有帮助的答案！ - Cam

Answer 3

以下是我针对两个字节的做法：

unsigned int rollover = byte[0] & 0x3;
byte[0] >>= 2;

byte[1] = byte[1] >> 2 | (rollover << 6);

从那里开始，您可以将其归纳为n字节的循环。 为了灵活性，您需要生成魔术数字（0x3和6），而不是硬编码它们。

- R Samuel Klatchko

Answer 4

我会研究类似于这样的东西：

#define number_of_bytes 3

template<size_t num_bytes>
union MyUnion
{
    char            bytes[num_bytes];
    __int64         ints[num_bytes / sizeof(__int64) + 1];
};

void main()
{
    MyUnion<number_of_bytes> mu;
    mu.bytes[0] = 1;
    mu.bytes[1] = 1;
    mu.bytes[2] = 1;
    mu.ints[0] >>= 2;
}

试着玩一下，我相信你会明白的。

- Poni

Answer 5

运算符重载是一种语法糖。它实际上只是一种调用函数并传递字节数组的方式，而不必让它看起来像是在调用函数。

因此，我会先编写这个函数。

 unsigned char * ShiftBytes(unsigned char * bytes, size_t count_of_bytes, int shift);

如果你想将这个函数封装成一个操作符重载，以便于使用或者只是因为你更喜欢那种语法，你也可以这样做。或者你也可以直接调用这个函数。

- John Knoeller

---

您只能在用户定义的类型上使用运算符重载，而此示例为 unsigned char *。发帖者需要定义一个类来表示数据结构。 - David Thornley

@David：很好的发现，应该是unsigned char而不是byte。但我不确定你所说的其他部分的意思。为了实现重载，您仍需要一个执行字节移位的函数。 - John Knoeller

“unsigned char” 用于表示一个字节很有用，但它不是用户定义的类型。你不能定义 unsigned char *::operator>>(int)，它必须像 Bitarray::operator>>(int) 这样。你错过了中间的一步，我可能会对海报上的细节变得苛刻。 - David Thornley

@David：我并不是建议在无符号字符上重载运算符，我是说这个函数可以成为任何运算符重载的核心。声明一个带有重载>>的foo类，然后重载可以直接调用此函数（将&foo强制转换为char*）。在可重用函数中完成艰苦的工作比在运算符重载内部实现移位更加灵活。 - John Knoeller