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

Question

我正在处理 C++ 中非常大的布尔值列表，每个大约有 2^N 项 N 个布尔值。因为内存在这种情况下很关键，即指数增长，所以我想建立一个 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)，适合我的超级计算机的一个节点。

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

我也试过 boost::dynamic_bitset<> 来自 Boost，但结果更差（至少 32B！），原因相同。

我知道一个选项是将所有元素写成一个布尔值链，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在评论中也指出的那样，这里的"trick"是为了尽可能接近所需的最小字节数（没有通过触发对齐损失、填充或指针间接来浪费内存，请参阅 http://www.catb.org/esr/structure-packing/)。

编辑2：如果你喜欢冒险，你也可以试试位域（请告诉我们它实际消耗了多少space）：

struct Bitset36 {
  unsigned long long data:36;
}

Answer 2

您可以使用 unsigned long int 数组并通过按位运算存储和检索所需的位链。这种方法不包括 space 开销。

无符号字节数组 B[] 和 12 位变量 V（表示为 ushort）的简化示例：

Set V[0]:  
B[0] = V & 0xFF; //low byte 
B[1] = B[1] & 0xF0;  // clear low nibble
B[1] = B[1] | (V >> 8);  //fill low nibble of the second byte with the highest nibble of V

Answer 3

我不是专家，但这就是我想要的"try"。找到你的编译器支持的最小类型的字节（应该是 char）。你可以用 sizeof 检查一下，你应该得到 1。这意味着 1 个字节，所以 8 位。

因此，如果您想要 24 位类型...您需要 3 个字符。对于 36，您将需要 5 个字符数组，最后将有 4 位浪费的填充。这很容易解释。

即

char typeSize[3] = {0}; // should hold 24 bits

现在制作一个位掩码来访问 typeSize 的每个位置。

const unsigned char one = 0b0000'0001;
const unsigned char two = 0b0000'0010;
const unsigned char three = 0b0000'0100;
const unsigned char four = 0b0000'1000;
const unsigned char five = 0b0001'0000;
const unsigned char six = 0b0010'0000;
const unsigned char seven = 0b0100'0000;
const unsigned char eight = 0b1000'0000;

现在您可以使用按位或在需要的地方将值设置为 1..

typeSize[1] |= four; 
*typeSize[0] |= (four | five);

要关闭位，请使用 & 运算符..

typeSize[0] &= ~four; 
typeSize[2] &= ~(four| five);

您可以使用&运算符读取每个位的位置。

typeSize[0] & four

请记住，我手头没有编译器来尝试这个，所以希望这是解决您的问题的有用方法。

祝你好运;-)

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

How to build N bits variables in C++?

c++

algorithm

optimization

bitarray

bitset