[C#] System.Collections.BitArray — ビット列を効率的に扱う固定長コレクション

System.Collections.BitArray は、真偽値（ビット）を 1 ビット単位で詰めて保持する固定長コレクション です。bool[] が 1 要素 1 バイト消費するのに対し、BitArray は 1 要素 1 ビット で済むためメモリ効率が約 8 倍。さらにコレクション全体を対象としたビット演算（And／Or／Xor／Not）が用意されており、エラトステネスの篩や集合演算など 数値的なビット操作 に強みを発揮します。

`BitArray` とは

名前空間：System.Collections
内部構造：int[]（32 ビット整数の配列）に 32 ビットずつパックして格納
長さは固定（生成時に決定）。Length を変えると配列が再確保される
要素は bool 値（インデックスでアクセス）

using System.Collections;

var bits = new BitArray(8);     // 全 false で 8 ビット
bits[0] = true;
bits[3] = true;

var fromBytes = new BitArray(new byte[] { 0b1010_0110 }); // 8 ビット
var fromInts  = new BitArray(new[] { 0x12345678 });        // 32 ビット
var fromBools = new BitArray(new[] { true, false, true });

サポートするインターフェース

インターフェース	役割
`ICollection`	`Count` / `CopyTo` / `IsSynchronized` / `SyncRoot`
`IEnumerable`	`foreach` で `bool` を列挙
`ICloneable`	`Clone()` で浅いコピー（中身は値型なので実質深いコピー）

BitArray は IList を実装していない点に注意してください。長さが固定 で要素の追加・削除という概念がないためです。IsFixedSize のような属性ではなく、IList 自体を実装しないことで「配列的な可変長操作はできない」と表現しています。

ICollection の詳細は ArrayList の記事、IEnumerable は IEnumerable と IEnumerator の記事、ICloneable は ICloneable インターフェースの記事を参照してください。

BitArray.Clone() は新しい int[] バッファを確保するため、実質的に深いコピー が得られます。

var a = new BitArray(new[] { true, false, true });
var b = (BitArray)a.Clone();
b[0] = false;
Console.WriteLine(a[0]); // True（独立している）

主な API

インデックスアクセス

var bits = new BitArray(16);
bits[5] = true;           // セット
bool b = bits[5];          // ゲット
bits.Set(7, true);         // メソッド版
bits.SetAll(false);        // 全ビットを false に

ビット演算

BitArray の真骨頂は コレクション同士のビット演算 が一発で書けることです。

var a = new BitArray(new[] { true,  false, true,  false });
var b = new BitArray(new[] { true,  true,  false, false });

a.And(b);  // [true, false, false, false]   破壊的：a が書き換わる
a.Or(b);   // ビット OR
a.Xor(b);  // ビット XOR
a.Not();   // ビット反転

これらはすべて a 自身を書き換えて a を返す API です。元を残したいなら (BitArray)a.Clone() してから演算してください。

var result = ((BitArray)a.Clone()).And(b);

長さが異なる BitArray 同士で演算すると ArgumentException がスローされます。

シフト（.NET Core 3.0+）

var x = new BitArray(new[] { true, false, true, true });
x.RightShift(1); // [false, true, false, true]
x.LeftShift(2);  // [false, false, false, true]

`Length`

bits.Length = 100; // 拡張時は false で埋められる、縮小時は切り捨て

計算量とメモリ

操作	計算量	備考
`bits[i]` の get/set	O(1)	ビットマスク 1 回
`And` / `Or` / `Xor` / `Not`	O(n / 32)	32 ビット単位で処理
`LeftShift` / `RightShift`	O(n / 32)
`CopyTo`	O(n)
`Length` 変更	拡張時 O(n)	内部配列を再確保

メモリ使用量はおおよそ (Length + 31) / 32 * 4 バイト。100 万ビットでも約 125 KB に収まります。

他選択肢との比較

用途	候補	コメント
真偽値の固定長配列	`bool[]`	1 要素 1 バイト。シンプルで速いが 8 倍のメモリ
ビットフラグ集合	`BitArray`	ビット演算がワンライナー、メモリ効率良
~32/64 個程度のフラグ	`enum [Flags]` + `int`/`long`	スタックに乗る軽量版。`HasFlag` で判定
整数集合	`HashSet<int>`	疎な集合に向く。密ならメモリで負ける
大規模・固定範囲の集合	`BitArray`	範囲が決まっていて密なら最強

使いどころ — エラトステネスの篩

範囲が決まっていて、要素が 密に存在する真偽値集合 を扱うときに BitArray は輝きます。古典的な例がエラトステネスの篩です。

static IEnumerable<int> Sieve(int max)
{
    var isComposite = new BitArray(max + 1); // 既定は false
    for (int i = 2; i * i <= max; i++)
    {
        if (!isComposite[i])
        {
            for (int j = i * i; j <= max; j += i)
                isComposite[j] = true;
        }
    }
    for (int i = 2; i <= max; i++)
        if (!isComposite[i]) yield return i;
}

foreach (var p in Sieve(100)) Console.Write($"{p} ");
// 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

bool[] でも書けますが、max = 10_000_000 規模になるとメモリ差（10 MB vs 1.25 MB）と GC 圧で BitArray の優位が見えてきます。

集合演算

権限ビットマップやフィーチャーフラグの ON/OFF を 大量に AND/OR したい ような用途にも向きます。

var canRead   = LoadPermissions("read");
var canWrite  = LoadPermissions("write");
var canManage = ((BitArray)canRead.Clone()).And(canWrite); // 読み書き両方可

注意点

Length は固定。動的に伸縮させたいときは List<bool> を使うか、最大長で確保してから論理長を別途管理する。
ジェネリックではない。とはいえ要素は常に bool なので ArrayList のようなボックス化問題はない。
ビット演算は 破壊的。元を残したいなら必ず Clone()。
長さが揃っていない BitArray 同士の演算は例外。Length を揃えてから渡す。

まとめ

BitArray は 固定長のビット集合。内部は int[] に 32 ビットずつパック。
ICollection / IEnumerable / ICloneable を実装。IList は実装しない。
要素アクセスは O(1)、コレクション全体のビット演算は O(n / 32)。
メモリは bool[] の約 1/8。範囲が決まった密な真偽値集合に最適。
エラトステネスの篩、フラグ集合の AND/OR、固定サイズのビットマスク管理が典型的な使いどころ。

BitArray とは