C++でNビットの変数を作成するには？

Question

私はC++で非常に大きなブール値のリストを処理していますが、それぞれNブール値の2^N個のアイテムがあります。このような状況、すなわち指数関数的な成長ではメモリが重要であるため、各要素を格納するためにNビットのlong変数を作成したいと考えています。

小さい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<>を試しましたが、同じ理由で結果がさらに悪い（少なくとも32B！）。

Iオプションは、次に、（38654705664 * 8分の64 288ギガバイトを与える38654705664（64分の2473901162496）unsigned long long intに次に格納する、ブール値のいずれかの鎖、2473901162496（* 36 2^36）のように全ての要素を記述するために知っています/ 1024/1024/1024）。次に、要素にアクセスするには、36ビットがどの要素に格納されているかを見つけるゲーム（1つでも2つでもよい）です。しかし、既存のコード（3000行）の書き換えが多いため、マッピングが不可能になり、実行中に項目を追加したり削除したりすることは、複雑で紛らわしく、困難になり、その結果が効率的でない可能性が高いからです。

C++でNビット変数を作成するにはどうすればよいですか？

Answer 1

5文字の構造体（および既存のコードとの互換性を維持するために、必要に応じて多少面白い演算子をオーバーロードするのはどうでしょう？長いとcharがおそらくパディング/アライメントの動作しませんを持つ構造体...

は、基本的には自分自身のミニサイズ用に最適化されたビットセット：

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)); 
    } 
    } 
}; 

編集：下座も指摘したようにここでの「トリック」とは、必要最小限のバイト数に可能な限り近づけることです（アラインメントロス、パディング、またはポインタ間接をトリガーすることによってメモリを浪費することなく、http://www.catb.org/esr/structure-packing/を参照）。

編集2：あなたは冒険を感じた場合、あなたはまた、ビットフィールドを試みることができる（そして、私たちはそれが実際に消費どのくらいのスペースお知らせください）：

struct Bitset36 { 
    unsigned long long data:36; 
} 

Answer 2

あなたはunsigned long intのアレイとストアを使用することができます必要なビット・チェーンをビット単位の操作で取り出すことができます。このアプローチでは、スペースのオーバーヘッドは除きます。

符号なしバイト配列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

私は専門家ではないんだけど、これは私が「試みる」なるものです。コンパイラがサポートする最小の型のバイトを探します（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 

これを試すにはコンパイラが便利ではありませんので、これが問題に有効な方法です。

幸運;-)