3

私は本のプログラミングパールで質問を勉強しています.彼らはこの関数をビットベクトルにビットを設定することを勧めました. 私はそれが何をするのか少し混乱しています。

#define BITSPERWORD 32
#define MASK 0x1F
#define SHIFT 5
#define N 1000000

int a[1 + N/BITSPERWORD];

void set(int i){
   a[i >> SHIFT] |= (1 << (i & MASK)); 
}

これが、このコードの私の (おそらく間違った) 解釈です。i = 64 の場合、

1) 最初に、それを受け取りi、SHIFT (5) ビットだけ右にシフトします。これは、除算 (私が最初に考えたように乗算ではありません) と同等iです2^5。したがって、 の場合、 a のインデックスiは642 (64 / 2^5)

2) a[2] |= (1 << (64 & MASK))
64 & 1 = 1000000 & 01 = 1000001.
では、1 は何ビット左にシフトされますか????

4

1 に答える 1

3
  1. 少し設定するより良い方法があるように感じますが、この方法がどのように機能するかのようです。それは基本的に 32 で除算するビットのインデックスを見つけることithです。これは、1 ワードあたりのビット数であるためです。
  2. ここで使用される演算子は|、ビットをトグルせずにビットを 1 に設定する機能であるためです。
  3. 0x1F は実際には 31 であり、 i で論理積すると、残りが得られます (なぜ使用しなかったのかわかりません%)
  4. そして最後に、シフトは 1 を適切な場所に移動し、ベクトル内の正しいスロットに移動します。

このコードを使用する予定がある場合

  1. 定義せずに、より明白な方法を使用してそれを非常に明確に書くことができますが、それが速度に違いをもたらすとは思えません。
  2. また、おそらく使用する必要がありますstd::bitset
  3. マスクを使用して残りを取得することは、すべての数字で必ずしも機能するとは限らないため、特にイライラしました.31はすべて1であるため、たまたま機能します
于 2013-07-20T17:29:42.997 に答える