12

0から67600までの数値の長いリストがあります。次に、67600要素の長さの配列を使用してそれらを格納したいと思います。数値がセットに含まれている場合、要素は1に設定され、数値がセットに含まれていない場合、要素は0に設定されます。すなわち。毎回、数値の存在を保存するために必要な情報は1ビットだけです。これを達成するのに役立つC/C ++のハックはありますか？

4

5 に答える 5

15

C ++ではstd::vector<bool>、サイズが動的である場合に使用できます（これは、の特殊なケースです。これstd::vectorを参照してください）。そうでない場合は（可能であれば推奨します）、実行時にサイズを設定/変更する必要がある場合もあります。あなたはここでそれに関する情報を見つけることができます、それはかなりクールです！std::bitsetstd::bitsetboost::dynamic_bitset

C（およびC ++）では、ビット演算子を使用してこれを手動で実装できます。一般的な操作の概要はこちらです。私が言及したいことの1つは、ビット演算を行うときに符号なし整数を使用することをお勧めします。<<負の整数を>>シフトする場合は未定義です。のような整数型の配列を割り当てる必要がありますuint32_t。Nビットを格納したい場合N/32は、これらを使用しuint32_tます。ビットは、'番目の'番目のビットにi格納されます。アーキテクチャやその他の制約に応じて、異なるサイズの整数型を使用することをお勧めします。ノートi % 32i / 32uint32_t：既存の実装を使用することをお勧めします（たとえば、C ++の最初の段落で説明されているように、GoogleでCソリューションを検索します）。これ。）この種のことは死ぬまで行われており、「良い」解決策があります。

1ビットしか消費しないトリックがいくつかあります。たとえば、ビットフィールドの配列（Cでも適用可能）ですが、使用するスペースが少なくなるかどうかはコンパイラー次第です。このリンクを参照してください。

何をするにしても、 Nビットの情報を格納するために正確にNビットを使用することはほぼ確実にできないことに注意してください-コンピュータは8ビット未満を割り当てることができない可能性が非常に高いです：7ビットが必要な場合は無駄にする必要があります1ビット。9ビットが必要な場合は、16ビットを取り、そのうちの7ビットを無駄にする必要があります。コンピュータ（CPU + RAMなど）がシングルビットで「動作」できる場合でも、malloc/を使用するOSで実行している場合はnew、オーバーヘッドが原因で、アロケータがデータをこのような小さな精度で追跡するのは適切ではありません。その最後の資格はかなりばかげていました-私が想像する一度に8ビット未満で操作できるアーキテクチャが使用されていることはわかりません:)

于 2013-03-18T18:18:51.100 に答える
11

を使用する必要がありますstd::bitset。

std::bitsetの配列のように機能しますがbool（値でコピーするため、実際にはのようstd::arrayになります）、要素ごとに1ビットのストレージしか使用しません。

別のオプションはですがvector<bool>、これはお勧めしません。理由は次のとおりです。

  • 低速のポインタ間接参照とヒープメモリを使用してサイズ変更を有効にしますが、これは必要ありません。
  • このタイプは、標準コンテナであると主張しているため、標準の純粋主義者によってしばしば悪意を持っていますが、標準コンテナの定義に準拠していません*。

*たとえば、標準準拠の関数は&container.front()、任意のコンテナタイプの最初の要素へのポインタを生成することを期待できますが、これは。で失敗しstd::vector<bool>ます。 おそらくあなたの使用例の落とし穴ですが、それでも知っておく価値があります。

于 2013-03-18T18:19:49.040 に答える
6

実はあります！ std::vector<bool>これに特化しています：http：//en.cppreference.com/w/cpp/container/vector_bool

ドキュメントを参照してください。可能な限り効率的に保存されます。

編集：他の誰かが言ったように、std::bitset利用可能です：http: //en.cppreference.com/w/cpp/utility/bitset

于 2013-03-18T18:19:15.087 に答える
4

Cで書き込みたい場合は、長さが67601ビット（67601/8 = 8451）のcharの配列を用意してから、各値の適切なビットをオン/オフにします。

于 2013-03-18T18:23:06.590 に答える
1

他の人は正しい考えを与えました。bitsarrこれが、ビットの「配列」の私自身の実装です。unsigned charは1バイトであるため、基本的には、個々のビットに情報を格納するunsignedcharの配列です。1ビット値に加えて2ビット値または4ビット値を格納するオプションを追加しました。これらは両方とも8（バイトのサイズ）を除算するため、0からの範囲の膨大な数の整数を格納する場合に便利です。 -3または0-15。

設定と取得の際、計算は関数で行われるため、通常の配列であるかのようにインデックスを付けることができます。どこを見ればよいかがわかります。

また、大きすぎる値を設定に渡さないようにするのはユーザーの責任です。そうしないと、他の値が台無しになります。オーバーフローが0にループバックするように変更することもできますが、それではさらに複雑になるため、自分自身を信頼することにしました。

#include<stdio.h>
#include <stdlib.h>
#define BYTE 8

typedef enum {ONE=1, TWO=2, FOUR=4} numbits;

typedef struct bitsarr{
    unsigned char* buckets;
    numbits n;
} bitsarr;


bitsarr new_bitsarr(int size, numbits n)
{
    int b = sizeof(unsigned char)*BYTE;
    int numbuckets = (size*n + b - 1)/b;
    bitsarr ret;  
    ret.buckets = malloc(sizeof(ret.buckets)*numbuckets);
    ret.n = n;
    return ret;
}
void bitsarr_delete(bitsarr xp)
{
    free(xp.buckets);
}

void bitsarr_set(bitsarr *xp, int index, int value)
{
    int buckdex, innerdex;
    buckdex = index/(BYTE/xp->n);
    innerdex = index%(BYTE/xp->n);
    xp->buckets[buckdex] = (value << innerdex*xp->n) | ((~(((1 << xp->n) - 1) << innerdex*xp->n)) & xp->buckets[buckdex]);

    //longer version

    /*unsigned int width, width_in_place, zeros, old, newbits, new;
    width = (1 << xp->n) - 1; 
    width_in_place = width << innerdex*xp->n;
    zeros = ~width_in_place;
    old = xp->buckets[buckdex];
    old = old & zeros;
    newbits = value << innerdex*xp->n;
    new = newbits | old;
    xp->buckets[buckdex] = new; */

}

int bitsarr_get(bitsarr *xp, int index)
{
    int buckdex, innerdex;
    buckdex = index/(BYTE/xp->n);
    innerdex = index%(BYTE/xp->n);
    return ((((1 << xp->n) - 1) << innerdex*xp->n) & (xp->buckets[buckdex])) >> innerdex*xp->n;

    //longer version

    /*unsigned int width = (1 << xp->n) - 1; 
    unsigned int width_in_place = width << innerdex*xp->n;
    unsigned int val = xp->buckets[buckdex];
    unsigned int retshifted = width_in_place & val;
    unsigned int ret = retshifted >> innerdex*xp->n;
    return ret; */
}

int main()
{
    bitsarr x = new_bitsarr(100, FOUR);
    for(int i = 0; i<16; i++)
        bitsarr_set(&x, i, i);
    for(int i = 0; i<16; i++)
        printf("%d\n", bitsarr_get(&x, i));
    for(int i = 0; i<16; i++)
        bitsarr_set(&x, i, 15-i);
    for(int i = 0; i<16; i++)
        printf("%d\n", bitsarr_get(&x, i));
    bitsarr_delete(x);
}
于 2014-07-04T22:35:44.610 に答える