Đếm bit

Mở đầu

Bạn đang say sưa hacking code và bắt gặp một hàm với những con số bí ẩn như ở dưới đây:

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;
}

Chắc hẳn bạn sẽ không khỏi hét lên: "what the fuck! Không hiểu gì hết" khi nhìn đoạn code này. Bạn hoàn toàn không hiểu mục đích của nó. Tên hàm không cho bạn một thông tin nào hữu ích. Những con số bí ẩn cùng phép toán >>, &, + làm bạn rối.

Nếu tôi nói với bạn fcb có nghĩa là "fast bit count" và hàm trên trả về số bit 1 của 1 số 32 bit (unsigned int trong C), tôi cá chắc chắn bạn sẽ không khỏi hoài nghi. Vậy chúng ta hãy thử biên dịch chương trình và test thử hàm này. Tôi viết chương trình như dưới đây để test hàm fbc.

#include <stdio.h>
#include <assert.h>

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;
        ans = fbc(5);
        assert(ans == 2);  // 5 = 101b
        ans = fbc(198123);
        assert(ans == 10); // 198123 = 110000010111101011b
        return 0;
}

Kết quả chạy:

$ gcc -o test test.c
$ ./test
$ echo $?
0

Chương trình chạy bình thường, cho kết quả bằng 0 chứng tỏ hàm fbc trả về giá trị như ta mong muốn.

Bạn sẽ thắc mắc: Tại sao hàm này lại có thể đếm được số bit 1? Chúng ta hãy cùng tìm hiểu cơ chế đếm của hàm này.

Cơ chế

Để 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)

"Dễ dàng" nhận thấy chuỗi bit của 0xFF có các bit 1 ở vị trí chẵn (0, 2, 4...) do vậy bằng cách & data với 0xFF, ta đã loại trừ các bit 1 ở vị trí lẻ (1,3,5...). Do vậy kết quả của data & 0x55 sẽ cho ra các bit 1 ở vị trí chẵn. Bằng cách dịch 1 bit của data, ta chuyển các bit từ vị trí lẻ sang vị trí chẵn, và lại & với 0xFF, do đó đại lượng sau dấu cộng sẽ có các bit 1 ở vị trí chẵn. Kết quả của phép cộng sẽ cho ra số lượng bit ở vị trí lẻ và vị trí chẵn

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

Hy vọng với giải thích trên, bạn đã hiểu ý nghĩa sâu sắc đằng sau hàm fbc. Bạn sẽ vẫn hét "What the fuck!!!" nhưng lần này cho sự tuyệt vời không những cho sự ngắn gọn, tinh tế của đoạn code.

Tham khảo

1. bithacks
2. assembly book
3. Programming groundup