Bit field vs Bitset

Question

我想在一个类似数组的数据结构中存储位(bit)。因此，我可以采用以下两种方法之一：

方法一(AN 1)

struct BIT
{
   int data : 1
};

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

第二种方法 (AN2)

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

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

- CLOWN

---

引用cplusplus.com关于bitset页面的话，"该类非常类似于常规数组，但优化了空间分配"。如果您使用的是4字节的整数，则bitset使用的空间将少32倍。 - AlcubierreDrive

您的结构体 BIT 无论如何都会对齐到至少一个字节。 - Archie

@Jon，请把那个作为一个答案发出来。（这是一个好点子。） - Jon-Eric

@sbi 大多数实现都具有 >= 1 字节的布尔值，因此位集仍然比布尔向量高效 8 倍。 - AlcubierreDrive

还应该提到的是，根据您的使用方式，AN1虽然使用更多的内存，但访问时间比AN2更快。我说“根据您的使用方式”，因为如果数组很大，由于CPU缓存内存，bitset/vector<bool>版本仍然可能更快。 - edA-qa mort-ora-y

Answer 1

第二种方法实际上使用了100比特的存储空间，再加上一些非常小的（常数）开销，而第一种方法通常使用每个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 将您的位数组封装在一个漂亮的对象表示中，并具有许多有用的操作。

- Fred Foo

---

为什么 sizeof(b) 的输出是16？100位意味着100/8字节。我错过了什么吗？ - CLOWN

它必须“舍入”到八的倍数，因为字节是直接可寻址的最小存储单元。尝试使用128位进行编译，然后仍然是16。bitset使用一些技巧来假装它实际上正在寻址位。 - Fred Foo

我的上一个评论有一半是正确的。它会被舍入为4字节的倍数，因为对于32位计算机来说，四字节单位是最快处理的。但无论如何，字节是最小的可寻址单元，所以至少为13个（100/8 = 12.5，而半个字节是不可寻址的）。抱歉，周五下午。 - Fred Foo

Answer 2

一个好的选择取决于你将如何使用这些位。 std::bitset<N> 是固定大小的。Visual C++ 10.0 在构造函数方面不符合标准；通常需要提供一个解决方法。具体来说，这是因为微软认为存在一个 bug，他们引入了一个带有 int 参数的构造函数，我记得是这样的。 std::vector<bool> 以与 std::bitset 相同的方式进行了优化。代价是：索引不能直接提供引用（C++ 中没有对单个位的引用），而是返回一个代理对象——这是你在试图将其用作引用时才会注意到的。优点是：最小存储空间，向量可以根据需要调整大小。

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

最后，除 Microsoft 外，全部大写的标识符都被约定保留给宏，以减少名称冲突的概率。因此，不要将全部大写的标识符用于除宏以外的任何其他内容，始终将全部大写的标识符用于宏（这也使它们更容易被识别）。

祝好运。

- Cheers and hth. - Alf

Answer 3

bitset has more operations

- Wernight

Answer 4

引用cplusplus.com的bitset页面，“该类非常类似于常规数组，但优化了空间分配”。如果您的int是4个字节，则bitset使用的空间少32倍。

即使像sbi建议的那样做bool bits[100]，仍然比bitset差，因为大多数实现都有>= 1字节的布尔值。

如果仅出于知识好奇的原因，您想要实现自己的bitset，则可以使用位掩码来实现：

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语言。显然，使用类的两个巨大优点是运算符重载和具有可变大小数组的能力。）

- AlcubierreDrive

---

在C++中，类和结构体的唯一区别在于，类的成员默认为私有(private)，而结构体的成员默认为公有(public)。 - M2tM

Answer 5

第一种方法很可能会被编译为4字节整数的数组，并且每个整数的1位将用于存储您的数据。理论上，聪明的编译器可以优化这个过程，但我不会指望它。

您不想使用std::bitset有什么原因吗？

- Jonathan