Làm cách nào để xác định số bit tương tự?

Question

Tôi cần phải so sánh hai số và tìm những điểm giống nhau trong các bit quan trọng hơn. Tôi đang cố gắng xác định số bit có ý nghĩa ít nhất khác nhau.

10111000 
10111011 

184 và 187 yêu cầu bù trừ hai, vì chỉ có hai bit có ý nghĩa nhất khác nhau.

10111011 
11111011 

187 và 251 yêu cầu bù đắp bảy, vì bit thứ bảy ít quan trọng nhất khác nhau.

Ý tưởng đầu tiên của tôi là XOR các số với nhau, sau đó chuyển bit sang phải cho đến khi số bằng 0. Tôi cảm thấy như có một giải pháp khôn ngoan hơn cho điều này mà không liên quan đến vòng lặp, nhưng tôi đã không làm đủ bit-twiddling của riêng tôi để đến với nó.

Giải pháp cần làm việc cho bất kỳ 64 bit nào, vì số của tôi đang được lưu trữ dưới dạng UInt64. Điều này đang được viết bằng C#, nhưng giải pháp rất có thể là ngôn ngữ bất khả tri.

---

11101101 
11010101 

Sẽ cần một bù đắp của 6 bit. Tôi đang cố gắng tìm ra bao nhiêu bit tương tự mà tôi có thể lấy ra khỏi đầu.

Answer 1

#include <stdio.h> 
#include <stdlib.h> 

#define TO_L(s) (strtol((s), NULL, 16)) 

int tsb(unsigned long xa, unsigned long xb) { 
    unsigned long v = xa^xb; 
    static const unsigned long b[] = { 
    0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000L, 0xFFFFffff00000000L 
    }; 
    static const unsigned int S[] = { 1, 2, 4, 8, 16, 32 }; 
    unsigned int r = 0; 

#define STEP(i) \ 
    if(v & b[i]) { \ 
    int t = S[i]; \ 
    v >>= t;  \ 
    r |= t;  \ 
    } 
    STEP(5) 
    STEP(4) 
    STEP(3) 
    STEP(2) 
    STEP(1) 
    STEP(0) 
    return r; 
} 

int main(int ac, char **av) { 
    return printf("%d\n", tsb(TO_L(av[1]), TO_L(av[2]))), 0; 
} 

Tôi nghĩ điều này thực hiện thuật toán của bạn và nó rất nhanh, chỉ cần 6 bước. Xem này great source of bit twiddling hacks.

so ross$ ./a.out 1f f 
4 
so ross$ ./a.out 471234abcdabcd 981234abcdabcd 
55 
so ross$ ./a.out 1deadbeef 7feedface 
34 

Answer 2

Something như

floor(log(184^187)/log(2)) + 1 

Không vòng lặp, nhưng có thể không được nhanh hơn, vì log trong một hoạt động tốn kém. Bạn nên kiểm tra nó, và so sánh với một vòng lặp đơn giản với bit-shifting.

Đôi khi vòng lặp (được mã hóa tốt) nhanh hơn không có vòng lặp, đặc biệt nếu bạn có tối đa 64 lần lặp và thường ít hơn.

---

phiên bản hiệu quả hơn của mã của tôi:

Pre-compute

double Ilog2 = 1/log(2); 

và sau đó mỗi khi bạn cần nó

floor(log(184^187) * ILog2) + 1 

Answer 3

Âm thanh như bạn đã phát hiện thủ thuật chính; r = x XOR y, sau đó tìm bit cao nhất trong r. Có một loạt các cách khác nhau để giải quyết that problem here. Nhanh nhất hiện nó trong O (n) hoạt động bằng cách tách r một nửa và kiểm tra nếu phần trên là số không. Nếu bạn đang làm điều này trên một số cố định của các bit (bạn nói 64) sau đó cuộn các vòng để có được một loạt các xét nghiệm:

pos = 0 
r = x XOR y 
if r>>32 == 0 : 
    r = r & 2^32-1 
else 
    pos += 32 
    r = r>>32 
if r>>16 == 0 : 
    r = r & 2^16-1 
else 
    pos += 16 
    r = r>16 
... etc 

Answer 4

Bạn có thể viết một O (log (n)) vòng lặp để tìm ra cao nhất thiết lập khá dễ dàng:

int findHighestSetBit(unsigned long long x) { 
    int rv = 0; 
    if (x == 0) 
     return -1; // no set bits 
    for (int shift = 32; shift > 0; shift >>= 1) { 
     if (x >> shift) { 
      rv += shift; 
      x >>= shift; 
     } 
    } 
    return rv+1; // number least significant bit as '1' rather than '0' 
} 

nếu điều này quá chậm, bạn có thể tự hủy vòng lặp 5 lần.

Answer 5

Giả sử trước tiên bạn phải làm điều đó cho số 8 bit. cách nhanh nhất là 256 byte tra cứu bảng với giá trị biên dịch sẵn:

static unsigned char highest_bit_num_LUT[256] = {0, 1, 2, 2, 3, etc }; // precomputed 

unsigned diff = (unsigned)a^(unsigned)b; // sure you need XOR and not MINUS? 
unsigned highest_bit_num = highest_bit_num_LUT[diff & 0xff]; 

nay mở rộng nó cho đếm bit cao hơn:

static unsigned char highest_bit_num_LUT[256] = {0, 1, 2, 2, 3, etc }; // precomputed 
unsigned diff = (unsigned)a^(unsigned)b; // sure you need XOR and not MINUS? 
unsigned highest_bit_num = 0; 
for (int i = 7; i >= 0; i--)  
    if (diff >> (i*8)){ // found most significant non-zero byte 
     highest_bit_num = i*8 + highest_bit_num_LUT[diff >> (i*8)]; 
     break; 
    } 

vì vậy bây giờ chúng ta có ít nhất 8 lần lặp lại.

EDIT: sẽ nhanh hơn khi sử dụng ý tưởng DigitalRoss cho 3 lần lặp đầu tiên và sau đó sử dụng LUT.