ビットマスクのサイズに実用的な制限はありますか？

StackOverflow https://stackoverflow.com/questions/177054

  •  05-07-2019
  •  | 
  •  

質問

ビットマスクを使用して、1つの変数に複数の値を保存する一般的な方法があります。たとえば、ユーザーがアイテムの読み取り、書き込み、実行の権限を持っている場合、 read = 4（2 ^ 2）、write = 2（2 ^ 1）、execute =と言うことで単一の数値に変換できます。 1（2 ^ 0）を追加して7を取得します。

この手法はいくつかのWebアプリケーションで使用します。通常、変数をフィールドに格納し、異なる値の数に応じてMEDIUMINTまたは任意のタイプを指定します。

私が興味を持っているのは、このように保存できる値の数に実際的な制限があるかどうかです。たとえば、数値が64を超えると、（64ビット）整数を使用できなくなります。この場合、何を使用しますか？プログラムロジックにどのように影響しますか（つまり、ビット単位の比較を使用できますか）

非常に大きな値のセットを取得し始めると、別の方法が最適なソリューションになることはわかっていますが、 this メソッドの境界に興味があります。

役に立ちましたか？

解決

頭から離れて、バイトの配列と配列内のビットオフセットを取得できる set_bit および get_bit 関数を記述し、使用します配列内の適切なビットを設定/取得するためのビット調整。次のようなものです（Cで、しかしうまくいけばアイデアが得られます）：

// sets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// result is 0 on success, non-zero on failure (offset out-of-bounds)
int set_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //set the right bit
  bytes[offset >> 3] |= (1 << (offset & 0x7));

  return 0; //success 
}

//gets the n-th bit in |bytes|. num_bytes is the number of bytes in the array
// returns (-1) on error, 0 if bit is "off", positive number if "on"
int get_bit(char* bytes, unsigned long num_bytes, unsigned long offset)
{
  // make sure offset is valid
  if(offset < 0 || offset > (num_bytes<<3)-1) { return -1; }

  //get the right bit
  return (bytes[offset >> 3] & (1 << (offset & 0x7));
}

他のヒント

ビットマスクがマシンワードよりも何倍も大きいファイルシステムコードでビットマスクを使用しました。 「ブール値の配列」のように考えてください。

（知りたい場合はフラッシュメモリのジャーナリングマスク）

多くのコンパイラーがこれを行う方法を知っていますあなたのため。 OOコードを少し追加して、賢明に動作する型を持たせると、コードはビットバンギングではなく意図通りに見え始めます。

私の2セント。

64ビット整数では、最大2 ^ 64-1までの値を保存できます。64は2 ^ 6のみです。はい、制限がありますが、64を超えるフラグが必要な場合は、それらがすべて何をしていたかを知りたいと思います：）

潜在的に考える必要がある州はいくつありますか？ 64の潜在的な状態がある場合、それらが存在できる組み合わせの数は、64ビット整数のフルサイズです。

128個のフラグについて心配する必要がある場合は、ビットベクトルのペアで十分です（2 ^ 64 * 2）。

追加：プログラミングパールでは、長さ10 ^ 7のビット配列の使用に関する拡張議論があり、整数で実装されています（使用された800個の数字を保持するため）-非常に高速で非常に適切ですその章で説明されているタスクのため。

一部の言語（perlはそうだと思いますが、確かではありません）は、文字列のビット演算を許可します。はるかに大きな有効範囲を与えます。 （（strlen * 8bit chars）の組み合わせ）

ただし、複数の/ type /データの重ね合わせに単一の値を使用することはありません。 3ビット整数の基本的なr / w / xトリプレットは、おそらく「実用的」な上位です。制限は、スペース効率の理由ではなく、実際の開発上の理由のためです。

（Phpはこのシステムを使用してエラーメッセージを制御しますが、PHPの定数が存在しない値を定義する必要があり、整数を手動で生成する必要がある場合、それが少し過剰であることがすでにわかっています、正直なところ、chmodが 'ugo + rwx'スタイルの構文をサポートしていなかった場合、マジックナンバーを思い出せないので、使用したくありません）

行き過ぎたコードをデバッグするために定数テーブルをクラックする必要がある瞬間。

古いスレッドですが、肥大化したビットマスクが必要な場合があることに注意する価値があります。たとえば、分子指紋は、多くの場合、32個のbigintフィールドにパックした1024ビット配列として生成されます（SQL ServerはUInt32をサポートしていません）。ビット単位の操作は正常に機能します。テーブルが大きくなり始め、個別の関数呼び出しが遅いことに気付くまでです。バイナリデータ型は機能しますが、2つのバイナリオペランドを持つビットごとの演算子に対するT-SQLの禁止ではありません。

たとえば、.NETは、整数の配列をBitArrayクラスの内部ストレージとして使用します。 実際には他に方法はありません。

つまり、SQLでは、すべての状態を格納するために複数の列が必要です（またはBLOBを使用します）。

この質問にSQLをタグ付けしたので、整数のサイズを見つけるには、データベースのドキュメントを参照する必要があると思います。次に、安全のために、符号の1ビットを減算します。

編集：コメントには、MySQLを使用していると書かれています。 MySQL 5.0 Numeric Types のドキュメントには、 NUMERICの最大サイズは64または65桁です。 64桁で212ビットです。

選択した言語がこれらの数字を処理できる必要があることを忘れないでください。そのため、いずれにしても64ビット整数に制限される可能性があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top