如何在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),这是一个有点过分.使用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在他评论中指出的那样,这里的"技巧"是尽可能接近所需的最小字节数(不通过触发对齐丢失,填充或指针间接来浪费内存,请参阅http:// www.catb.org/esr/structure-packing/).

编辑2:如果你觉得有冒险精神,你也可以尝试一下这个领域(请告诉我们它实际消耗的空间):

struct Bitset36 {
  unsigned long long data:36;
}