c++ - 如何在 C++ 中构建 N 位变量？

Question

我正在处理 C++ 中非常大的 bool 值列表，每个大约有 2^N 项 N 个 bool 值。因为内存在这种情况下很重要，即呈指数增长，所以我想构建一个 N 位长的变量来存储每个元素。

对于小 N，例如 24，我只使用 unsigned long int .它需要 64MB ((2^24)*32/8/1024/1024)。但我需要增加到 36。唯一带有内置变量的选项是 unsigned long long int , 但它需要 512GB ((2^36)*64/8/1024/1024/1024), 这有点太多了。使用 36 位变量，它对我有用，因为大小下降到 288GB ((2^36)*36/8/1024/1024/1024)，适合我的 super 计算机的一个节点。

我试过了 std::bitset ，但是std::bitset< N >创建至少 8B 的元素。所以列表 std::bitset< 1 >远大于 unsigned long int 的列表.这是因为 std::bitset只需更改表示，而不是容器。

我也试过boost::dynamic_bitset<>来自 Boost，但出于同样的原因，结果更差(至少 32B!)。

我知道一个选项是将所有元素写成一个 bool 值链，2473901162496 (2^36*36)，然后存储在 38654705664 (2473901162496/64) unsigned long long int ，它提供 288GB (38654705664*64/8/1024/1024/1024)。然后访问一个元素只是一个寻找 36 位存储在哪些元素中的游戏(可以是一个或两个)。但这是对现有代码(3000 行)的大量重写，因为映射变得不可能，并且因为在某些函数的执行过程中添加和删除项目肯定会变得复杂、困惑、具有挑战性，结果很可能效率不高。

如何在 C++ 中构建一个 N 位变量？

Answer 1

一个包含 5 个字符的结构体如何(可能需要一些奇特的运算符重载以保持它与现有代码兼容)？由于填充/对齐，具有 long 和 char 的结构可能无法工作...

基本上是您自己的针对大小优化的迷你 BitSet:

struct Bitset40 {
   unsigned char data[5];
   bool getBit(int index) {
     return (data[index / 8] & (1 << (index % 8))) != 0;
   }
   bool setBit(int index, bool newVal) {
     if (newVal) {
        data[index / 8] |= (1 << (index % 8));
     } else {
        data[index / 8] &= ~(1 << (index % 8));
     }
   }
};

编辑:正如 geza 在评论中指出的那样，这里的“技巧”是尽可能接近所需的最小字节数(不会通过触发对齐丢失而浪费内存，填充或指针间接寻址，请参阅 http://www.catb.org/esr/structure-packing/ )。

编辑 2:如果你喜欢冒险，你也可以尝试一个位域(请告诉我们它实际占用了多少空间):

struct Bitset36 {
  unsigned long long data:36;
}