ビット配列

ビット配列（、ビットマップ、ビットセット、ビット列、ビットベクタとも呼ばれる）とは、ビットを効率的に格納する配列データ構造を指す。集合の簡単な実装にも利用できる。ビット配列はハードウェアのを活かして高速に演算を行う点で優れている。典型的なビット配列はビットを格納する。ここではバイトやワードなどの格納単位のビット数、は正の整数である。が格納するビット数を割り切れない場合、によって一部の領域が無駄になる。

定義ビット配列は、ある定義域（ほぼ常に整数の範囲）からの集合の値への写像である。これらの値は、暗/明、不在/存在、ロック/アンロック、無効/有効などと解釈できる。重要な点は取りうる値が2種類しかないため、1ビットで格納できることである。他の配列と同様に、インデックスを適用することで個々のビットへのアクセスが可能である。サイズ（長さ）を n ビットとすると、この配列は定義域の部分集合（例: ）を表すことができ、-ビットは集合内に数が存在することを、-ビットは不在を示す。この集合データ構造は約ワードの空間を使用する（は各マシンワードのビット数）。ワードの最下位ビットと最上位ビットのどちらが最小インデックスを表すかは基本的に任意だが、前者が優先される傾向にある（リトルエンディアンのマシンで）。

有限二項関係は、論理行列と呼ばれるビット配列で表現できる。では、これらの配列はブール演算を使った行列の乗法によって合成され、その合成は関係の合成を表す。

基本演算ほとんどのマシンはメモリ上の個々のビットをアドレス指定したり単一ビットを操作する命令を持っていないが、ビット演算を使えばワード内の各ビットを取り出して操作できる。具体的には:

OR でビットを1にセット: 11101010 OR 00000100 = 11101110 AND でビットを0にクリア: 11101010 AND 11111101 = 11101000 AND によるビット検査（ゼロテスト）: 11101010 AND 00000001 = 00000000 （0はビットがセットされていないことを意味する）

11101010 AND 00000010 = 00000010 （非ゼロはビットがセットされていることを意味する） XOR によるビットの反転: 11101010 XOR 00000100 = 11101110

11101110 XOR 00000100 = 11101010 NOT による全ビット反転: NOT 10110010 = 01001101

これらの演算に必要なビットマスクを得るには、ビットシフト演算子で1を適切な桁数だけ左シフトし、必要に応じてビット否定を適用すればよい。

同じサイズの2つのビット配列が集合を表す場合、それぞれ回の単純なビット演算（差集合は回）で和集合、積集合、差を計算でき、どちらかの補集合も同様に計算できる:

for i from 0 to n/w-1 complement_a[i] := not a[i] union[i] := a[i] or b[i] intersection[i] := a[i] and b[i] difference[i] := a[i] and (not b[i])

ビット配列のビットを順に処理したい場合、各ワードを順に処理する二重ネストループで効率よく行える。必要なメモリアクセスは回のみである:

for i from 0 to n/w-1 index := 0 // 必要に応じて word := a[i] for b from 0 to w-1 value := word and 1 ≠ 0 word := word shift right 1 // valueを使って処理 index := index + 1 // 必要に応じて

これらのコードはいずれも理想的な参照の局所性を示し、データキャッシュメモリによって大幅な性能向上が得られる。キャッシュラインがワードの場合、キャッシュミスは約回だけ発生する。

より複雑な演算

文字列と同様に、長さ、部分列、辞書順比較、連結、反転などの演算を定義することは簡単である。これらの演算の実装はエンディアンに依存することがある。

人口カウント / ハミング重みビット配列中の1ビットの数（ポピュレーションカウントまたはハミング重みと呼ばれることもある）を求めたい場合、ワード内のビット数を一連の単純なビット演算で計算できる分岐なしの効率的なアルゴリズムが存在する。このアルゴリズムを各ワードに実行し、合計を累積していけばよい。ゼロビットの計数も同様である。効率的な実装例についてはハミング重みの記事を参照。

反転

1ビット/ピクセルの画像の垂直反転や一部のFFTアルゴリズムでは、個々のワードのビットを反転する（b31 b30 ... b0 を b0 ... b30 b31 にする）必要がある。プロセッサにこの演算がない場合でも、例えば32ビットに対して順次パスで処理できる:

