এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা X দেওয়া হয়েছে৷ আমাদের কাজ হল 0 থেকে X তে রূপান্তরিত করার জন্য নেওয়া পদক্ষেপগুলির মোট সংখ্যা খুঁজে বের করা৷
বৈধ রূপান্তর − একটি ধাপ গণনা করা হয় যখন একটি রূপান্তর A থেকে B তে সংঘটিত হয়। রূপান্তরটি সংঘটিত হওয়ার শর্ত হল A !=B এবং A &B =A (&বিটওয়াইজ AND)। সুতরাং, 1 ধাপ A থেকে B তে রূপান্তরিত হচ্ছে এবং আমাদের একটি প্রোগ্রাম তৈরি করতে হবে যা 0 থেকে X রূপান্তর করার জন্য সর্বাধিক সংখ্যক ধাপ গণনা করবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট − X =7
আউটপুট − 3
ব্যাখ্যা −
আমাদের 0 থেকে 7 রূপান্তর করতে হবে।
Steps taken will be Step1: 0(00) to 1(01) , 0!= 1 and 0&1 = 0, transform 00=>01 Step2: 1(001) to 3(011) , 1!= 3 and 1&3 = 1, transform 001=>011 Step3: 3(0011) to 7(0111) , 3!= 7 and 3&7 = 3, tranform 0011=>0111.
এই সমস্যাটি সমাধান করার জন্য, আমরা X-এ সেট বিটের সংখ্যা গণনা করব যা 0 থেকে X থেকে সর্বাধিক রূপান্তর দেবে।
যেহেতু আমাদের সর্বাধিক রূপান্তর প্রয়োজন, আমাদের প্রতিটি সেট বিটের জন্য ধাপে ধাপে যেতে হবে (মান 1 সহ বিট)। বিট-এর পর বিট ট্রান্সফর্মেশন 0 থেকে X-এ রূপান্তরিত করার সর্বোচ্চ ধাপ দেবে।
A থেকে B তে রূপান্তরে, A এর সমস্ত সেট বিট B তে সেট করা উচিত, তবে বিপরীতটি প্রয়োজনীয় নয়। সুতরাং, ন্যূনতম রূপান্তর 1 হতে পারে কারণ 0-তে কোনও সেট বিট নেই যা ক্ষুদ্রতম রূপান্তরকে সরাসরি করে।
আমরা যে উদাহরণটি নিয়েছি তাতে দেখতে পাচ্ছি, সংখ্যার বাইনারি রূপান্তর এবং তাদের বিটওয়াইজ ANDs।
উদাহরণ
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম -
//বিটওয়াইজ এবং C++ এ 0 থেকে X রূপান্তর করার জন্য সর্বাধিক ধাপগুলি খুঁজে বের করার প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int maxtransformation(int x){
int steps = 0;
// counting number of bits
while (x) {
steps += x & 1;
x >>= 1;
}
return steps;
}
int main(){
int x = 7;
cout<<"The maximum number of steps to transform 0 to "<<x<<" with bitwise AND are "<<maxtransformation(x);
return 0;
} আউটপুট
The maximum number of steps to transform 0 to 7 with bitwise AND are 3
