manipulacja bitami: usuwanie zakresu bitów

Question

Przygotowuję się do wywiadu z wykorzystaniem tekstu "Cracking the Coding Interview" autorstwa Gayle Laakman McDowell. W dziale dotyczącym manipulacji bitami są dwie funkcje, ale nie do końca rozumiem, jak to działa.

// 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; 
} 

W pierwszej funkcji, rozumiem co (1 << i) robi oczywiście, ale co nie jestem pewny jest jak odjęcie 1 od tej wartości wpływa bitów (tj (1 << i) - 1)).

W zasadzie mam takie samo zamieszanie z drugą funkcją. Do jakich efektów, szczególnie na bitach, odejmuje się 1 od ((1 << (i+1))? Z mojego rozumowania wynika, że ​​((1 << (i+1)) powoduje powstanie pojedynczego bitu "na", przesuniętego w lewo i + 1 razy - co odejmuje od 1?

Dzięki i mam nadzieję, że to było jasne! Proszę dać mi znać, jeśli są jakieś inne pytania.

Dla tych, którzy przypadkiem mają tekst, do którego się odwołuję, jest on na stronie 91 w 5. Edycji.

Answer 1

załóżmy i= 5

(1 << i) daje 0100000 1 umieszcza się w 6. pozycji bitowej

więc teraz, jeśli odjąć 1 od niego, wtedy otrzymujemy 0011111 ==> tylko 5 pierwszy bit są ustawiony 1 i inni są ustawione na 0 iw ten sposób otrzymujemy nasz Maska

Wniosek: dla dając i(1 << i) -1 daje maskę z i pierwsze bity ustawione na 1 i inni ustawiony 0

Answer 2

pierwsza funkcja:

Weźmy i=3 na przykład. (1 << i) dałoby 1000 w systemie binarnym. Odjęcie 1 od tego daje 0111 w postaci binarnej (która jest liczbą 1). ORAZ z tym numerem usunie wszystkie, oprócz ostatnich i bitów, tak jak opisuje opis funkcji.

Druga funkcja:

Dla drugiej funkcji, to samo dotyczy. Jeśli i=3, to ((i << (i+1)) - 1) daje nam 01111. Tilda odwraca bity, więc mamy 10000. Ważne jest, aby zrobić to w ten sposób, zamiast przesuwać tylko bitów i, ponieważ przed naszą maską może znajdować się dowolna liczba znaczących bitów (więc 10000 może mieć długość 8 bitów i wyglądać jak 11110000. Tak robi nas tylda, być jasne).Potem liczba ta AND z maską dla końcowego wyniku

Answer 3

Na pierwsze pytanie:

Powiedzmy i = 5

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

Więc & z tej maski czyści najbardziej znaczący bit w dół do I ponieważ wszystkie pozycje bitów powyżej i zawierające indeks i będą wynosić 0, a każdy z nich będzie wynosił 1.

Drugie pytanie:

Ponownie powiedzmy 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 

Więc & z tych masek czyści bity do indeksu i

Answer 4

// Aby usunąć wszystkie bity od najbardziej znaczącego bitu przez I (włącznie), robimy:

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 

// Aby usunąć wszystkie bity od I do 0 (włącznie), robimy:

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

samo przykładem i = 3 daje

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