Trong bài toán này, chúng ta được cung cấp hai số, num1 và num2. Nhiệm vụ của chúng ta là tìm vị trí của bit lệch ngoài cùng bên trái cho hai số. Chúng ta cần in bit đầu tiên không giống nhau cho cả hai số trong biểu diễn nhị phân tương ứng của chúng. Độ dài của cả hai cần giống nhau để tìm ra bit. Điều này được thực hiện bằng cách thêm các số 0 vào đầu số có ít bit hơn.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
num1 = 4, num2 = 7
Đầu ra
1
Giải thích
Biểu diễn nhị phân của 4 là 100
Biểu diễn nhị phân của 7 là 111
Bit đầu tiên không giống nhau.
Phương pháp tiếp cận giải pháp
Một cách tiếp cận để giải quyết vấn đề trước tiên là cân bằng số bit trong cả hai số bằng cách nhân nó với 2 (chênh lệch bit) . Và việc lấy XOR của cả hai số sẽ chỉ trả về 1 ở những nơi mà các bit của chúng khác nhau. Vì vậy, trong XOR này, chúng tôi sẽ tìm vị trí đầu tiên và sau đó thêm 1 vào nó để tạo ra vị trí cần thiết.
Thuật toán
Bước 1 - Cân bằng các bit của các số bằng cách nhân nhỏ hơn chỉ với (2 ^ (chênh lệch độ dài bit)).
Bước 2 - Thực hiện thao tác XOR trên num1 và num2.
Bước 3 - Chênh lệch bit bằng tổng số (bitCount - XORbitCount + 1).
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
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;
} Đầu ra
The position of leftmost dis-similar bit of the two number is 4