এই সমস্যাতে, আমাদের দুটি সংখ্যা num1 এবং num2 দেওয়া আছে। আমাদের কাজ হলো দুটি সংখ্যার বামপাশের সবচেয়ে প্রথম অমিল বিট (leftmost dissimilar bit) এর পজিশন বের করা। অর্থাৎ, তাদের বাইনারি রিপ্রেজেন্টেশনে প্রথম কোন বিট মিলছে না সেটি বের করতে হবে। দুটি সংখ্যার বিটের দৈর্ঘ্য একই হতে হবে। এজন্য কম বিট वाली সংখ্যার শুরুতে ০-গুলো যোগ করা হয়।
উদাহরণ দিয়ে সমস্যা বোঝা যাক,
ইনপুট
num1 = 4, num2 = 7
আউটপুট
1
ব্যাখ্যা
4-এর বাইনারি রিপ্রেজেন্টেশন: 100
7-এর বাইনারি রিপ্রেজেন্টেশন: 111
প্রথম বিটটি মিলছে না।
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের একটি পদ্ধতি হলো প্রথমে দুটি সংখ্যার বিট সংখ্যা সমান করা ছোট সংখ্যাকে 2^(বিট পার্থক্য) দিয়ে গুণ করে। তারপর দুটি সংখ্যার XOR অপারেশন করা যাতে শুধু যেখানে বিটগুলো আলাদা সেখানে ১ আসে। এই XOR-এ প্রথম ১-এর পজিশন বের করে ১ যোগ করলে প্রয়োজনীয় পজিশন পাওয়া যায়।
আলগরিদম
স্টেপ ১ − ছোট সংখ্যাকে (2^(বিট দৈর্ঘ্যের পার্থক্য)) দিয়ে গুণ করে বিট সংখ্যা সমান করা।
স্টেপ ২ − num1 এবং num2-এর XOR অপারেশন করা।
স্টেপ ৩ − বিট পার্থক্য = মোট (বিটকাউন্ট - XORবিটকাউন্ট + ১)।
সমাধান কোড:
উদাহরণ
#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
