最初の 3 つの定数は相互に関連しています。 BITSPERWORD は 32 です。これは、コンパイラとアーキテクチャに基づいて設定する必要があります。 2^5 =32 であるため、SHIFT は 5 です。同様に、MASK =BITSPERWORD - 1.
ビットセットは、概念的には単なるビットの配列です。この実装は、実際には int の配列を使用し、int あたり 32 ビットを想定しています。したがって、ビットを設定、クリア、またはテスト (読み取り) するときはいつでも、次の 2 つのことを理解する必要があります。
- それが (配列の) どの int にあるか
- その int のどのビットについて話しているのか
int ごとに 32 ビットを想定しているため、32 で除算 (および切り捨て) するだけで、必要な配列インデックスを取得できます。 32 で割ること (BITSPERWORD) は、5 だけ右にシフトすること (SHIFT) と同じです。それが a[i>>SHIFT] ビットの目的です。これを a[i/BITSPERWORD] として記述することもできます (実際、コンパイラに適切なオプティマイザーがあると仮定すると、おそらく同じか、または非常によく似たコードが得られるでしょう)。
a のどの要素が必要かがわかったので、次はどのビットかを把握する必要があります。本当に、残りが欲しいです。 i%BITSPERWORD を使用してこれを行うこともできますが、i&MASK が同等であることがわかります。これは、BITSPERWORD が 2 の累乗 (この場合は 2^5) であり、MASK がすべて設定された下位 5 ビットであるためです。
基本的には、最適化されたバケット ソートです:
- 長さ n ビットのビット配列を予約します。
- ビット配列をクリアします (最初にメインで)。
- 項目を 1 つずつ読み上げます (項目はすべて別個のものでなければなりません)。
- 読み取り番号が i の場合、ビット配列の i 番目のビットを設定します。
- ビット配列を繰り返します。
- ビットが設定されている場合は、その位置を出力します。
または言い換えると (N <10 の場合、3 つの数字 4、6、2 を並べ替える場合) 0
空の 10 ビット配列 (通常は 1 つの整数) から始めます
0000000000
4 を読み取り、配列内のビットを設定します..
0000100000
6 を読み取り、配列内のビットを設定します
0000101000
2 を読み取り、配列内のビットを設定します
0010101000
配列を反復し、ビットが 1 に設定されているすべての位置を出力します。
2, 4, 6
set() から始めます:
5 の右シフトは 32 で除算することと同じです。これは、ビットがどの int にあるかを見つけるために行われます。
MASK は 0x1f または 31 です。アドレスと AND を取ると、int 内のビット インデックスが得られます。アドレスを 32 で割った余りと同じです。
ビット インデックス ("1<<(i &MASK)") だけ左に 1 シフトすると、指定された位置セットに 1 ビットだけを持つ整数になります。
ORing によってビットが設定されます。
「int sh =i>>SHIFT;」という行は無駄な行です。なぜなら、彼らはその下で sh を再び使用せず、代わりに "i>>SHIFT"
clr() は基本的に set と同じですが、ビットを設定するために 1<<(i &MASK) と OR する代わりに、逆数と AND してビットをクリアします。 test() 1<<(i &MASK) の AND でビットをテストします。
ビットソートは、整数ごとに最大 1 つしかカウントしないため、リストから重複も削除します。ビットの代わりに整数を使用してそれぞれを 1 以上カウントするソートは、基数ソートと呼ばれます。