Bit Utilizzo maschera nel programma di programmazione da Perle

Question

Ho iniziato a leggere "Programming Pearls" oggi e mentre facevo esercizio mi sono imbattuto in questa domanda "Come implementeresti il ​​tuo vettore bit?". Quando ho guardato la soluzione era così:

#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)); 

Dove mi sto confuso in questa affermazione

1 << (i & MASK) 

Qualcuno potrebbe spiegare che cosa sta succedendo qui?

Answer 1

noti che MASK è impostato in modo che esso ha il più basso SHIFT bit impostati, dove SHIFT è esattamente il logaritmo a base 2 della BITSPERWORD.

Pertanto (i & MASK) selezionerà i bassi 5 bit di i, che è lo stesso che il resto dopo la divisione del 32 (basta considerare come prendendo i bassi due cifre di un numero decimale si dà il resto dopo la divisione per 100, per esempio). Che dà il numero del bit all'interno una parola che ci interessa.

1 << (i & MASK)) (che è, tra l'altro, un espressione, non un dichiarazione) ora crea un valore esattamente dove il bit ci interessa è impostato. L'unione di questo valore nella parola di memoria con |= imposterà il bit desiderato del vettore di bit.

Answer 2

0x20 è 32, quindi i & 0x1F assume i modulo 32, in modo da non spostarsi mai di 32 bit. Questa è una salvaguardia perché spostare qualsiasi cosa che non sia strettamente inferiore alla dimensione del tipo è un comportamento indefinito.