इस समस्या में हमें एक संख्या N दी गई है जिसकी बाइनरी प्रतिनिधित्व में केवल एक सेट बिट है। हमारा कार्य एकमात्र सेट बिट की स्थिति खोजना है। यदि संख्या में केवल एक सेट बिट है तो संख्या की स्थिति वापस करें अन्यथा अमान्य संख्या प्रिंट करें।
आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
N = 32
आउटपुट
6
व्याख्या
संख्या का बाइनरी प्रतिनिधित्व 10000 है।
समाधान दृष्टिकोण
आगे बढ़ने से पहले एक तथ्य जानना आवश्यक है कि संख्या में केवल 1 सेट बिट होगी यदि यह 2 की घात है। अन्यथा इसमें अधिक संख्या में सेट बिट्स होंगे।
एक सरल समाधान सबसे दाएं बिट से शुरू करके बिट्स के मान की जांच करना है। हम यह जांचने के लिए एक लूप का उपयोग करेंगे कि यह सेट है या नहीं।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#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, जहां n संख्या है और i संख्या की स्थिति है i का मान यहां सूत्र का उपयोग करके पाया जा सकता है, 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
