एक ही बिटवाइज ऑपरेशन से जाँचें कि कोई संख्या 2 का घात है या नहीं
मान लीजिए आपके पास एक धनात्मक पूर्णांक n है और आपको यह जाँचना है कि क्या वह 2 का घात (power of 2) है। इसे एक ही बिटवाइज ऑपरेशन से किया जा सकता है। यदि हम किसी ऐसी संख्या का बाइनरी स्वरूप देखें जो 2 का घात है, तो उसमें केवल एक ही 1 होता है और शेष सभी बिट्स 0 होते हैं।
2^n संख्या | बाइनरी अभिव्यक्ति |
|---|---|
8 | 1000 |
32 | 100000 |
128 | 10000000 |
अनियमित संख्या | बाइनरी अभिव्यक्ति |
|---|---|
7 | 111 |
67 | 1000011 |
144 | 10010000 |
यह बाइनरी अभिव्यक्ति की परिभाषा से स्पष्ट होता है। बाइनरी अभिव्यक्ति में जिन पोज़ीशनों पर 1 होता है, वे 2 के संबंधित घात को जोड़ते हैं (जैसे 67 = 1 + 2 + 0 + 0 + 0 + 0 + 64, 8 = 0 + 0 + 0 + 8)। इसलिए, किसी संख्या में केवल एक ही 1 बिट होने का अर्थ है कि उस संख्या में 2 के सिर्फ उसी घात का योग है, और कोई अन्य घात मौजूद नहीं है। इस समस्या का सार यह है कि हमें यह जाँचना है कि n के बाइनरी स्वरूप में सिर्फ एक ही 1 है या नहीं।
इसे आसान तरीके से जाँचा जा सकता है: n & (n-1) का परिणाम यदि 0 आता है ⇒ तो वह संख्या 2 का घात है।
किसी ऐसी संख्या के लिए जो 2 का घात नहीं है, n & (n-1) का परिणाम 0 से भिन्न होता है:
7 & 6 = 111 & 110 = 110 (6)
67 & 66 = 1000011 & 1000010 = 1000010 (66)
144 & 143 = 10010000 & 10001111 = 10000000 (128)
लेकिन 2 के घात वाली संख्याओं के लिए यह हमेशा 0 होता है:
8 & 7 = 1000 & 111 = 0
32 & 31 = 100000 & 11111 = 0
128 & 127 = 10000000 & 1111111 = 0
इनपुट
इनपुट की पहली पंक्ति में एक एकल पूर्णांक n (2 ≤ n ≤ ) दिया जाता है।
आउटपुट
यदि n 2 का घात है तो प्रोग्राम को Yes प्रिंट करना चाहिए, अन्यथा No।
उदाहरण
Input | Output |
|---|---|
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB