Đếm số bit: Dòng này hoạt động như thế nào? n = n &(n-1);

Question

Tôi cần giải thích cách hoạt động của dòng cụ thể này.
Tôi biết rằng chức năng này đếm số bit của 1, nhưng cách chính xác đường này xóa hết 1 bit bên phải?

int f(int n) { 
    int c; 
    for (c = 0; n != 0; ++c) 
     n = n & (n - 1); 
    return c; 
} 

Có thể một số giải thích cho tôi một thời gian ngắn hoặc đưa ra một số "bằng chứng"?

Answer 1

Bất kỳ số nguyên không dấu 'n' nào sẽ có các chữ số k sau cùng: Một theo sau là (k-1) zeroes: 100 ... 0 Lưu ý rằng k có thể là 1 trong trường hợp không có số 0.

(n - 1) sẽ kết thúc ở định dạng này: Zero tiếp theo (k-1) 1 của: 011 ... 1

n & (n-1) do đó sẽ kết thúc trong zero 'k': 100 ... 0 & 011 ... 1 = 000 ... 0

Do đó n & (n - 1) sẽ loại bỏ phần ngoài cùng bên phải '1'. Mỗi lần lặp lại điều này về cơ bản sẽ loại bỏ chữ số '1' bên phải và do đó bạn có thể đếm số của 1.

Answer 2

Tôi đã đánh lừa thao tác bit và đã xem xét điều này. Nó có thể không hữu ích cho các poster ban đầu bây giờ (3 năm sau), nhưng tôi sẽ trả lời anyway để cải thiện chất lượng cho người xem khác.

Có nghĩa là gì đối với n & (n-1) bằng 0?

Chúng tôi phải đảm bảo rằng chúng tôi biết rằng vì đó là cách duy nhất để ngắt vòng lặp (n != 0). Giả sử n=8. Biểu diễn bit cho điều đó sẽ là 00001000. Biểu diễn bit cho n-1 (hoặc 7) sẽ là 00000111. Toán tử & trả về các bit được đặt trong cả hai đối số. Vì 00001000 và 00000111 không có bất kỳ bit tương tự nào được đặt, kết quả sẽ là 00000000 (hoặc không). Bạn có thể đã bắt gặp rằng số 8 không được chọn ngẫu nhiên. Đó là một ví dụ trong đó n là sức mạnh của 2. Tất cả các quyền hạn của 2 (2,4,8,16, vv) sẽ có kết quả tương tự.

Điều gì sẽ xảy ra khi bạn chuyển một thứ không phải là số mũ 2? Ví dụ, khi n=6, biểu diễn bit là 00000110 và n-1=5 hoặc 00000101. & được áp dụng cho 2 đối số này và chúng chỉ có một bit chung là 4. Bây giờ, n=4 không bằng 0 để chúng tôi tăng c và thử quá trình tương tự với n=4. Như chúng ta đã thấy ở trên, 4 là số mũ của 2 vì vậy nó sẽ phá vỡ vòng lặp trong lần so sánh tiếp theo. Người ta cắt đứt các bit ngoài cùng bên phải cho đến khi n bằng một sức mạnh của 2.

c là gì?

Nó chỉ được incrementing bởi một trong mỗi vòng lặp và bắt đầu từ 0. c là số bit cắt đứt trước số bằng một sức mạnh của 2.