Tìm vị trí bit khác biệt trái nhất của hai số trong C++

Trong bài toán này, cho hai số num1 và num2. Nhiệm vụ là tìm vị trí bit khác biệt trái nhất (leftmost dis-similar bit). In bit đầu tiên khác nhau trong biểu diễn nhị phân. Cần cùng độ dài bit (thêm 0 dẫn đầu cho số ít bit hơn).

Ví dụ minh họa:

Đầu vào

num1 = 4, num2 = 7

Đầu ra

1

Giải thích

Nhị phân 4 = 100, 7 = 111. Bit đầu tiên khác nhau.

Phương pháp giải

Cân bằng độ dài bit: nhân số nhỏ hơn với 2^(chênh lệch bit). XOR hai số -> kết quả có bit 1 tại vị trí khác nhau. Tìm vị trí bit 1 đầu tiên: vị trí = tổng bit - bit XOR + 1.

Thuật toán

Bước 1 - Cân bằng bit: nhân số nhỏ với 2^(chênh lệch độ dài bit).

Bước 2 - XOR hai số.

Bước 3 - Vị trí khác biệt = độ dài bit max - độ dài bit XOR + 1.

Chương trình minh họa:

Ví dụ

#include <iostream> 
#include <math.h> 
using namespace std; 

int findmisMatchBit(int num1, int num2) { 
    if (num1 == num2) return 0; 
    int num1Size = floor(log2(num1)) + 1; 
    int num2Size = floor(log2(num2)) + 1; 
    int BitSizeDiff = abs(num1Size - num2Size); 
    int maxBitSize = max(num1Size, num2Size); 
    if (num1Size > num2Size) num2 *= pow(2, BitSizeDiff); 
    else num1 *= pow(2, BitSizeDiff); 
    int XOR = num1 ^ num2; 
    int XORBitSize = floor(log2(XOR)) + 1; 
    return (maxBitSize - XORBitSize + 1); 
} 

int main() { 
    int num1 = 43, num2 = 765; 
    cout<<"The position of leftmost dis-similar bit of the two number is "<<findmisMatchBit(num1, num2); 
    return 0; 
}

Kết quả

The position of leftmost dis-similar bit of the two number is 4