algorithm - 10000 ビットのみを使用して 10000 個のブール値を表現する

Question

10000 ビットの情報を表現したい (それぞれ 1 または 0 のいずれか)。これを行う方法はありますか？

ウィキペディアは、これを達成するためのちょっとしたハックを説明しています。しかし、10000 ビットを格納するために 2^10000 の大きさの数値を指定するように求められます。

大量のビットを格納する場合でも扱いやすい方法はありますか?

Answer 1

ウィキペディアが説明しているように、ここではビット フィールドが適切な選択です。10,000 ビットを保持できるビット フィールドには、2^10000 の状態があります。

これを行うための適切な選択 (整数が 32/64 ビットであることを考えると) はビット ベクトルです。これについて尋ねられ、ここで非常に詳細に説明されています。

Programming Pearls, 2nd Edition での set のビット ベクトル実装

一般的な考え方は、ビット フィールドとして使用される整数の配列を使用することです。

Answer 2

C++ では、次の 2 つの標準ライブラリ コンテナーのいずれかを使用して、これを非常に簡単に行うことができます。

std::vector<bool>

この標準ベクトルの特殊化は、(ほとんど) 他のベクトルと同じように機能しますが、その内容を要素ごとに 1 ビットに圧縮します。その事実を楽しむだけでなく、ベクトルのように扱うこともできます。

// Create a vector of 10000 booleans
std::vector<bool> lots_of_bits(10000);
// Set all the odd ones to true
for (int i = 1; i < lots_of_bits.size(); i += 2) {
  lots_of_bits[i] = true;
}
// Add another 100 trues at the end
for (int j = 0; j < 100; ++j) {
  lots_of_bits.push_back(true);
}
// etc.

std::bitset<N>

標準コンテナのふりをしない「新しく改良された」ビット ベクトル。特に、これは固定サイズであり、コンパイル時にサイズを知る必要があります。これは少し制限的かもしれませんが、それ以外は非常に便利なクラスです。と同様に、個々のビットを取得および設定するためstd::vector<bool>の演算子を実装します。[]また、ビットごとの論理演算子&、|、 '^' および~(and、or、xor および not)、左右のビットシフト、およびその他のユーティリティもサポートしています。

Answer 3

たとえば、ブールがたくさんある場合は、1ビットを取ることができます。次のように、構造体で：

struct A { bool a:1, b:1, c:1, d:1, e:1; };

変数の数が多い場合、上記の方法は役に立ちません。代わりに、サイズが 10000/4*8 の整数の配列を作成します。ちょうど 10000 ビットが作成されます。これで、offset と << または >> を使用して各ビットにアクセスできます (55 番目のビットにアクセスする場合と同様に、floor(55/4*8) と >>55%32 を使用します。そのビットに到達できます)。

Answer 4

nビット番号へのアクセスにはシフト時間が必要であるという懸念はありますnか? その場合、文字の配列を使用して 10,000 ビットを 10,000 / 8 バケットに分割することで、問題を扱いやすくすることができます (ここでは C または C++ を想定しています)。nこれで、そのビットがどのバケットにあるか ( n / 8)、次にバケット内の位置( ) を把握することで、ビット番号にアクセスできますn % 8。あとはマスキングをするだけです。追加のストレージは必要ありません (最後のパディングを除いて、32 ビットの完全な倍数がない場合は余分なビットが必要です)。