Bạn có chắc chắn muốn xóa bài viết này không ?
Bạn có chắc chắn muốn xóa bình luận này không ?
Bit twiddling (part 2)
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)







