7

今日から「ProgrammingPearls」を読み始めましたが、その演習をしているときに、「独自のビットベクトルをどのように実装しますか？」という質問に出くわしました。私が解決策を見たとき、それは次のようでした：

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

int a[1 + N/BITSPERWORD]; 

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

私が混乱しているのはこの声明です

 1 << (i & MASK)

誰かがここで何が起こっているのか説明してもらえますか？

4

2 に答える 2

4

MASKは、最下位SHIFTビットが設定されるように設定されていることに注意してください。ここで、SHIFTは正確に2を底とする対数ですBITSPERWORD。

したがって(i & MASK)、の下位5ビットを選択しますi。これは、32で除算した後の余りを取得するのと同じです（たとえば、10進数の下位2桁を取得すると、100で除算した後の余りが得られることを考慮してください）。これにより、関心のある単語内のビット数がわかります。

1 << (i & MASK))（ちなみに、ステートメントではなく式です）は、関心のあるビットが正確に設定されている値を作成するようになりました。この値をメモリワードにマージすると、ビットベクトルの目的のビットが設定されます。|=

于 2011-08-28T03:03:04.333 に答える
2

0x20は32であるため、モジュロ32i & 0x1Fをi使用するため、32ビットだけシフトすることはありません。型のサイズより厳密に小さくないものによるシフトは未定義の動作であるため、これは安全策です。

于 2011-08-28T03:06:59.293 に答える