ビット配列

ビット配列（ビットマスク、^[1] ビットマップ、ビットセット、ビット文字列、またはビットベクターとも呼ばれる）は、ビットをコンパクトに格納する配列データ構造です。これは、単純なセットデータ構造を実装するために使用できます。ビット配列は、ハードウェアのビットレベルの並列処理を利用して操作を迅速に実行するのに効果的です。一般的なビット配列にはkwビットが格納されます。ここで、wはバイトやワードなどのストレージ単位のビット数、kは負でない整数です。wが格納されるビット数を割り切れない場合は、内部の断片化によりスペースが無駄になります。

ビット配列は、あるドメイン（ほとんどの場合、整数の範囲）から集合 {0, 1} 内の値へのマッピングです。値は、暗い/明るい、不在/存在、ロック/ロック解除、有効/無効などとして解釈できます。ポイントは、可能な値は 2 つしかないため、1 つのビットに格納できることです。他の配列と同様に、単一ビットへのアクセスは、配列にインデックスを適用することで管理できます。サイズ（または長さ）をnビットとすると、配列を使用してドメインのサブセット（例 {0, 1, 2, ..., n −1}）を指定できます。ここで、1 ビットは集合内に数値が存在することを示し、0 ビットは集合内に数値が存在しないことを示します。この集合データ構造では、約n / wワードのスペースが使用されます。ここで、w は各マシン ワードのビット数です。最小のインデックス番号を示すのが最下位ビット (ワードの) か最上位ビットかはほとんど関係ありませんが、前者の方が好まれる傾向があります (リトルエンディアンマシンの場合)。

有限二項関係は、論理行列と呼ばれるビット配列で表すことができます。関係の計算では、これらの配列はブール演算による行列乗算で構成され、このような合成は関係の合成を表します。^[2]

ほとんどのマシンはメモリ内の個々のビットをアドレス指定できず、単一ビットを操作する命令も持っていませんが、ワード内の各ビットをビット単位の演算を使用して選択して操作することができます。具体的には、次の ようになります。

ORビットを 1 に設定するには、次 を使用します。

   11101 0 10
または 00000 1 00
 = 11101 1 10

ANDビットをゼロに設定するには:

    111010 1 0
そして 111111 0 1
  = 111010 0 0

ANDゼロテストによってビットが設定されているかどうかを判定します。

       1110101 0                 111010 1 0
   かつ 0000000 1            かつ 000000 1 0
     = 0000000 0               = 000000 1 0
(=0 ∴ ビットが設定されていません) (≠0 ∴ ビットが設定されています)

XORビットを反転または切り替えるには:

    11101 0 10 11101 1 10
排他的論理和 00000 1 00 排他的論理和 00000 1 00
  = 11101 1 10 = 11101 0 10

NOTすべてのビットを反転するには:

10110010ではない
  = 01001101

これらの操作に必要なビット マスクを取得するには、ビット シフト演算子を使用して、数値 1 を適切な桁数だけ左にシフトし、必要に応じてビット否定演算を実行します。

集合を表す同じサイズの 2 つのビット配列が与えられた場合、それらの和集合、積集合、集合論的差を、それぞれn / w 個の単純なビット演算 (差の場合は 2 n / w )を使用して計算できます。また、次のいずれかの補数も計算できます。

iは0からn/w-1まで
    complement_a[i] := a[i]ではない
    union[i] := a[i]またはb[i]
    交差点[i] := a[i]かつb[i]
    差[i] := a[i]かつ( b[i]ではない)

ビット配列のビットを反復処理したい場合は、各ワードを 1 つずつループする二重にネストされたループを使用して効率的に実行できます。必要なのはn / w回のメモリ アクセスだけです。

iは0からn/w-1まで
    index := 0 // 必要な場合
    単語 := a[i]
    bは0からw-1まで
        値 := 単語かつ1 ≠ 0
        単語 := 単語を右に 1 シフト
        // 値を使って何かする
        index := index + 1 // 必要な場合

これらのコード サンプルは両方とも理想的な参照の局所性を示しており、その後、データ キャッシュから大幅なパフォーマンスの向上が得られます。キャッシュ ラインがkワードの場合、約n / wk のキャッシュ ミスしか発生しません。

文字列と同様に、長さ、部分文字列、辞書式 比較、連結、逆の操作を定義するのは簡単です。これらの操作の一部は、実装がエンディアンに左右されます。

