Trong các hệ thống phân quyền hoặc cấu hình cờ trạng thái, làm thế nào để đếm tổng số lượng bit 1 đang được bật (Population Count hay Hamming Weight) trong một số nguyên 32-bit một cách tối ưu hiệu năng mà không dùng vòng lặp duyệt qua từng bit?

Question

Accepted Answer

Để đếm số lượng bit 1 trong một số nguyên mà không cần dùng vòng lặp 32 lần (vốn gây tốn kém hiệu năng trong các vòng lặp lớn), kỹ thuật chuẩn Enterprise sử dụng thuật toán Hamming Weight theo phương pháp chia để trị (Divide and Conquer), thường được gọi là thuật toán SWAR (Simultaneous Within A Register).
Bản chất cơ chế hoạt động:
Thuật toán nhóm các bit lại với nhau và tính tổng từng phần theo cặp, sau đó theo nhóm 4, nhóm 8, nhóm 16 và nhóm 32 bằng các mặt nạ (masks) định sẵn:

Đếm tổng số bit trong các khối 2-bit.
Đếm tổng số bit trong các khối 4-bit.
Cộng dồn các khối 8-bit, 16-bit và 32-bit.

Ví dụ mã nguồn minh họa:
#include <stdio.h>

int countSetBits(unsigned int n) {
    n = n - ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n + (n >> 4)) & 0x0F0F0F0F;
    n = n + (n >> 8);
    n = n + (n >> 16);
    return n & 0x0000003F;
}

int main() {
    unsigned int num = 29; // Biểu diễn nhị phân: 11101 (có 4 bit 1)
    int count = countSetBits(num);
    printf("Tong so bit 1: %d
", count);
    return 0;
}
Kinh nghiệm thực chiến:

Phương pháp này chạy với độ phức tạp O(1) thuần túy vì không có vòng lặp.
Trong các kiến trúc CPU hiện đại, các lập trình viên thường tận dụng các tập lệnh phần cứng chuyên dụng như lệnh POPCNT (x86 SSE4.2) thông qua các compiler intrinsics (__builtin_popcount trong GCC/Clang) để đạt hiệu năng phần cứng tối đa.

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ủ đề