Fast bit counter

Hàm đếm bit - Fast bit counter

Mở đầu

Bạn đang chăm chú ngắm nghía 1 đoạn code, bỗng nhiên bạn gặp một hàm trông có vẻ rất nguy hiểm như sau:

int fbc(unsigned int data)
{
        data = (data & 0x55555555) + ((data >> 1) & 0x55555555);
        data = (data & 0x33333333) + ((data >> 2) & 0x33333333);
        data = (data & 0x0F0F0F0F) + ((data >> 4) & 0x0F0F0F0F);
        data = (data & 0x00FF00FF) + ((data >> 8) & 0x00FF00FF);
        data = (data & 0x0000FFFF) + ((data >> 16) & 0x0000FFFF);
        return data;
}

Một đoạn hàm rất bí ẩn với một loạt các phép toán logic >>, &, +.

Bạn có biết đoạn hàm này có nhiệm vụ gì không? Nó chính là “Fast bit count”, được sử dụng để đếm nhanh số bit 1 có trong 1 số 32bit (unsigned int trong C).

Bạn có thấy hoài nghi không? Thử biên dịch và xem hàm này nó làm thế nào mà hay vậy nhé!

#include <iostream>

using namespace std;

int fbc(unsigned int data)
{
        data = (data & 0x55555555) + ((data >> 1) & 0x55555555);
        data = (data & 0x33333333) + ((data >> 2) & 0x33333333);
        data = (data & 0x0F0F0F0F) + ((data >> 4) & 0x0F0F0F0F);
        data = (data & 0x00FF00FF) + ((data >> 8) & 0x00FF00FF);
        data = (data & 0x0000FFFF) + ((data >> 16) & 0x0000FFFF);
        return data;
}

int main()
{
        int ans;
        int input;
        cout<<"Input: ";
        cin>>input;
        ans = fbc(input);
        cout<<"\nAnswer: "<<ans;
        return 0;
}
Input: 7
Answer: 3

Kết quả rất chuẩn. Vậy bạn có biết hàm fbc kia làm thế nào không?

Cơ chế hoạt động

Để có thể hiểu tại sao hàm này trả về số bit 1, ta hãy thử xem các con số 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF và 0x0000FFFF có ý nghĩa gì.

Bằng cách ấn máy tính, đổi từ hệ 16 sang hệ 2, ta có giá trị nhị phân của các số trên như bảng dưới đây:

0x55555555      01010101010101010101010101010101
0x33333333      00110011001100110011001100110011
0x0F0F0F0F      00001111000011110000111100001111
0x00FF00FF      00000000111111110000000011111111
0x0000FFFF      00000000000000001111111111111111

Ta nhận thấy các con số trên không hoàn toàn bí ẩn mà nó hoàn toàn có quy luật. Từ trên xuống dưới, các bit 1 xen kẽ nhau theo chu kỳ 1, 2, 4, 8, 16.

Ta thử quay lại hàm fbc và xem cách con số này được sử dụng. Vì số 0x55555555 lên đến 32 bit nên rất khó theo dõi (nhiều 0 với 1 quá), ta sẽ thử xét trường hợp số 8 bit với bit pattern không đổi (tức là số 0xFF). Dòng 1 của hàm fbc sẽ như dưới đây:

data = (data & 0x55) + ((data >> 1) & 0x55);

Giả sử data = 10110011b, ta sẽ có:

data = 10110011 & 01010101 + ((10110011 >> 1 & 01010101)

Lần tính 1

data & 01010101 00 01 00 01

(data >> 1)& 01010101 01 01 00 01

01 10 00 10

Do kết quả tối đa của phép + này là 2, khả năng kết quả phép cộng “tràn sang” vùng bit bên cạnh là không có. Sau lần tính thứ nhất, ta có kết quả của số bit 1 của cặp đôi bit cạnh nhau.

Tất nhiên ở đây ta vẫn chua có kết quả số bit. Tuy nhiên ta sẽ áp dụng phương pháp tương tự cho cụm 4 bit.

Nhìn dòng thứ 2 đoạn code bạn sẽ thấy: …1100110011b: 2 bit đan xen! Phép dịch bit bây giờ là >> 2.

Lần tính 2

data & 00110011 00 10 00 10

(data >> 2)& 00110011 00 01 00 00

00 11 00 10

Như vậy ta có 4 bit đằng sau có tổng số bit là 2, 4 bit đâu có tổng số bit là 11 (3 trong hệ thập phân)!!!

Áp dụng cách tính tương tự, ta có kết quả như ở dưới.

Lần tính 3

data & 00001111 00 00 00 10

(data >> 4)& 00001111 00 00 00 11

00 00 01 01

Kết quả là 5, chính là số bit của data ban đầu!!

Để tính số bit của 1 số 32 bit, ta chỉ việc tăng số bit của các “magic number” lên. Đấy là lý do ta có các số 0x55555555, 0x33333333, …

Đến đây chắc hẳn bạn đã hiểu tại sao hàm fbc trả về số bit 1.

Tổng kết

Đoạn code rất nhẹ nhàng và tinh tế đúng không nào? :) Và nó cũng rất hiệu quả nữa.

Tham khảo

Từ Kipalog.com