ビット配列内の 1 ビットの数 (人口カウントまたはハミング重みと呼ばれることもあります) を見つけたい場合は、一連の単純なビット操作を使用してワード内のビット数を計算できる効率的な分岐のないアルゴリズムがあります。各ワードに対してこのようなアルゴリズムを実行し、実行中の合計を保持するだけです。ゼロをカウントする場合も同様です。効率的な実装の例については、 ハミング重みの記事を参照してください。

1 ビット/ピクセルの画像、または一部の FFT アルゴリズムの垂直反転では、個々のワードのビットを反転する必要があります (したがって にb31 b30 ... b0なりますb0 ... b30 b31)。この操作がプロセッサで利用できない場合でも、連続パスで続行することは可能です。この例では 32 ビットです。

2つの16ビットハーフワードを交換する
バイトをペアで交換する (0xddccbbaa -> 0xccddaabb)
...
ビットをペアで交換する
ビットをスワップする (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)

最後の操作は ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)) と記述できます。

find first setまたはfind first one操作は、配列内でインデックスが最小の 1 ビットのインデックスまたは位置を識別します。この操作には、広範なハードウェア サポート (ワード以下の配列の場合) と効率的な計算アルゴリズムがあります。優先キューがビット配列に格納されている場合、find first one を使用して、キュー内で最も優先度の高い要素を識別できます。ワード サイズのfind first oneをより長い配列に拡張するには、最初の 0 以外のワードを見つけてから、そのワードに対してfind first one を実行します。関連する操作find first zero、count leading zeros、count leading ones、count trailing zeros、count trailing ones、およびlog base 2 ( find first setを参照) も、簡単な方法でビット配列に拡張できます。

ビット配列は、「ランダム」なビット、つまり各ビットが 0 または 1 になる可能性が等しく、それぞれが独立しているビットを最も高密度に格納できる方法です。ただし、ほとんどのデータはランダムではないため、よりコンパクトに格納できる可能性があります。たとえば、一般的な FAX 画像のデータはランダムではないため、圧縮できます。これらの長いストリームを圧縮するには、ランレングス符号化がよく使用されます。ただし、ほとんどの圧縮データ形式は、ランダムにアクセスするのがそれほど簡単ではありません。また、ビット配列を過度に圧縮すると、ビットレベルの並列処理 (ベクトル化) による利点が失われるリスクがあります。したがって、ビット配列をビットのストリームとして圧縮する代わりに、バイトまたはワードのストリームとして圧縮する場合があります ( 「ビットマップ インデックス (圧縮) 」を参照)。

ビット配列は、そのシンプルさにもかかわらず、同じ問題に対して他のデータ構造に比べて多くの顕著な利点があります。

• これらは非常にコンパクトです。n個の独立したデータをn / wワードに格納できるデータ構造は他にありません。
• これらにより、メモリにアクセスすることなく、長期間にわたってレジスタ セットに小さなビット配列を保存して操作できるようになります。
• ビットレベルの並列処理を活用し、メモリ アクセスを制限し、データ キャッシュを最大限に活用できるため、実用的なデータ セットでは、漸近的に効率がより高い他の多くのデータ構造よりも優れたパフォーマンスを発揮することがよくあります。

ただし、ビット配列はすべての問題の解決策ではありません。特に、

• 圧縮しないと、スパース セット (範囲に比べて要素が少ないセット) の場合、時間と空間の両方で無駄なセット データ構造になります。このようなアプリケーションでは、代わりに圧縮ビット配列、Judy 配列、トライ、またはBloom フィルターを検討する必要があります。
• 個々の要素にアクセスすることは、言語によってはコストがかかり、表現が難しい場合があります。ランダム アクセスがシーケンシャル アクセスよりも一般的で、配列が比較的小さい場合は、バイト アドレス指定が可能なマシンではバイト配列が適している可能性があります。ただし、マシンがワード アドレス指定のみを備えている場合を除き、ワード配列は、スペースのオーバーヘッドが大きく、追加のキャッシュ ミスが発生するため、おそらく適切ではありません。

ビット配列はコンパクトであるため、スペースや効率が重視される分野でさまざまな用途に使用できます。最も一般的には、ブール フラグの単純なグループやブール値の順序付けられたシーケンスを表すために使用されます。

ビット配列は優先キューに使用され、インデックスkのビットは、キュー内にk がある場合にのみ設定されます。このデータ構造は、たとえばLinux カーネルによって使用され、ハードウェアの find-first-zero 操作から大きな恩恵を受けます。

