एक ही बिटवाइज ऑपरेशन से जाँचें कि कोई संख्या 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 और n-1 संख्या पर विचार करते हैं, तो उन दोनों की सबसे महत्वपूर्ण (most significant) बिट तभी सुरक्षित रहती है जब n के बाइनरी स्वरूप में सबसे महत्वपूर्ण बिट के अलावा भी अन्य 1 मौजूद हों। यदि n, 2 का घात है ⇒ इसका बाइनरी स्वरूप केवल एक ही 1 रखता है, इसलिए n-1 में वह सबसे महत्वपूर्ण बिट कम हो जाती है (वह 0 हो जाती है) और बाकी बिट्स 1 बन जाते हैं।
दूसरी तरफ, (6, 67, 144 आदि) में कई 1 बिट्स होती हैं, इसलिए उनसे 1 घटाने पर उनका सबसे महत्वपूर्ण बिट कम नहीं होता।इनपुट
इनपुट की पहली पंक्ति में एक एकल पूर्णांक
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