मूल्यांकन करें कि कोई संख्या 4

Question

की पूर्णांक शक्ति है, तो निम्न कार्य का मूल्यांकन करने का दावा किया जाता है कि कोई संख्या 4 की पूर्णांक शक्ति है या नहीं। मुझे समझ में नहीं आता कि यह कैसे काम करता है?

bool fn(unsigned int x) 
{ 
if (x == 0) return false; 
if (x & (x - 1)) return false; 
return x & 0x55555555; 
} 

Answer 1

पहली शर्त 0 से बाहर है, जो स्पष्ट रूप से 4 की शक्ति नहीं है लेकिन गलत तरीके से निम्नलिखित दो परीक्षणों को पारित करेगी। (संपादित करें: नहीं, यह इंगित नहीं किया जाएगा। पहला परीक्षण अनावश्यक है।)

अगला वाला एक अच्छा चाल है: यह सही होता है यदि केवल और यदि संख्या 2 की शक्ति है। दो की शक्ति केवल एक बिट सेट होने के द्वारा विशेषता है। एक बिट सेट के साथ एक संख्या शून्य से एक परिणाम में उस बिट के पिछले सभी बिट्स के साथ एक संख्या में परिणाम (यानी 0x1000 शून्य एक 0x0111 है)। और उन दो संख्याओं, और आप 0 प्राप्त करते हैं। किसी भी अन्य मामले में (यानी 2 की शक्ति नहीं), कम से कम एक बिट होगा जो ओवरलैप हो जाएगा।

तो इस बिंदु पर, हम जानते हैं कि यह 2.

x & 0x55555555 रिटर्न गैर शून्य (= सच) यदि कोई भी थोड़ा यह सेट (बिट 0, थोड़ा 2, बिट 4, थोड़ा 6, आदि की एक शक्ति है)। इसका मतलब है कि यह 4 की शक्ति है। (यानी 2 पास नहीं होता है, लेकिन 4 पास, 8 पास नहीं होता है, 16 पास, इत्यादि)।

Answer 2

4 की हर शक्ति शून्य की समान संख्या (बाइनरी प्रतिनिधित्व) के बाद 1 के रूप में होना चाहिए: 100 ... 00:

100 = 4

10000 = 16

1000000 = 64

1. 1 परीक्षण ("अगर") स्पष्ट है।

2. जब प्रपत्र XY100 ... 00 के एक नंबर से 1 घटाने पर आपको XY011 ... 11 मिलता है। तो, दूसरा परीक्षण जांचता है कि इस उदाहरण में संख्या में एक से अधिक "1" बिट है (XY)।

3. अंतिम परीक्षण जांचता है कि यह एकल "1" सही स्थिति में है, यानी, बिट # 2,4,6 आदि। यदि यह नहीं है, तो मास्किंग() एक गैर-परिणाम परिणाम देगा।