[Dev] Hàm đếm bit nhanh – 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:

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é!

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:

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:

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

  1. Có thể 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…).
  2. Do vậy kết quả của data & 0x55 sẽ cho ra các bit 1 ở vị trí chẵn.
  3. 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.
  4. 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

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

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

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

  1. Bithacks
  2. Assembly book
  3. Programming groundup

Từ Kipalog.com

Leave a Reply

Be the First to Comment!

Notify of
avatar
wpDiscuz