c++ - 非常に大きなビット/ブール値の配列を作成する必要があります。C / C ++でこれを行うにはどうすればよいですか？

Question

100000000を超える要素を持つビットの配列を作成することさえ可能ですか？もしそうなら、私はこれをどのように行うのですか？char配列の場合、これを実行できることを知っています。

char* array;

array = (char*)malloc(100000000 * sizeof(char));

それまでに配列を宣言するとchar array[100000000]、要素の最大数を超えたため、セグメンテーション違反が発生します。これが、を使用する理由ですmalloc。

ビット配列に対して私ができる同様のことはありますか？

score 12 · Accepted Answer

C ++を使用している場合は、std::vector<bool>要素をビットマップにパックすることに特化しています。もちろん、C ++を使用している場合は、の使用を停止する必要がありますmalloc。

score 8 · Accepted Answer

boost::dynamic_bitsetを見てみることができます。次に、次のようなことを行うことができます（Boostのサンプルページから取得）。

boost::dynamic_bitset<> x(100000000); // all 0's by default
x[0] = 1;
x[1] = 1;
x[4] = 1;

ビットセットは要素ごとに1ビットを使用するため、4バイトのスペースに32個のアイテムを格納できるため、必要なメモリの量が大幅に削減されます。

score 5 · Accepted Answer

CおよびC++では、charが最小のタイプです。ビットの配列を直接宣言することはできません。ただし、基本的なタイプの配列は基本的にビットで構成されているため、次のようにエミュレートできます（コードはテストされていません）。

unsigned *array;
array = (unsigned *) malloc(100000000 / sizeof(unsigned) + 1);

/* Retrieves the value in bit i */
#define GET_BIT(array, i) (array[i / sizeof(unsigned)] & (1 << (i % sizeof(unsigned))))

/* Sets bit i to true*/
#define SET_BIT(array, i) (array[i / sizeof(unsigned)] |= (1 << (i % sizeof(unsigned))))

/* Sets bit i to false */
#define CLEAR_BIT(array, i) (array[i / sizeof(unsigned)] &= ~(1 << (i % sizeof(unsigned))))

score 4 · Accepted Answer

気付いたセグメンテーション違反は、スタックスペースが不足していることが原因です。もちろん、サイズが12.5 MB（1億ビット）のローカル変数を宣言することはできません。スタックが最大4 MBのスレッドでは、サイズが100 MB（1億バイト）は言うまでもありません。グローバル変数として機能するはずですが、12MBまたは100MBの実行可能ファイルになってしまう可能性がありますが、それでも良い考えではありません。動的割り当ては、そのような大きなバッファに対して行うのが間違いなく正しいことです。

score 3 · Accepted Answer

STLの使用が許可されている場合は、を使用しますstd::bitset。

（100,000,000ビットの場合、下に100000000/32が使用されunsigned int、それぞれに32ビットが格納されます。）

std::vector<bool>、すでに述べたように、別の良い解決策です。

score 1 · Accepted Answer

C++でビットマップを作成する方法はいくつかあります。

コンパイル時のビットマップのサイズがすでにわかっている場合は、STLstd::bitsetテンプレートを使用できます。

これは、ビットセットでそれを行う方法です std::bitset<100000000> array

それ以外の場合、実行時にビット配列のサイズが動的に変化する場合は、http：//en.cppreference.com/w/cpp/utility/bitsetstd::vector<bool>を使用するかboost::dynamic_bitset、推奨されているとおりに使用できます（下部の注を参照）。

score 0 · Accepted Answer

はい、でももう少し複雑になります！

ビットを格納するためのより良い方法は、文字自体にビットを使用することです！

したがって、8ビットをcharに格納できます！

これは「たった」 12'500'000オクテットを必要とします！

バイナリに関するいくつかのドキュメントは次のとおりです：http：//www.somacon.com/p125.php

あなたはグーグルを見る必要があります:)

score 0 · Accepted Answer

その他の解決策：

unsignedchar*配列;
array =（unsigned char *）malloc（100000000 / sizeof（unsigned char）+ 1）;

bool MapBit（unsigned char arraybit []、DWORD位置、boolセット）
{{
    //4294967295ビット位置で0で動作します
    //ビット位置を計算します
    DWORD bytepos =（位置/ 8）;
    //
    unsigned char bitpos =（位置％8）;

    unsignedcharビット=0x01;

    //ビットを取得
    if（bitpos）
    {{
        ビット=ビット<<ビット位置;
    }

    if（set）
    {{
        arraybit [bytepos]|=ビット;
    }
    そうしないと
    {{
        //得る
        if（arraybit [bytepos]＆bit）
            trueを返します。
    }

    falseを返します。
}

score 0 · Accepted Answer

私はhttp://www.jjj.de/fxt/のオープンソースfxtライブラリにあるビット配列が好きです。シンプルで効率的で、いくつかのヘッダーに含まれているため、プロジェクトに簡単に追加できます。さらに、ビット配列で使用する多くの補完的な関数があります（http://www.jjj.de/bitwizardry/bitwizardrypage.htmlを参照）。

c++ - 非常に大きなビット/ブール値の配列を作成する必要があります。C / C ++でこれを行うにはどうすればよいですか？

9 に答える 9

Related

Reference