manipolazione bit: azzeramento intervallo di bit

Question

Mi sto preparando per un'intervista utilizzando 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, comprendo cosa (1 << i) fa naturalmente, ma ciò non sono sicuro di è come sottraendo 1 da questo valore influenza i bit (cioè, (1 << i) - 1)).

Fondamentalmente ho la stessa confusione con la seconda funzione. A quali effetti, in particolare sui bit, è necessario sottrarre 1 da ((1 << (i+1))? Dalla mia comprensione, ((1 << (i+1)) si traduce in 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 qualche motivo hanno il testo di riferimento, è a pagina 91 della quinta edizione.

Answer 1

supponiamo i= 5

(1 << i) dare 0100000 l'1 è posto nella posizione 6 ° bit

così ora se togliamo 1 da esso, allora otteniamo 0011111 ==> solo il 5 primo bit sono impostati 1 e gli altri sono impostati per 0 ed è così che otteniamo la nostra maschera

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

Answer 2

Funzione First:

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, lo stesso vale. Se i=3, quindi ((i << (i+1)) - 1) ci dà 01111. La tilde inverte i bit, quindi abbiamo 10000. È importante farlo in questo modo invece di spostare solo i bit i, perché potrebbero esserci un numero qualsiasi di bit significativi prima della nostra maschera (quindi 10000 potrebbe essere lungo 8 bit e assomigliare a 11110000. Questo è ciò che ci viene dalla tilde, solo per essere chiaro).Quindi, il numero è AND con la maschera per il risultato finale

Answer 3

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 per i perché tutte le posizioni di bit di cui sopra e comprendente indice i saranno 0 e ogni soffietto saranno 1.

Per la seconda domanda:

consente Ancora una volta dicono 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 questo maschere cancella i bit fino a indice i

Answer 4

// Per cancellare tutti i bit dal bit più significativo attraverso i (compreso), che 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<<i)-1 will clear the bits from msb to i 

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

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

stesso esempio di i = 3 ti dà

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