Opérations sur les bits Cracking the Coding Interview

Question

J'ai essayé de résoudre le premier problème de CTCI, qui implique la manipulation de bits, et je n'arrive pas à comprendre comment l'auteur a fait le masque avec précision dans sa solution finale. Quelqu'un pourrait-il expliquer les calculs de "int left", "int right", et "int mask"? Ce serait formidable de voir ce que ces lignes calculent spécifiquement pour l'exemple qu'il a fourni.

La question est: Vous avez deux nombres de 32 bits, N et M, et deux positions de bits, i et j. Ecrivez une méthode pour régler tous les bits entre i et j dans N égal à M (par exemple, M devient une sous-chaîne de N situé en i et commençant en j). EXEMPLE: entrée: N = 10000000000, M = 10101, i = 2, j = 6 sortie: N = 10001010100

public static int updateBits(int n, int m, int i, int j) { 
int max = ~0; /* All 1’s */ 

// 1’s through position j, then 0’s 
int left = max - ((1 << j) - 1); 

// 1’s after position i 
int right = ((1 << i) - 1); 

// 1’s, with 0s between i and j 
int mask = left | right; 

// Clear i through j, then put m in there 
return (n & mask) | (m << i); 
} 

Answer 1

expliquer les calculs pour "int gauche", "int droite", et "masque int"

// 1’s through position j, then 0’s 
int left = max - ((1 << j) - 1); 

• (1 << j) a juste le bit à la position j ensemble à 1
• ((1 << j) - 1) (soustrayant 1), on obtient tous les bits j ci-dessous (à droite) de la position j ensemble à 1
• max - ((1 << j) - 1) (soustrayant tout 1) donne le complément de bits de ce qui précède, i. e. tous les bits ci-dessus (à la gauche de) et y compris la position j fixé à 1, et les bits de j ci-dessous ensemble à 0

e. g.

j   1<<j   (1<<j)-1  ~0-((1<<j)-1) 
------------------------------------------------------- 
0  000000000001  000000000000  111111111111 
1  000000000010  000000000001  111111111110 
2  000000000100  000000000011  111111111100 
3  000000001000  000000000111  111111111000 
4  000000010000  000000001111  111111110000 
5  000000100000  000000011111  111111100000 
6  000001000000  000000111111  111111000000 
... 

// 1’s after position i 
int right = ((1 << i) - 1); 

• (1 << i) a juste le bit à la position i ensemble à 1
• ((1 << i) - 1) (soustrayant 1), on obtient tous les i bits de dessous (à droite) de la position i ensemble à 1

e. g.

i   1<<i   (1<<i)-1 
------------------------------------- 
0  000000000001  000000000000 
1  000000000010  000000000001 
2  000000000100  000000000011 
... 

// 1’s, with 0s between i and j 
int mask = left | right; 

i = 2, j = 6:

left  111111000000 
right  000000000011 
|   ------------ 
mask  111111000011 

// Clear i through j, then put m in there 
return (n & mask) | (m << i); 

• (n & mask), à la différence de commentaires, efface les bits i par j -1 seulement (voir mask ci-dessus)
• (m << i) décale la valeur à régler à la position de bit souhaitée
• (n & mask) | (m << i) ORs les bits de valeur décalée vers la masqué n

avec votre exemple:

Maintenant, bien que ces valeurs d'exemple donnent un résultat correct, nous pouvons voir que la mise en œuvre de updateBits() est actuall

y a tort, car la partie leftmask a besoin de 1 bits seulement à gauche de et pas, y compris la position j, puisque la position de bit j appartient à la sous-chaîne qui doit être masquée. L'erreur montre e. g. avec les valeurs n = 11111111111, m = 00000, i = 2, j = 6:

n  011111111111 
mask 111111000011 
&  ------------ 
n&mask 011111000011 
m<<i 000000000000 
|  ------------ 
     011111000011 

La valeur m a été mis dans des positions de bit i-j-1 seulement.

L'erreur peut être corrigée en modifiant

int left = max - ((1 << j) - 1); 

à

int left = max - ((1 << j+1) - 1);