位域与位集

Question

我想将位存储在数组（如结构）中。因此，我可以采用以下两种方法之一

方法 1 (AN 1)

struct BIT
{
   int data : 1
};

int main()
{
   BIT a[100];
   return 0;
}

方法 2 (AN 2)

int main()
{
    std::bitset<100> BITS;
    return 0;
}

为什么有人会更喜欢 AN 2 而不是 AN 1？

Answer 1

因为方法nr。 2 实际上使用 100 位存储，加上一些非常小的（恒定）开销，而 nr. 1 通常每个 Bit 结构使用四个字节的存储空间。一般来说，根据 C++ 标准，struct 至少有一个字节大。

#include <bitset>
#include <iostream>

struct Bit { int data : 1; };

int main()
{
    Bit a[100];
    std::bitset<100> b;
    std::cout << sizeof(a) << "\n";
    std::cout << sizeof(b) << "\n";
}

除此之外

400
16

， bitset 将位数组包装在一个漂亮的对象表示中有许多有用的操作。

Answer 2

一个好的选择取决于您将如何使用这些位。

std::bitset 具有固定大小。 Visual C++ 10.0 不符合标准。给建造者；一般来说，您必须提供解决方法。具有讽刺意味的是，这是由于微软认为是一个错误修复——我记得他们引入了一个采用 int 参数的构造函数。

std::vector 的优化方式与 std::bitset 大致相同。成本：索引并不直接提供引用（C++ 中没有对各个位的引用），而是返回一个代理对象——除非您尝试将其用作引用，否则您不会注意到它。优点：存储空间最小，并且矢量可以根据需要调整大小。

如果您要处理少量位（实际上是 32 位或更少，尽管正式保证只是 16 位），那么简单地使用例如 unsigned 也是一种选择。

最后，所有大写标识符按照惯例（Microsoft 除外）保留给宏，以减少名称冲突的可能性。因此，最好不要对宏以外的任何其他内容使用全部大写标识符。并且始终对宏使用全部大写标识符（这也使得更容易识别它们）。

干杯&呵呵，，

Answer 3

bitset有更多操作

Answer 4

方法 1 最有可能被编译为 4 字节整数数组，并且每个整数的一位将用于存储数据。理论上，智能编译器可以对此进行优化，但我不会指望它。

您是否有理由不想使用 std::bitset？

Answer 5

引用 cplusplus.com 关于 bitset 的页面，“该类与常规的数组，但优化空间分配”。如果您的 int 为 4 个字节，则位集使用的空间将减少 32 倍。

即使按照 sbi 的建议执行 bool bits[100] ，仍然比 bitset 更糟糕，因为大多数实现都具有 >= 1 字节的 bool。

如果仅出于求知欲的原因，您想实现自己的位集，则可以使用位掩码来实现：（

typedef struct {
  unsigned char bytes[100];
} MyBitset;

bool getBit(MyBitset *bitset, int index)
{
  int whichByte = index / 8; 
  return bitset->bytes[whichByte] && (1 << (index = % 8));
}

bool setBit(MyBitset *bitset, int index, bool newVal)
{
  int whichByte = index / 8;

  if (newVal)
  {
    bitset->bytes[whichByte] |= (1 << (index = % 8));
  }
  else
  {
    bitset->bytes[whichByte] &= ~(1 << (index = % 8));
  }
}

顺便说一句，很抱歉使用结构而不是类。我正在直接使用 C 进行思考，因为我显然，使用类的两个巨大好处是运算符重载和拥有可变大小数组的能力。）