ビット配列は、メモリ ページ、i ノード、ディスク セクタなどの割り当てに使用できます。このような場合、ビットマップという用語が使用されることがあります。ただし、この用語は、ピクセルごとに複数のビットを使用するラスター イメージを指す場合によく使用されます。

ビット配列のもう 1 つの用途は、ブルーム フィルタです。これは、エラーの確率を低く抑える代わりに、小さなスペースに大きなセットを格納できる確率セット データ構造です。また、偽陽性または偽陰性のいずれかを受け入れるビット配列に基づいて、 確率ハッシュ テーブルを構築することもできます。

ビット配列とその操作は、可能な限り最小限のスペースを使用する簡潔なデータ構造を構築する上でも重要です。このコンテキストでは、 n番目の 1 ビットを検索したり、特定の位置までの 1 ビットの数を数えたりする操作が重要になります。

ビット配列は、圧縮されたデータのストリームを調べるのにも役立つ抽象化です。圧縮されたデータ ストリームには、バイトの一部を占有する要素やバイト整列されていない要素が含まれることがよくあります。たとえば、1 つの 8 ビット文字の圧縮されたハフマン コーディング表現は、1 ビットから 255 ビットの長さになります。

情報検索では、ビット配列は、非常に頻繁に出現する用語のポスティング リストを表すのに適しています。厳密に増加する整数のリストで隣接する値の間のギャップを計算し、単項コーディングを使用してエンコードすると、 nがリスト内にある場合に限り、n番目の位置に 1 ビットがあるビット配列が生成されます。 nのギャップの暗黙の確率は1/2 ⁿです。これは、パラメーター M が 1 であるGolomb コーディングの特殊なケースでもあります。このパラメーターは通常、−log(2 − p ) / log(1 − p ) ≤ 1の場合、つまりおおよそ用語がドキュメントの少なくとも 38% に出現する場合にのみ選択されます。

APLプログラミング言語は、整数とは異なるブールデータ型として、任意の形状とサイズのビット配列を完全にサポートします。すべての主要な実装 ( Dyalog APL、APL2、APL Next、NARS2000、Gnu APLなど) は、マシンワードのサイズに関係なく、ビットを密にパックします。ビットには、通常のインデックス表記 (A[3]) を介して個別にアクセスできるほか、通常のプリミティブ関数と演算子のすべてを介してアクセスできます。これらの関数と演算子では、バイトのテーブル参照を介してビットを合計するなどの特殊なアルゴリズムを使用して操作されることがよくあります。

Cプログラミング言語のビット フィールドは、あるビット数に等しいサイズを持つ構造体にある疑似オブジェクトで、実際には小さなビット配列です。ワードにまたがることはできないという制限があります。便利な構文を提供しますが、ほとんどのマシンでは、ビットは依然としてバイト単位の演算子を使用してアクセスされ、静的にしか定義できません (C の静的配列のように、サイズはコンパイル時に固定されます)。また、C プログラマーがワードを小さなビット配列として使用し、ビット演算子を使用してそのビットにアクセスするのも一般的なイディオムです。X11 システムに含まれる広く利用可能なヘッダー ファイルxtrapbits.hは、「システムがビット配列のビット フィールド操作を定義するための移植可能な方法」です。前述のアプローチのより詳しい説明は、comp.lang.c の faq にあります。

C++では、個々のboolは通常バイトまたは整数と同じ空間を占有しますが、 STL型は、空間効率の最適化としてビットがパックされる部分的なテンプレート特殊化vector<bool>です。バイト (ビットではなく) は C++ での最小のアドレス指定可能な単位であるため、[] 演算子は要素への参照を返さず、プロキシ参照 を返します。これは些細な点のように思えるかもしれませんが、 は標準の STL コンテナではないことを意味し、 の使用は一般に推奨されません。もう 1 つのユニークな STL クラスである、^{[3] は}、コンパイル時に特定のサイズに固定されたビットのベクトルを作成し、そのインターフェイスと構文は、C プログラマによるビット セットとしてのワードの慣用的な使用に似ています。また、設定されているビットの数を効率的にカウントする機能など、いくつかの追加の機能もあります。Boost C++ ライブラリは、実行時にサイズが指定される クラス^[4]を提供します。vector<bool>vector<bool>bitsetdynamic_bitset