exchange two 16-bit halfwords exchange bytes by pairs (0xddccbbaa -> 0xccddaabb) ... swap bits by pairs swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)

The last operation can be written ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).

先頭1ビット検索（find first one）演算は、配列中で最小インデックスを持つ1ビットのインデックスまたは位置を特定するもので、（ワードより大きくない配列に対して）広くハードウェアでサポートされており、効率的なアルゴリズムが存在する。ビット配列に優先度付きキューを格納する場合、先頭1ビット検索でキュー内の最高優先度要素を特定できる。ワードサイズの先頭1ビット検索を長い配列に拡張するには、最初の非ゼロワードを見つけてそのワードに対して先頭1ビット検索を実行すればよい。関連演算である先頭0ビット検索、先頭ゼロカウント、先頭1カウント、末尾ゼロカウント、末尾1カウント、2の対数（find first set参照）も同様にビット配列に拡張できる。

圧縮

ビット配列は「ランダム」なビット（各ビットが等確率で0または1であり互いに独立な場合）に対して最も高密度な格納形式である。しかし多くのデータはランダムではないため、より圧縮して格納できる場合がある。例えば典型的なFAX画像はランダムではなく圧縮可能である。連長圧縮はこのような長いビット列の圧縮によく使われる。ただし多くの圧縮データ形式はランダムアクセスが容易でなく、ビット配列を過度に圧縮するとビットレベル並列性（ベクトル化）の恩恵を失うリスクもある。そのためビット配列をビットストリームとして圧縮する代わりに、バイトやワードのストリームとして圧縮する方法も考えられる（参照）。

利点と欠点ビット配列はその単純さにもかかわらず、同じ問題に対する他のデータ構造と比べて際立った利点がある: 極めてコンパクトである。ワードに個の独立したデータを格納できるデータ構造は他にない。小さなビット配列をメモリアクセスなしにレジスタ集合に長時間格納・操作できる。ビットレベル並列性の活用、メモリアクセスの削減、キャッシュメモリの最大活用により、漸近的に効率的な構造を含む多くのデータ構造を実際のデータ集合で上回ることが多い。

ただしビット配列が万能なわけではなく、特に以下の場合には適さない: 圧縮なしでは、疎な集合（範囲に対して要素数が少ない集合）に対して時間・空間ともに非効率なデータ構造になる。そのような用途には圧縮ビット配列、、トライ、ブルームフィルタなどが適している。個々の要素へのアクセスはコストがかかり、一部の言語では表現が難しい。ランダムアクセスがシーケンシャルアクセスより多く配列が比較的小さい場合は、バイトアドレス指定可能なマシンではバイト配列の方が好ましいこともある。ワード配列はそのスペースオーバーヘッドと追加のキャッシュミスのため、ワードアドレス指定のみのマシンでない限りほとんど正当化できない。

応用コンパクトさゆえに、ビット配列はスペースや効率が重視される分野で多くの用途がある。最も一般的には、単純なブールフラグのグループや順序付きブール値列の表現に使われる。

ビット配列は優先度付きキューに使われる。インデックスのビットはがキューに含まれる場合にのみセットされる。このデータ構造は例えばLinuxカーネルで使われており、ハードウェアの先頭ゼロビット検索命令の恩恵を大きく受ける。

ビット配列は、Inode、ディスクセクタなどの割り当てに使われる。この場合「ビットマップ」という用語が使われることがある。ただしこの用語は複数ビット/ピクセルを使うラスターグラフィックスを指すことも多い。

ブルームフィルタもビット配列の応用例である。これは少量のエラー確率と引き換えに大きな集合を小さな空間に格納できる確率的集合データ構造である。また偽陽性または偽陰性のどちらかを許容するビット配列ベースの確率的ハッシュテーブルを構築することも可能である。

ビット配列とその演算は、最小限の空間を使う簡潔データ構造の構築にも重要である。この文脈では、番目の1ビットを見つけたり特定の位置までの1ビット数を数えるなどの演算が重要になる。

ビット配列は圧縮データストリームを検査する抽象化としても有用である。圧縮データはバイトの一部を占めたりバイト境界に整列していない要素を含むことが多い。例えば1つの8ビット文字のハフマン符号表現は1ビットから255ビットの長さになりえる。

