หาตำแหน่งบิตที่ต่างกันซ้ายสุดของสองตัวเลขใน C++

ในปัญหานี้ เราได้รับตัวเลขสองตัว num1 และ num2 งานของเราคือหาตำแหน่งของบิตที่ต่างกันซ้ายสุดของสองตัวเลข เราต้องพิมพ์บิตแรกที่ไม่เหมือนกันสำหรับทั้งสองตัวเลขในการแทนค่าไบนารีของแต่ละตัว ความยาวของทั้งสองต้องเท่ากันเพื่อหาบิต ทำได้โดยการเติม 0 ไปด้านหน้าของตัวเลขที่มีบิตน้อยกว่า

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

num1 = 4, num2 = 7

Output

1

อธิบาย

การแทนค่าไบนารีของ 4 คือ 100

การแทนค่าไบนารีของ 7 คือ 111

บิตแรกไม่เหมือนกัน

วิธีแก้ปัญหา

วิธีแก้คือทำให้จำนวนบิตของทั้งสองตัวเลขเท่ากันโดยคูณตัวเลขที่เล็กกว่าด้วย 2^(bit difference) แล้วทำ XOR ของทั้งสองตัวเลข ซึ่งจะคืนค่า 1 เฉพาะตำแหน่งที่บิตต่างกัน ดังนั้น ใน XOR นี้ เราจะหาตำแหน่งแรกแล้วบวก 1 เข้าไปจะได้ตำแหน่งที่ต้องการ

อัลกอริทึม

ขั้นตอนที่ 1 - ทำให้บิตของตัวเลขเท่ากันโดยคูณตัวเลขที่เล็กกว่าด้วย (2 ^ (bit-length difference))

ขั้นตอนที่ 2 - ทำ XOR operation บน num1 และ num2

ขั้นตอนที่ 3 - ความต่างของบิตเท่ากับ total (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