Dプログラミング言語は、標準ライブラリ Phobos でビット配列を提供しますstd.bitmanip。C++ と同様に、[] 演算子は参照を返しません。これは、ほとんどのハードウェアでは個々のビットを直接アドレス指定できないためです。代わりに、を返しますbool。

Javaでは、クラスはBitSetビット配列を作成し、C プログラマーに馴染みのあるビット演算子にちなんで名付けられた関数で操作します。C bitset++ とは異なり、Java にはBitSet「サイズ」状態がありません (実質的には無限サイズで、0 ビットで初期化されます)。ビットは任意のインデックスで設定またはテストできます。さらに、ビット フィールドのより安全な代替手段として、列挙型EnumSetの値のセットを内部的にビット ベクトルとして表すクラスがあります。

.NET Framework はコレクション クラスを提供しますBitArray。このクラスは、配列型を使用してビットを格納しますint(配列の各要素は通常 32 ビットを表します)。^[5]このクラスはランダム アクセスとビット演算子をサポートし、反復処理が可能で、Lengthプロパティを変更してサイズを拡大または切り捨てることができます。

Standard ML はビット配列をサポートしていませんが、Standard ML of New JerseyBitArrayの SML/NJ ライブラリには拡張機能である構造体があります。この構造体はサイズが固定されておらず、セット演算とビット演算 (異例ですがシフト演算を含む) をサポートしています。

同様に、 Haskell も現在、ビット演算の標準サポートを欠いていますが、GHCと Hugs はどちらもData.Bits、シフト演算や回転演算などのさまざまなビット関数と演算子を備えたモジュールを提供しており、ブール値の「ボックス化されていない」配列を使用して Bit 配列をモデル化することもできますが、これは前者のモジュールからのサポートがありません。

Perlでは、文字列は拡張可能なビット配列として使用できます。通常のビット演算子（~ | & ^）を使用して操作することができ、^[6] vec関数を使用して個々のビットをテストおよび設定できます。^[7]

Rubyでは、ビットの配列であるかのように、 括弧演算子 ( ) を使用して整数 (Fixnumまたは)のビットにアクセスできます (設定はできません) 。Bignum[]

Apple のCore Foundationライブラリには、CFBitVector および CFMutableBitVector 構造体が含まれています。

PL/I は、固定長または可変長の任意の長さのビット文字列の配列をサポートします。配列要素は、整列されている場合(各要素はバイトまたはワード境界で始まります)、または非整列の場合(要素がパディングなしですぐに連続する場合) があります。

PL/pgSQLとPostgreSQLのSQLはビット文字列をネイティブ型としてサポートしています。SQLビット型には と の2つがあり、は正の整数です。^[8]bit(n)bit varying(n)n

VHDL、Verilog、SystemVerilogなどのハードウェア記述言語は、フリップフロップ、ハードウェアバス、ハードウェア信号などのストレージ要素をモデル化するために使用されるビットベクターをネイティブでサポートしています。OpenVera、 e、SystemVerilogなどのハードウェア検証言語では、ビットベクターはハードウェアモデルから値をサンプリングし、シミュレーション中にハードウェアに転送されるデータを表すために使用されます。

Common Lisp は、bit-vector組み込みの の特殊なケースとして1 次元実装を提供しarray、クラスと型指定子の両方の役割を果たします。^[9]make-array配列の派生であるため、の要素型で設定される一般的な関数に依存しておりbit、これにより、ビット ベクトルを動的にサイズ変更可能として指定することもできます。bit-vectorただし、 の範囲は無限ではありません。simple-bit-vector動的な特性を明示的に除外する、より制限された型が存在します。^{[10]ビット ベクトルは、}リーダー マクロ として表され、より簡潔な方法で構築できます。^[11]すべての配列に適用可能な一般的な関数に加えて、ビット ベクトル専用の操作が存在します。単一のビットには、関数と関数を使用してアクセスおよび変更でき^[12]、広範な論理操作がサポートされています。^[13]#*bitsbitsbit

• 算術論理ユニット
• バイナリコード
• 二進法
• Bitboard Chess および類似のゲーム。
• ビットフィールド
• ビットマップインデックス
• ビットストリーム
• 2つの要素からなる有限体、またはGF(2)
• ジュディ配列
• 可変長コード

• 数学的基数 2019-10-16にWayback Machineでアーカイブされました。著者: Pr. DEKnuth
• vector<bool> は非準拠であり、最適化の選択を強制します
• vector<bool>: 問題が増えれば、解決策も改善される