情報検索では、ビット配列は非常に頻出する語句のの良い表現形式である。単調増加整数リストの隣接値間のギャップを計算して一進符号で符号化すると、がリストに含まれる場合にのみ番目の位置に1ビットを持つビット配列になる。ギャップがである確率はと推測される。これはパラメータが1のゴロム符号の特殊ケースでもある。このパラメータはのとき、つまりおおよそ38%以上の文書にその語句が出現するときにのみ通常選択される。

使用例 IPv4アドレスの大きなファイル（100GB超）からユニークなアドレスを数える例を示す。汎用のmap[string]boolを使うと64GB超のRAMが必要になるため、Goでビットマップを使う:package main

import ( "bufio" "fmt" "math/bits" "os" )

// bitsetSizeは2^32ビット（512 MiB）に必要なバイト数 const bitsetSize = 1 << 29

func main() { file, err := os.Open("ip_addresses") if err != nil { fmt.Println("Error opening file:", err) return } defer file.Close()

bitset := [bitsetSize]byte{}

// より大きなバッファを持つバッファ付きスキャナーを使用 scanner := bufio.NewScanner(file) const maxBuffer = 64 * 1024 // 64 KBバッファ buf := make([]byte, 0, maxBuffer) scanner.Buffer(buf, maxBuffer)

// 各行を処理 for scanner.Scan() { line := scanner.Bytes()

// バイト列からIPv4アドレスを手動でパース ip := parseIPv4(line) // ビットをセット byteIndex := ip >> 3 // 8で割る bitIndex := ip & 7 // ビット位置 0-7 bitset[byteIndex] |= 1 << bitIndex

// スキャンエラーのチェック if err := scanner.Err(); err != nil { fmt.Println("Error reading file:", err) return

var count uint64 for i := 0; i < bitsetSize; i++ { count += uint64(bits.OnesCount8(bitset[i]))

fmt.Println("Number of unique IPv4 addresses:", count) }

func parseIPv4(line []byte) (ip uint32) { i := 0

// オクテット1 n := uint32(line[i] - '0') for i = 1; line[i] != '.'; i++ { n = n*10 + uint32(line[i]-'0') } ip |= n << 24 i++ // ドットをスキップ

// オクテット2 n = uint32(line[i] - '0') i++ for ; line[i] != '.'; i++ { n = n*10 + uint32(line[i]-'0') } ip |= n << 16 i++ // ドットをスキップ

// オクテット3 n = uint32(line[i] - '0') i++ for ; line[i] != '.'; i++ { n = n*10 + uint32(line[i]-'0') } ip |= n << 8 i++ // ドットをスキップ

// オクテット4 n = uint32(line[i] - '0') i++ for ; i < len(line); i++ { n = n*10 + uint32(line[i]-'0') } ip |= n

return ip }

言語サポートビット配列は多くのプログラミング言語で、専用のインターフェースまたはより汎用的なビット操作機能を通じてサポートされている。

APLプログラミング言語は、整数とは異なるブールデータ型として任意の形状・サイズのビット配列を完全にサポートしている。主要な実装（Dyalog APL、APL2、APL Next、NARS2000、Gnu APLなど）はすべてビットをマシンワードサイズに密にパックする。ビットには通常のインデックス記法（例: A）でアクセスでき、通常の基本関数や演算子でも操作できる。その際、バイトのテーブル参照によるビット総和など特殊なアルゴリズムが使われることが多い。

C言語のビットフィールドは、構造体内でビット数を指定したサイズを持つ疑似オブジェクトであり、実質的には小さなビット配列である。ただしワードをまたぐことができないという制限がある。便利な構文を提供するが、ほとんどのマシンではバイト単位演算子でビットにアクセスし、静的にしか定義できない（Cの静的配列と同様、サイズはコンパイル時に固定される）。Cプログラマーがワードを小さなビット配列として使いビット演算子でビットにアクセスするのも一般的な慣用法である。X11システムに含まれる広く利用可能なヘッダファイル <xtrapbits.h> は「システムがビット配列のビットフィールド操作を定義するための移植可能な方法」とされている。上記アプローチの詳しい解説は comp.lang.c FAQ で参照できる。

C++では、個々のboolは通常バイトまたは整数と同じ空間を占めるが、STL型std::vector<bool>は空間効率最適化としてビットをパックするテンプレートの部分特殊化である。C++ではバイト（ビットではない）が最小アドレス単位であるため、[]演算子は要素への参照ではなくプロキシ参照を返す。これは些細な点に見えるかもしれないが、vector<bool>が標準STLコンテナではないことを意味し、そのため一般的に使用が推奨されない。別の固有のSTLクラス std::bitset<N>は、コンパイル時に特定のサイズ N に固定されたビットベクタを作成し、そのインターフェースや構文はCプログラマーがビットセットとしてワードを使う慣用法に近い。セットされたビットの数を効率的に数える機能など追加の機能もある。と同様、bitsetのサイズはコンパイル時に指定する必要があり、コンパイラが推論することはできない。Boost C++ライブラリは実行時にサイズを指定できる boost::dynamic_bitset クラスを提供している。

D言語は標準ライブラリPhobosの std.bitmanip でビット配列をサポートしている。C++と同様に、個々のビットはほとんどのハードウェアで直接アドレス指定できないため、[]演算子は参照ではなくboolを返す。

Javaでは、クラスjava.util.BitSetがビット配列を作成し、Cプログラマーが使うビット演算子にちなんだ関数名で操作する。C++のbitsetと異なり、JavaのBitSetには「サイズ」状態がない（実質的に無限のサイズを持ち、0ビットで初期化される）。任意のインデックスのビットをセットまたはテストできる。またjava.util.EnumSet<E>クラスは列挙型の値の集合を内部的にビットベクタとして表現し、ビットフィールドのより安全な代替となる。

.NET FrameworkはSystems.Collections.BitArrayコレクションクラスを提供する。int型の配列を使ってビットを格納する（配列の各要素は通常32ビットを表す）。ランダムアクセスとビット演算をサポートし、イテレーション可能で、Lengthプロパティでサイズの変更が可能である。

Standard MLはビット配列をネイティブサポートしていないが、Standard ML of New JerseyはそのSML/NJライブラリにBitArray構造体の拡張を持つ。サイズは固定でなく、集合演算とビット演算（シフト演算を含む、これは珍しい）をサポートする。

Haskellも現在ビット演算の標準サポートを欠いているが、GHCとHugsはシフト・ローテート演算やその他のビット操作関数・演算子を含むData.Bitsモジュールを提供している。ブール値の「アンボックス化」配列でビット配列をモデル化することもできるが、前述のモジュールからのサポートは得られない。

Perlでは、文字列を拡張可能なビット配列として使える。通常のビット演算子（~、|、&、^）で操作でき、vec関数で個々のビットのテストやセットが可能である。

Rubyでは、整数（FixnumまたはBignum）のビットにブラケット演算子（[]）でアクセス（ただし設定は不可）できる。配列のように使える。

Rustはビット演算を使ってネイティブな数値型を固定幅ビット配列として使うことをサポートしている。bitvecなどのサードパーティライブラリが専用のインターフェースを提供している。かつてはstd::collections::BitSetとstd::collections::BitVecという型があったが、バージョン1.3.0で非推奨となり2015年に削除された。

AppleのCore FoundationライブラリにはCFBitVectorとCFMutableBitVector構造体が含まれる。

PL/Iは任意の長さのビット列の配列をサポートし、固定長または可変長のどちらもとれる。配列要素は整列（各要素がバイトまたはワード境界から開始）または非整列（パディングなしで要素が連続）のどちらかになる。

PL/pgSQLとPostgreSQLのSQLはビット列をネイティブ型としてサポートしている。bit(n)とbit varying(n)の2つのSQLビット型がある（nは正の整数）。

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

Common Lispは多次元ビット配列を提供する。1次元のbit-vector実装は組み込みのarrayの特殊ケースとして提供され、クラスおよび型指定子として二重の役割を持つ。ビット配列（したがってビットベクタ）は、要素型をbitに設定した汎用のmake-array関数で設定でき、オプションで動的リサイズ可能なビットベクタを指定できる。ただしbit-vectorは無限の長さを持たない。より制限されたsimple-bit-vector型も存在し、動的な特性を明示的に除外する。ビットベクタはリーダーマクロ #*bitsでより簡潔に表現・構築できる。すべての配列に適用可能な汎用関数に加えて、ビット配列専用の演算も存在する。個々のビットにはbitおよびsbit関数でアクセス・修正でき、多数の論理演算がサポートされている。

ビット配列

Źródło i licencja