Bit twiddling (part 2)
C
29
White

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)
Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Hoàng Minh Trung

23 bài viết.
61 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
19 1
Bài viết dịch từ http://arslan.io/tenusefultechniquesingo Sử dụng một GOPATH duy nhất Sử dụng đồng thời nhiều GOPATH sẽ không giúp cho hệ thống ...
Hoàng Minh Trung viết 2 năm trước
19 1
White
18 15
(Ảnh) Mục đích của bài viết là hướng dẫn cơ bản nhất cho những ai chưa biết về docker, môi trường thực hiện là mac OS. Chuẩn bị Cài đặt virtua...
Hoàng Minh Trung viết gần 3 năm trước
18 15
White
14 0
Bài viết dịch từ https://github.com/luciotato/golangnotes/blob/master/OOP.md Mục đích bài viết Học golang dễ dàng hơn với những kiến thức bạn đ...
Hoàng Minh Trung viết 2 năm trước
14 0
Bài viết liên quan
White
3 1
Chú ý: Bài viết này trình bày chủ yếu cho CentOS 64 bit, tuy nhiên ý tưởng có thể áp dụng cho các hệ điều hành khác. Cuối bài có ghi chú cho Ubunt...
Ngoc Dao viết hơn 2 năm trước
3 1
White
18 5
Gần đây tôi có dịp đụng vào CMake, nên có tìm hiểu một chút về nó. Hy vọng có ích cho anh em. Nó cung cấp tính năng sinh ra Makefile một cách hiệu...
Phùng Văn Tú viết gần 3 năm trước
18 5
White
6 1
Xử lí song song từ xa xưa cho đến gần đây là lãnh vực cao cấp hầu như chỉ dành cho các nhà khoa học. Có ít nhất 2 nguyên nhân: Xử lí song song đòi...
Ngoc Dao viết hơn 2 năm trước
6 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
23 bài viết.
61 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!