Cách nhanh nhất để đếm số lần chuyển tiếp bit trong một số không dấu int

Question

Tôi đang tìm cách nhanh nhất để đếm số lần chuyển bit trong một unsigned int.

Nếu int chứa: 0b00000000000000000000000000001010

Số lượng hiệu ứng chuyển tiếp là: 4

Nếu int chứa: 0b00000000000000000000000000001001

Số lượng hiệu ứng chuyển tiếp bao gồm: 3

Ngôn ngữ là C.

Answer 1

int numTransitions(int a) 
{ 
    int b = a >> 1; // sign-extending shift properly counts bits at the ends 
    int c = a^b; // xor marks bits that are not the same as their neighbors on the left 
    return CountBits(c); // count number of set bits in c 
} 

Đối với thực hiện có hiệu quả CountBits thấy http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Answer 2

Ngôn ngữ nào?

Tôi sẽ lặp 64 lần và sau đó bit thay đổi số của bạn để kiểm tra các bit, sau đó lưu trữ bit trước đó và so sánh nó với bit hiện tại. Nếu nó khác, hãy đếm số đếm của bạn.

Answer 3

Ok, với các chuyển động bạn có nghĩa là nếu bạn đi bộ qua chuỗi từ 0-s và 1-s, bạn đếm từng Sự kiện xảy ra rằng một 0 sau 1 hoặc 1 sau một 0.

Đây là dễ dàng bằng cách chuyển bit ra và đếm các thay đổi:

transitions(n) 
    result = 0 
    prev = n mod 2 
    n = n div 2 
    while n<>0 
    if n mod 2 <> prev then 
     result++ 
     prev = n mod 2 
    fi 
    n = n div 2 
    elihw 
    return result 

bạn có thể thay thế mod và div theo ca.

Answer 4

Nhanh nhất phụ thuộc vào kịch bản của bạn: Khi bạn chỉ định kiểu dữ liệu của bạn dưới dạng hằng số có kích thước (unsigned int), có thể với bảng tra cứu. Nhưng khi bạn cần thao tác này chỉ khi chi phí liên tục để bắt đầu bảng quá lớn, và quét + đếm qua int nhanh hơn rất nhiều.

Tôi đoán tổng thể tốt nhất sẽ là kết hợp: Tra cứu bảng cho một byte hoặc từ (mục 256 hoặc 64k không nhiều), sau đó kết hợp các byte/từ theo bit cuối cùng/đầu tiên của chúng.

Answer 5

Trong C/C++ tôi sẽ làm như sau:

unsigned int Transitions(unsigned int value) 
{ 
    unsigned int result = 0; 

    for (unsigned int markers = value^(value >> 1); markers; markers = markers >> 1) 
    { 
     if (markers & 0x01) result++; 
    } 

    return result; 
} 

Answer 6

Dưới đây là các mã sử dụng sự thay đổi số học + xor và phương pháp Kernighan cho đếm chút :

int count_transitions(int x) 
{ 
    assert((-1 >> 1) < 0); // check for arithmetic shift 
    int count = 0; 
    for(x ^= (x >> 1); x; x &= x - 1) 
     ++count; 
    return count; 
}