manipolazione di bit: cancellazione di intervalli di bit

Mi sto preparando per un’intervista usando il testo, “Cracking the Coding Interview” di Gayle Laakman McDowell. Nella sezione che riguarda la manipolazione dei bit, sono disponibili due funzioni, ma non capisco come funziona.

// To clear all bits from the most significant bit through i (inclusive), we do: int clearMSBthroughI(int num, int i) { int mask = (1 << i) - 1; return num & mask; } // To clear all bits from i through 0 (inclusive), we do: int clearBitsIthrough0(int num, int i) { int mask = ~(((1 << (i+1)) - 1); return num & mask; } 

Nella prima funzione, capisco cosa (1 << i) fa, naturalmente, ma ciò di cui non sono sicuro è come sottrarre 1 da questo valore influenzi i bit (cioè, (1 << i) - 1) ).

Fondamentalmente ho la stessa confusione con la seconda funzione. A quali effetti, in particolare sui bit, viene sottratto 1 da ((1 << (i+1)) ? Dalla mia comprensione, ((1 << (i+1)) risulta un singolo bit “on”, spostato a sinistra i + 1 volte – cosa significa sottrarre questo di 1?

Grazie e spero sia stato chiaro! Per favore fatemi sapere se ci sono altre domande.

Per coloro che per caso hanno il testo a cui sto riferendo, è a pagina 91 della 5a edizione.

assumiamo i= 5

(1 << i) ti dà 0100000 l'1 è posizionato nella sesta posizione di bit

quindi ora se sottostrogliamo 1 da esso, allora otteniamo 0011111 ==> solo i primi 5 bit sono impostati su 1 e gli altri sono impostati su 0 ed è così che otteniamo la nostra maschera

Conclusione: per un dare i (1 << i) -1 ti darà una maschera con i primi bit impostati su 1 e altri su 0

Per la prima domanda:

diciamo i = 5

 (1 << i ) = 0010 0000 = 32 in base 10 (1 << i ) -1 = 0001 1111 = 31 

Quindi un & con questa maschera cancella il bit più significativo verso il basso in quanto tutte le posizioni di bit sopra e incluso l'indice i saranno 0 e qualsiasi muggito sarà 1.

Per la seconda domanda:

Di nuovo diciamo i = 5

  (1 << (i + 1)) = 0100 0000 = 64 in base 10 (1 << (i + 1)) - 1 = 0011 1111 = 63 ~((1 << (i + 1)) - 1) = 1100 0000 = 192 

Quindi un & con queste maschere cancella i bit fino all'indice i

Prima funzione:

Prendiamo i=3 per esempio. (1 << i) produrrebbe 1000 in binario. Sottraendo 1 da quello si ottiene 0111 in binario (che è il numero di 1). ANDando che con il numero si cancellano tutti gli ultimi ma i bit, proprio come dice la descrizione della funzione.

Seconda funzione:

Per la seconda funzione vale lo stesso. Se i=3 , allora ((i << (i+1)) - 1) ci dà 01111 . La tilde inverte i bit, quindi abbiamo 10000 . È importante farlo in questo modo invece di spostare i bit a sinistra, perché ci potrebbe essere un numero qualsiasi di bit significativi prima della nostra maschera (quindi 10000 potrebbe essere lungo 8 bit e apparire come 11110000 Questo è ciò che ci viene dalla tilde, solo per essere chiaro). Quindi, il numero è ANDed con la maschera per il risultato finale

// Per cancellare tutti i bit dal bit più significativo attraverso i (incluso), facciamo:

 int clearMSBthroughI(int num, int i) { int mask = (1 << i) - 1; return num & mask; } Take the example of i = 3 1<<3 gives you 0x00001000 (1<<3)-1 gives you 0x00000111 num & (1< 

// Per cancellare tutti i bit da I a 0 (inclusi), facciamo:

 int clearBitsIthrough0(int num, int i) { int mask = ~(((1 << (i+1)) - 1); return num & mask; } 

lo stesso esempio di i = 3

 1 <<(3+1) =0x00010000 1 <<(3+1)-1 = 0x00001111 mask =~(1<<(3+1)-1) = 0x11110000 num & mask will cleaR the bits from 0 throuh i