ビットマップの基本的な概念は、ある要素に対応する値を1ビットで表記するというものです。ここで、キーはその要素自体となります。
ビット単位でデータを保存するため、記憶領域を大幅に節約できます。（重要ポイント：記憶領域の節約）
- 必要条件 ====
例えば、20億個のランダムな整数の中に特定の数mが存在するかどうかを見つけるという要件を考えてみましょう。32ビットOSで4GBメモリがあると仮定します。
Javaでは、int型は4バイト、1バイト=8ビット（1 byte = 8 bit）です
- 各数字をintで保存する場合、20億個のintが必要になり、占有スペースは約 (2000000000*4/1024/1024/1024)≈7.45GBになります
- ビット単位で保存する場合、20億個の数値は20億ビットとなり、占有スペースは約 (2000000000/8/1024/1024/1024)≈0.233GBになります
数値をどのように表現するか？
先ほど述べたように、各ビットが1つの数値を表し、0は存在しない、1は存在することを示します。これは二進数の考え方と一致します。
これにより、{1,2,4,6}という数値を簡単に表現できます：
{12,13,15}を表現するにはどうすればよいか？
コンピュータのメモリ割り当ての最小単位はバイト（8ビット）です。では、{12,13,15}を表現するにはどうすればよいでしょうか？
もちろん、別の8ビットを使用して表現します：
これにより、まるで二次元配列のようになります
1つのintは32ビットを占めるため、int配列の長さを int tmp[1+N/32] とすれば、Nは保存する数値の最大値を表し、次のように保存できます：
tmp[0]：0〜31を表現可能
tmp[1]：32〜63を表現可能
tmp[2]：64〜95を表現可能
。。。
こうすることで、任意の整数Mが与えられた場合、M/32でインデックスが、M%32でその位置がわかります
追加
ここで問題があります。数値をどうやって配置するのでしょうか？例えば、5という数字を追加するにはどうすればよいでしょうか？
まず、5/32=0、5%32=5です。つまり、tmp[0]の5番目の位置にあるはずです。そこで、1を左に5ビットシフトし、ビット単位のOR演算を行います。
二進数で表すと：
これは 86 | 32 = 118 と同じことです
86 | (1<<5) = 118
b[0] = b[0] | (1<<5)
つまり、数値を挿入するには、1をその数字を表すビット分左にシフトし、元の値とビット単位のOR演算を行います。
簡略化すると、p + (i/8) | (1<<(i%8)) となります。ここでpは現在の値、iは挿入する数値です
削除
追加の方法はわかりましたが、削除はどうすればよいでしょうか？
先ほどの例で、6を削除する場合を考えてみましょう。
図からわかるように、その数値の位置を0にするだけです。
1を6ビット左にシフトし、ビット単位で反転させ、最後に元の値とビット単位のAND演算を行うことで、その位置を0にできます。
b[0] = b[0] & (~(1<<6))
b[0] = b[0] & (~(1<<(i%8)))
検索
前に述べたように、各ビットは1つの数値を表し、1は存在（または存在する）、0は不存在（または存在しない）を示します。ビットを1または0に設定して追加・削除を行うので、数値が存在するかどうかは、その数値のビットが0か1かを判断するだけです。
例えば、3が存在するかどうかを知りたい場合、b[0] & (1<<3) を判断します。この値が0なら存在しない、1なら存在することを示します。
- ビットマップの用途 ============
高速重複排除
20億個の整数の中から重複しない整数の個数を見つける場合、メモリ容量が20億個の整数を格納するのに十分ではありません。
まず、「メモリ容量が20億個の整数を格納するのに十分ではない」という点から、ビットマップが連想できます。
ここでの重要な問題は、20億個の数字の状態を表現するビットマップをどのように設計するかです。
実際、この問題は非常に簡単です。数字の状態は3つしかありません：「存在しない」「1回だけ存在する」「2回以上存在する」です。
したがって、2ビットを使えば数字の状態を保存できます。数字が存在しない場合を00、1回存在する場合を01、2回以上存在する場合を11と設定しましょう。
これにより、約2GBの保存容量で済みます。
次のタスクは、20億個の数字を配置（保存）することです。対応する状態ビットが00の場合、01に変更して「1回存在する」ことを示します。対応する状態ビットが01の場合、11に変更して「すでに存在する（重複）」ことを示します。11の場合、状態ビットは変更せず、「重複」のままにします。
最後に、状態ビットが01である個数を統計すれば、重複しない数字の個数が得られます。時間計算量はO(n)です。
高速検索
これは前に述べた通りです。int配列の1要素は4バイト（32ビット）を占めるため、32で割ると要素のインデックスがわかり、32で剰余を求め（%32）するとどのビットにあるかがわかります。そのビットが1であれば存在することを示します。
補足1
数字がオーバーフローしない前提で、正数と負数の両方について、左に1ビットシフトは2の1乗倍に相当し、nビット左にシフトすると2のn乗倍になります。右に1ビットシフトは2で割ることと同等で、nビット右にシフトすると2のn乗で割ることと同等です。
<< 左シフト：2のn乗倍に相当します。例：1<<6 は1×64=64に相当、3<<4 は3×16=48に相当
>> 右シフト：2のn乗で割ることに相当します。例：64>>3 は64÷8=8に相当
^ 排他的論理和（XOR）：剰余を求めることに相当します。例：48^32 は48%32=16に相当
補足2
第三の変数を使用せずに、2つの変数の値を交換する
1 // 方法1
2 a = a + b;
3 b = a - b;
4 a = a - b;
5
6 // 方法2
7 a = a ^ b;
8 b = a ^ b;
9 a = a ^ b;
- ビットセット（BitSet） =========
BitSetはビットベクターを実装しており、必要に応じてサイズを拡張できます。各ビットにはブール値が割り当てられています。
BitSetのビットは非負の整数でインデックスできます（つまり、各ビットが非負の整数を表現できます）。
特定のビットを検索、設定、クリアできます。論理演算子を使用して別のBitSetの内容を変更できます。デフォルトでは、すべてのビットの値はfalseです。
前に考えたものとほぼ同じです
long配列を使用して保存し、初期長さは64です。値を設定する際には、まず6ビット右にシフト（64で割るに相当）して配列内の位置を計算し、状態ビットを変更します
他の部分は理解できなくても、この2行を理解すれば十分です：
int wordIndex = wordIndex(bitIndex);
words[wordIndex] |= (1L << bitIndex);