এই সমস্যায় আমাদের একটি সংখ্যা N দেওয়া হয়েছে যার বাইনারি উপস্থাপনায় শুধুমাত্র একটি সেট বিট রয়েছে। আমাদের কাজ হল একমাত্র সেট বিটের অবস্থান খুঁজে বের করা। যদি নম্বরটিতে শুধুমাত্র একটি সেট বিট থাকে তাহলে নম্বরটির অবস্থান ফেরত দিন অন্যথায় অবৈধ নম্বর প্রিন্ট করুন।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
N = 32
আউটপুট
6
ব্যাখ্যা
Binary representation of the number is 10000.
সমাধান পদ্ধতি
আমরা আরও এগিয়ে যাওয়ার আগে একটি তথ্য জানতে হবে যে সংখ্যাটি 2 এর পাওয়ার হলে শুধুমাত্র 1 সেট বিট থাকবে। অন্যথায় এটিতে আরও বেশি সংখ্যক সেট বিট থাকবে।
একটি সহজ সমাধান হল ডানদিকের বিট থেকে শুরু করে তারপর বিটের মান পরীক্ষা করুন। এটি সেট করা আছে কি না তা পরীক্ষা করার জন্য আমরা একটি লুপ ব্যবহার করব৷
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
সমস্যা সমাধানের একটি বিকল্প পদ্ধতি হল সংখ্যাটিকে 0 না হওয়া পর্যন্ত ডানদিকে স্থানান্তর করতে শিফট অপারেশন ব্যবহার করে। শেষে 0 এ পৌঁছানোর জন্য করা শিফটের সংখ্যা হল সেট বিটের অবস্থান।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
সমস্যা সমাধানের আরেকটি পদ্ধতি হল গণিত সূত্র ব্যবহার করা। আমরা জানি যে,
2i = n, where n is the number and i is the position of the number The values of i here can be found using the formula, i = log2(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
