এই সমস্যাতে, আমাদের একটি সংখ্যা N দেওয়া আছে যার বাইনারি রিপ্রেজেন্টেশনে শুধু একটি সেট বিট (set bit) আছে। আমাদের কাজ হলো সেট বিটের পজিশন (position) বের করা। যদি সংখ্যাটিতে একটিমাত্র সেট বিট থাকে তবে তার পজিশন রিটার্ন করুন, অন্যথায় "Invalid number" প্রিন্ট করুন।
উদাহরণ দিয়ে সমস্যা বোঝা যাক,
ইনপুট
N = 32
আউটপুট
6
ব্যাখ্যা
32-এর বাইনারি রিপ্রেজেন্টেশন: 100000
সমাধানের পদ্ধতি
আগে একটি факт জানা দরকার: একটি সংখ্যার শুধু ১টি সেট বিট থাকবে যদি সেটি ২-এর ঘাত (power of 2) হয়। অন্যথায় তার একাধিক সেট বিট থাকবে।
একটি সহজ সমাধান হলো ডান পাশ থেকে (rightmost bit) বিটগুলো চেক করা। আমরা একটি লুপ ব্যবহার করব সেট বিট কিনা চেক করার জন্য।
সমাধান কোড (বিট চেকিং):
উদাহরণ
#include <iostream>
using namespace std;
bool isPowerOfTwo(unsigned n) {
if(n > 0) {
while(n % 2 == 0)
n /= 2;
if(n == 1)
return true;
}
if(n == 0 || n != 1)
return false;
return false;
}
int findPostionOfSetBit(unsigned n) {
unsigned i = 1, position = 1;
while (!(i & n)) {
i = i << 1;
++position;
}
return position;
}
int main(void){
int n = 64;
if(!isPowerOfTwo(n))
cout<<"Invalid Number!";
else
cout<<"The position of the number "<<n<<" is "<<findPostionOfSetBit(n);
return 0;
}
আউটপুট
The position of the number 64 is 7
এই সমস্যা সমাধানের একটি বিকল্প পদ্ধতি হলো শিফট অপারেশন (shift operation) ব্যবহার করে সংখ্যাকে ডান দিকে শিফট করা যতক্ষণ না সেটি ০ হয়ে যায়। শেষে ০ পর্যন্ত পৌঁছাতে কতবার শিফট করা হয়েছে সেটিই সেট বিটের পজিশন।
সমাধান কোড (রাইট শিফট):
উদাহরণ
#include <iostream>
using namespace std;
bool isPowerOfTwo(unsigned n) {
if(n > 0) {
while(n % 2 == 0)
n /= 2;
if(n == 1)
return true;
}
if(n == 0 || n != 1)
return false;
return false;
}
int findPostionOfSetBit(unsigned n) {
unsigned position = 0;
while (n) {
n = n >> 1;
++position;
}
return position;
}
int main(void){
int n = 64;
if(!isPowerOfTwo(n))
cout<<"Invalid Number!";
else
cout<<"The position of the number "<<n<<" is "<<findPostionOfSetBit(n);
return 0;
}
আউটপুট
The position of the number 64 is 7
এই সমস্যা সমাধানের আরেকটি পদ্ধতি হলো গাণিতিক সূত্র ব্যবহার করা। আমরা জানি,
2^i = n, যেখানে n হলো সংখ্যা এবং i হলো সেট বিটের পজিশন i-এর মান বের করা যায় সূত্র দিয়ে: i = log₂(n)
সমাধান কোড (লগারিদম):
উদাহরণ
#include <iostream>
#include <math.h>
using namespace std;
bool isPowerOfTwo(unsigned n) {
if(n > 0) {
while(n % 2 == 0)
n /= 2;
if(n == 1)
return true;
}
if(n == 0 || n != 1)
return false;
return false;
}
int findPostionOfSetBit(unsigned n) {
unsigned position = log2(n) + 1;
return position;
}
int main(void){
int n = 64;
if(!isPowerOfTwo(n))
cout<<"Invalid Number!";
else
cout<<"The position of the number "<<n<<" is "<<findPostionOfSetBit(n);
return 0;
}
আউটপুট
The position of the number 64 is 7
