इस समस्या में, हमें एक पूर्णांक X दिया जाता है। हमारा कार्य 0 से X में बदलने के लिए उठाए गए चरणों की कुल संख्या ज्ञात करना है।
मान्य परिवर्तन - ए से बी में एक परिवर्तन होने पर एक कदम गिना जाता है। परिवर्तन होने की शर्त ए! =बी और ए और बी =ए (और बिटवाइज और है)। तो, 1 कदम ए से बी में बदल रहा है और हमें एक प्रोग्राम बनाना होगा जो 0 से एक्स में बदलने के लिए अधिकतम चरणों की गणना करेगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - एक्स =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 में बदलने के लिए अधिकतम कदम देगा।
ए से बी में परिवर्तन में, ए के सभी सेट बिट्स को बी में सेट किया जाना चाहिए, लेकिन रिवर्स आवश्यक नहीं है। तो, न्यूनतम परिवर्तन 1 हो सकता है क्योंकि 0 में कोई सेट बिट नहीं है जो सबसे छोटे रूपांतरण को प्रत्यक्ष बनाता है।
जैसा कि हम अपने द्वारा लिए गए उदाहरण में देख सकते हैं, संख्याओं और उनके बिटवाइज़ AND पर बाइनरी रूपांतरण।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम -
//प्रोग्राम बिटवाइज के साथ 0 से X में और C++ में बदलने के लिए अधिकतम चरणों को खोजने के लिए
#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