ในปัญหานี้เราได้รับสองตัวเลข num1 และ num2 งานของเราคือการหาตำแหน่งของบิตที่เหมือนกันทางซ้ายสุดของตัวเลขสองตัว เราจำเป็นต้องพิมพ์บิตแรกซึ่งไม่เหมือนกันสำหรับตัวเลขทั้งสองในการแทนค่าไบนารีตามลำดับ ความยาวของทั้งสองต้องเท่ากันเพื่อค้นหาบิต ทำได้โดยเติม 0 ต่อท้ายตัวเลขที่มีบิตน้อยกว่า
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
num1 = 4, num2 = 7
ผลลัพธ์
1
คำอธิบาย
การแทนค่าไบนารีของ 4 คือ 100
การแทนค่าไบนารีของ 7 คือ 111
บิตแรกไม่เหมือนกัน
แนวทางการแก้ปัญหา
แนวทางในการแก้ปัญหาคือขั้นแรกให้จำนวนบิตเท่ากันในทั้งสองจำนวนโดยคูณด้วย 2 (ความแตกต่างของบิต) . และการรับ XOR ของตัวเลขทั้งสองซึ่งจะคืนค่า 1 เฉพาะในตำแหน่งที่บิตต่างกัน ดังนั้นใน XOR นี้ เราจะหาตำแหน่งแรกแล้วบวก 1 เข้าไปเพื่อให้ได้ตำแหน่งที่ต้องการ
อัลกอริทึม
ขั้นตอนที่ 1 − ทำให้บิตของตัวเลขเท่ากันโดยคูณน้อยกว่าด้วย (2 ^ (ความแตกต่างของความยาวบิต))
ขั้นตอนที่ 2 − ดำเนินการ XOR บน num1 และ num2
ขั้นตอนที่ 3 − ความแตกต่างของบิตเท่ากับผลรวม (bitCount - XORbitCount + 1)
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The position of leftmost dis-similar bit of the two number is 4
