thao tác bit: phạm vi thanh toán bù trừ của các bit

Question

Tôi đang chuẩn bị cho một cuộc phỏng vấn bằng văn bản, "Cracking the Coding Interview" của Gayle Laakman McDowell. Trên phần bao gồm thao tác bit, có hai chức năng được cung cấp, nhưng tôi không hoàn toàn hiểu cách nó hoạt động.

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

Trong chức năng đầu tiên, tôi hiểu những gì (1 << i) làm tất nhiên, nhưng những gì tôi không chắc chắn của là cách trừ đi 1 từ giá trị này ảnh hưởng đến các bit (ví dụ: (1 << i) - 1)).

Tôi về cơ bản có cùng sự nhầm lẫn với hàm thứ hai. Đối với những hiệu ứng nào, cụ thể trên các bit, trừ trừ 1 từ ((1 << (i+1)) có? Từ sự hiểu biết của tôi, ((1 << (i+1)) kết quả trong một bit "trên" duy nhất, được dịch chuyển sang bên trái i + 1 lần - điều nào trừ đi điều này bằng 1 làm?

Cảm ơn và tôi hy vọng điều này đã rõ ràng! Vui lòng cho tôi biết nếu có bất kỳ câu hỏi nào khác.

Đối với những người có cơ hội có văn bản tôi đang tham chiếu, thì đó là trang 91 trong ấn bản thứ năm.

Answer 1

hãy giả sử i= 5

(1 << i) cung cấp cho bạn 0100000 1 được đặt ở vị trí bit thứ 6

vì vậy bây giờ nếu chúng ta trừ 1 từ nó, sau đó chúng tôi nhận 0011111 ==> chỉ bit đầu tiên 5 là thiết lập để 1 và những người khác được thiết lập để 0 và đó là cách chúng tôi có được mặt nạ của chúng tôi

Kết luận: một cho i các (1 << i) -1 sẽ cung cấp cho bạn một chiếc mặt nạ với i bit đầu tiên thiết lập để 1 và những người khác thiết lập để 0

Answer 2

Chức năng đầu tiên:

Chúng ta hãy i=3 ví dụ. (1 << i) sẽ mang lại 1000 trong nhị phân. Trừ 1 từ đó cung cấp cho bạn 0111 trong nhị phân (tức là số của 1). ANDing rằng với số sẽ xóa tất cả nhưng cuối cùng i bit, giống như mô tả chức năng nói.

Chức năng thứ hai:

Đối với chức năng thứ hai, cùng áp dụng. Nếu i=3, thì ((i << (i+1)) - 1) cung cấp cho chúng tôi 01111. Dấu ngã đảo ngược các bit, vì vậy chúng tôi có 10000. Điều quan trọng là làm theo cách này thay vì chỉ chuyển đổi các bit còn lại i, vì có thể có bất kỳ số lượng bit đáng kể nào trước mặt nạ của chúng tôi (vì vậy 10000 có thể dài 8 bit và trông giống như 11110000. rõ ràng).Sau đó, con số này ANDed với mặt nạ cho kết quả cuối cùng

Answer 3

Đối với câu hỏi đầu tiên:

phép nói i = 5

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

Vì vậy, một & với mặt nạ này sẽ xóa các bit quan trọng nhất xuống i bởi vì tất cả các vị trí bit ở trên và bao gồm chỉ mục i sẽ là 0 và bất kỳ dưới đây sẽ là 1.

Đối với câu hỏi thứ hai:

Một lần nữa cho phép nói 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 

Vì vậy, một & với mặt nạ này sẽ xóa bit lên đến chỉ số i

Answer 4

// Để xóa tất cả các bit từ bit quan trọng nhất thông qua i (bao gồm), chúng tôi làm:

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 

// Để xóa tất cả các bit từ i qua 0 (bao gồm), chúng tôi làm:

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

cùng ví dụ về i = 3 mang đến cho bạn

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