Làm thế nào để thực hiện Bitcount chỉ sử dụng các toán tử Bitwise?

Question

Nhiệm vụ là thực hiện logic đếm bit chỉ sử dụng toán tử bitwise. Tôi nhận được nó làm việc tốt, nhưng tôi tự hỏi nếu ai đó có thể đề xuất một cách tiếp cận thanh lịch hơn.

Chỉ cho phép sử dụng bitwise. Không "nếu", "cho" v.v.

int x = 4; 

printf("%d\n", x & 0x1); 
printf("%d\n", (x >> 1) & 0x1); 
printf("%d\n", (x >> 2) & 0x1); 
printf("%d\n", (x >> 3) & 0x1); 

Cảm ơn bạn.

Answer 1

Từ http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

unsigned int v; // count bits set in this (32-bit value) 
unsigned int c; // store the total here 

c = v - ((v >> 1) & 0x55555555); 
c = ((c >> 2) & 0x33333333) + (c & 0x33333333); 
c = ((c >> 4) + c) & 0x0F0F0F0F; 
c = ((c >> 8) + c) & 0x00FF00FF; 
c = ((c >> 16) + c) & 0x0000FFFF; 

Edit: Phải thừa nhận rằng đó là một chút tối ưu hóa mà làm cho nó khó khăn hơn để đọc. Nó dễ dàng hơn để đọc như:

c = (v & 0x55555555) + ((v >> 1) & 0x55555555); 
c = (c & 0x33333333) + ((c >> 2) & 0x33333333); 
c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F); 
c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF); 
c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF); 

Mỗi bước của những năm, thêm bit láng giềng với nhau trong nhóm 1, sau đó 2, sau đó 4, vv Phương pháp này có trụ sở tại chia để trị.

Trong bước đầu tiên, chúng tôi cộng các bit 0 và 1 và đặt kết quả trong phân đoạn bit 2 0-1, thêm bit 2 và 3 và đặt kết quả trong phân đoạn hai bit 2-3 ... Trong bước thứ hai, chúng ta thêm hai bit 0-1 và 2-3 lại với nhau và đặt kết quả trong 4-bit 0-3, cộng hai bit 4-5 và 6-7 lại với nhau và đặt kết quả trong bốn-bit 4-7 vv ...

Ví dụ:

So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1) 
After the first step I have:  0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10 
In the second step I have:  0000000100010011 (00+00 00+01 01+00 01+10) = 0000 0001 0001 0011 
In the fourth step I have:  0000000100000100 ( 0000+0001  0001+0011 ) = 00000001 00000100 
In the last step I have:   0000000000000101 (  00000001+00000100  ) 

tương đương với 5, đó là kết quả chính xác

Answer 2

Một số giải pháp thú vị here.

Nếu các giải pháp trên là quá nhàm chán, đây là một C đệ quy phiên bản miễn kiểm tra điều kiện hay vòng lặp:

int z(unsigned n, int count); 
    int f(unsigned n, int count); 

    int (*pf[2])(unsigned n, int count) = { z,f }; 

    int f(unsigned n, int count) 
    { 
    return (*pf[n > 0])(n >> 1, count+(n & 1)); 
    } 

    int z(unsigned n, int count) 
    { 
    return count; 
    } 

    ... 
    printf("%d\n", f(my_number, 0)); 

Answer 3

tôi sẽ sử dụng một mảng tính toán trước

uint8_t set_bits_in_byte_table[ 256 ]; 

Các i - mục nhập thứ hai trong bảng này lưu trữ số bit đã đặt trong byte i, ví dụ: set_bits_in_byte_table[ 100 ] = 3 vì có 3 1 bit trong biểu diễn nhị phân của số thập phân 100 (= 0x64 = 0110-0100).

Sau đó, tôi sẽ cố gắng

size_t count_set_bits(uint32_t x) { 
    size_t count = 0; 
    uint8_t * byte_ptr = (uint8_t *) &x; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    return count; 
} 

Answer 4

Dưới đây là một minh họa đơn giản để các answer:

a b c d  0 a b c  0 b 0 d  
&    &    + 
0 1 0 1  0 1 0 1  0 a 0 c 
-------  -------  ------- 
0 b 0 d  0 a 0 c  a+b c+d 

Vì vậy, chúng tôi có chính xác 2 bit để lưu trữ a + b và 2 bit để lưu trữ c + d. a = 0, 1 vv, do đó, 2 bit là những gì chúng ta cần lưu trữ tổng của chúng. Trong bước tiếp theo, chúng tôi sẽ có 4 bit để lưu trữ tổng giá trị 2 bit, v.v.