Trong các thuật toán tối ưu hóa tìm kiếm đường đi hoặc xử lý đồ thị, làm thế nào để đếm tổng số lượng bit 1 (Population Count / Hamming Weight) trong một số nguyên 32-bit một cách hiệu quả nhất?

Question

Accepted Answer

Bản chất vấn đề
Đếm số lượng bit 1 trong một số nguyên (thường được gọi là hàm popcount hoặc trọng số Hamming) là một bài toán kinh điển trong lập trình hệ thống, mã hóa sửa lỗi (Error-correcting codes) và tối ưu hóa truy vấn đồ thị.
Giải pháp tối ưu bằng Brian Kernighan Algorithm
Thay vì duyệt qua từng bit từ phải sang trái bằng vòng lặp 32 lần, thuật toán Brian Kernighan cho phép loại bỏ từng bit 1 một cách trực tiếp trong mỗi vòng lặp. Số lần lặp sẽ đúng bằng số lượng bit 1 thực tế có trong số nguyên đó.
int CountSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1); // Xóa bit 1 thấp nhất
        count++;
    }
    return count;
}
Phân tích cơ chế hoạt động
Biểu thức n & (n - 1) luôn luôn tắt (clear) bit 1 thấp nhất của số n. 
Ví dụ: Nếu $n = 12$ (nhị phân 1100):

Lần lặp 1: n = 1100, n - 1 = 1011. 1100 & 1011 = 1000 (số 8). count = 1.
Lần lặp 2: n = 1000, n - 1 = 0111. 1000 & 0111 = 0000 (số 0). count = 2.
Kết thúc vòng lặp, tổng số bit 1 là 2.

Kinh nghiệm thực chiến Enterprise
Thuật toán này cực kỳ hiệu quả khi số lượng bit 1 thưa thớt (sparse). Đối với các kiến trúc CPU hiện đại, các lập trình viên cũng có thể tận dụng các tập lệnh phần cứng chuyên dụng như POPCNT (có sẵn trên x86_64 và ARM) thông qua các hàmIntrinsic của ngôn ngữ lập trình để đạt hiệu suất tối đa.

Trong các thuật toán tối ưu hóa tìm kiếm đường đi hoặc xử lý đồ thị, làm thế nào để đếm tổng số lượng bit 1 (Population Count / Hamming Weight) trong một số nguyên 32-bit một cách hiệu quả nhất?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi bit manipulation liên quan cùng chủ đề