Bit twiddling (part 2)

C

29

Hoàng Minh Trung viết ngày 18/09/2015

Vấn đề: bạn có một số nguyên X, giả sử X = 10. Biểu diễn binary của X sẽ là 1010. Vậy nếu câu hỏi là

Làm thế nào để đếm số lượng bit 1 trong biểu diễn cơ số 2 của một số nguyên.

Câu trả lời cho trường hợp X = 10 sẽ là 2, vì 1010 có 2 số 1.
Câu trả lời cho trường hợp X = 7 (111) sẽ là 3

Với một cách nghĩ đơn giản nhất, chúng ta sẽ đếm lần lượt bằng cách loop qua từng bit của X và tìm xem có bao nhiêu bit 1:

int count_bit(uint_64 input) { //giả sử đầu vào là một số nguyên 64 bit
    uint count = 0;
    while (value > 0) {         //lần lượt shift giá trị hiện tại về bên phải từng bit một
        if ((value & 1) == 1) { //đếm xem bit đầu tiên bên phải của giá trị này có phải là 1 không
            count ++ ;          //nếu là 1 thì cộng giá trị trả về thêm 1
        }
        value >>= 1;            //shift về bên phải 1 bit
    }
    return count;
}

Cách sử dụng ở trên theo tôi là đã khá sáng sủa rồi, tuy nhiên chúng ta sẽ nghĩ xem có cách nào tốt hơn không?
Nghĩ một lúc rồi, tôi chịu :D, bạn có nghĩ ra không?
Sau khi nghĩ một lúc không ra tôi google :D, google một lúc tôi tìm được một thuật toán tên là hamming weight, thuật toán có lời giải như sau:

#include <stdio.h>
#include <stdint.h>

const uint64_t m1  = 0x5555555555555555; //binary: 0101...
const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t hff = 0xffffffffffffffff; //binary: all ones
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...


int popcount_1(uint64_t x) {
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits
    x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits
    return x;
}

int main(int argc, char** args) {
  printf("%d", popcount_1(3));
}

Về concept thì thuật toán trên sẽ chia thành từng khoảng: 2 bit một, 4 bit một, ... 32 bit một.
Ví dụ với với đầu vào là 3 chúng ta sẽ có

[00] [11] //khoảng 2 bit một
[0011]  // khoảng 4 bit một

Sau đó chúng ta sẽ đếm lần lượt số bit 1 trong từng khoảng. Do 3 chỉ có 2 bit nên để ví dụ mình sẽ sẽ chỉ làm đến bước m2, không cần làm hết đến 64 bit .

 x = (x & m1 ) + ((x >>  1) & m1 ); // -->  0011 & 0101 + 0001 & 0101 = 0010 (0010 = tức là có 2 số 1 ở trong 2 bit cuối, và 0 bit 1 ở 2 bit đầu)
 x = (x & m2 ) + ((x >>  2) & m2 ); // -->  0010 & 0011 + 0000 && 0011 = 0010 (tức là có 2 số 1 ở trong 4 bit)

như vậy kết quả chúng ta sẽ có 2 bit 1 trong số 3.

Ứng dụng của hamming weight là để tính khoảng cách Hamming (Hamming distance) giữa 2 chuỗi A, B một cách khá nhanh bằng

hammingDistance(String A, String B) = hammingWeight(A) XOR hammingWeight(B)