इस समस्या में, हमें एक पूर्णांक X दिया गया है। हमारा कार्य 0 से X में बदलने में लगे कुल चरणों की संख्या ज्ञात करना है।
मान्य परिवर्तन - एक चरण तब गिना जाता है जब A से B में एक परिवर्तन होता है। परिवर्तन होने की शर्त है A != B और A & B = A (& बिटवाइज़ AND है)। तो, 1 चरण A से B में परिवर्तन है और हमें एक प्रोग्राम बनाना है जो 0 से X में बदलने के अधिकतम चरणों की गणना करेगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - X = 7
आउटपुट - 3
व्याख्या -
हमें 0 से 7 में बदलना है।
उठाए गए चरण होंगे चरण1: 0(00) से 1(01), 0!= 1 और 0&1 = 0, परिवर्तन 00=>01 चरण2: 1(001) से 3(011), 1!= 3 और 1&3 = 1, परिवर्तन 001=>011 चरण3: 3(0011) से 7(0111), 3!= 7 और 3&7 = 3, परिवर्तन 0011=>0111।
इस समस्या को हल करने के लिए, हम X में सेट बिट्स की संख्या गिनेंगे जो 0 से X में अधिकतम परिवर्तन देगा।
चूंकि हमें अधिकतम परिवर्तन चाहिए, हमें प्रत्येक सेट बिट (मान 1 वाला बिट) के लिए चरण दर चरण जाना होगा। बिट दर बिट परिवर्तन 0 से X में बदलने के लिए अधिकतम चरण देगा।
A से B में परिवर्तन में, A के सभी सेट बिट्स B में सेट होने चाहिए, लेकिन विपरीत आवश्यक नहीं है। तो, न्यूनतम परिवर्तन 1 हो सकता है क्योंकि 0 में कोई सेट बिट नहीं है जो सबसे छोटा रूपांतरण प्रत्यक्ष बनाता है।
जैसा कि हमने उदाहरण में देखा है, संख्याओं का बाइनरी रूपांतरण और उनके बिटवाइज़ AND।
उदाहरण
हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम -
// C++ में बिटवाइज़ AND से 0 को X में बदलने के अधिकतम चरणों का प्रोग्राम
#include <bits/stdc++.h> using namespace std; int maxtransformation(int x){ int steps = 0; // बिट्स की संख्या गिनना 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
