Phương pháp này đếm số lượng 1 trong biểu diễn nhị phân như thế nào?

Question

thể trùng lặp:
n & (n-1) what does this expression do?

Hãy xem xét các thuật toán sau đây:

int count(int num) 
{ 
    int ones = 0; 
    while(num) 
    { 
    ++ones; 
    num &= num - 1; 
    } 

    return ones; 
} 

tầm quan trọng của num & (num-1) là gì? Làm thế nào nó hoạt động?

Answer 1

num &= num - 1; 

xóa bit ít quan trọng nhất được đặt bằng num.

Thuật toán này đếm số bit được đặt bằng cách xóa chúng và tăng bộ đếm cho đến khi hết.

Để hiểu lý do tại sao nó xóa bit ít quan trọng nhất, bạn cần phải suy nghĩ về những gì decrementing không cho các bit và tất nhiên hiểu những gì các hoạt động & nào.

Trừ trong tác phẩm nhị phân giống như quy trình chúng tôi được dạy bằng số thập phân dưới dạng trẻ em. Bạn làm việc từ phải (ít quan trọng nhất) sang trái, chỉ cần trừ các chữ số riêng lẻ khi có thể và "mượn" từ chữ số tiếp theo khi cần.

Khi trừ 1 từ số nhị phân kết thúc bằng một số 0, thì "mượn" và trừ tất cả các số 0 ở vị trí thấp hơn số phải từ 1 đến 1 và rẽ phải 1 đến 0 (vì nó được mượn).

Sau đó, áp dụng các nhà điều hành & lá tất cả các chữ số nhỏ hơn số không bởi vì họ đang không ở num, và thiết lập các bit quan trọng nhất của num bằng không bởi vì nó là zero trong num-1.

Cả hai thao tác này đều không thay đổi chữ số có nghĩa.

Dưới đây là danh sách tốt gồm bit twiddling hacks bao gồm danh sách này, là do Brian Kernighan.

Answer 2

Dưới đây là câu trả lời chi tiết hơn (nhưng không được viết tốt!).

Có hai trường hợp: bit ít quan trọng nhất được đặt, sau đó "num-1" sẽ tắt nó. Hoặc nó không được thiết lập, sau đó num-1 biến tất cả các số 0 theo sau thành 1 và ít nhất là 1 đến 0, phần còn lại của các bit không bị thay đổi. Khi bạn "và", tất cả các bit không thay đổi đều giống nhau, số ít nhất có ý nghĩa 1 được tạo thành với 0 biến thành 0 và các bit còn lại là số 0. Điều này được minh họa tại đây:

num    =  1000110111[1]0000 
num - 1   =  1000110111[0]1111 
num & (num - 1) =  1000110111[0]0000 

Tôi sẽ chỉ ra rằng thường có một hoạt động lắp ráp để đếm số lượng đơn vị trong một chu kỳ. Các hoạt động được gọi là "popcount" và ví dụ trong GCC, nó có thể được truy cập bằng cách sử dụng "__builtin_popcount", xem this link để biết chi tiết.

Answer 3

Thuật toán hoạt động như máy bơm, di chuyển bit hiệu quả sang phải trong biến "num".Dòng

num &= num - 1; 

là nơi công việc được thực hiện, có nhiệm vụ và hoạt động Boolean AND diễn ra cùng một lúc. Đó là tất cả về số học bit.

Pom