2 की उच्चतम शक्ति की गणना करना जो समान रूप से सी

Question

में एक संख्या को विभाजित करता है, मुझे निर्धारित करने के लिए कुछ तर्क लिखने की आवश्यकता है, यहां तक ​​कि संख्या भी दी गई है। दो की उच्चतम शक्ति जो समान रूप से इसे विभाजित करती है। 2^एन का अधिकतम मूल्य क्या है जहां इनपुट% 2^n == 0?

आईई:
इनपुट -> आउटपुट

4 (0100) -> 4 

8 (1000) -> 8 

12 (1100) -> 4 

14 (1110) -> 2 

24 (11000) -> 8 

etc.... 

यह कुछ बिटवाइज़ तर्क यह है कि बाहर काम कर सकते हैं वहाँ दिखाई देता है: जब बाइनरी में इनपुट पर देख रहे हैं, सबसे दायीं ओर एक सा समाधान प्रतीत होता है। मैं सी में यह मान कैसे निर्धारित करूं? क्या कोई और समाधान आसान हो सकता है?

धन्यवाद जोनाथन

Answer 1

चल बिन्दु अंकगणित का प्रयोग कर के बिना:

((x^(x - 1)) >> 1) + 1 

सरलीकरण और धार मामलों पाठक के लिए व्यायाम के रूप में छोड़ दिया जाता है।

Answer 2

आप 2 के पूरक गणित ग्रहण करने के लिए तैयार हैं, तो:

x & -x

आप बात की इस तरह का एक बहुत करते हैं (या यहां तक ​​कि अगर आप सिर्फ लगता है यह दिलचस्प), अपने आप को उसकी एक प्रति प्राप्त पुस्तक "हैकर डिलिट"।

संपादित करें: अवकर सही ढंग से नोट करता है कि अगर यह हस्ताक्षरित है तो यह 2 के पूरक पर निर्भर नहीं है। मानक के प्रासंगिक अनुभाग, §6.2.5 है पैरा 9:

एक अहस्ताक्षरित ऑपरेंड शामिल कभी नहीं अतिप्रवाह कर सकते हैं अभिकलन, क्योंकि वह द्वारा प्रतिनिधित्व नहीं किया जा सकता एक परिणाम जिसके परिणामस्वरूप अहस्ताक्षरित पूर्णांक प्रकार कम सापेक्ष है के सबसे बड़े मान से अधिक प्रकार का प्रतिनिधित्व प्रकार से प्रदर्शित किया जा सकता है।

"एक सबसे बड़ा मूल्य से अधिक" एक विशेष रूप से विकृत कार्यान्वयन के लिए कुछ लचीलेपन की तुलना में (विशेष रूप से, एक कार्यान्वयन कि द्विआधारी का उपयोग नहीं करता, उदाहरण के लिए) को छोड़ देता है, लेकिन आप सुंदर है कि मुठभेड़ की संभावना नहीं कर रहे हैं।

Answer 3

हम (~x + 1) द्वारा (-x) की जगह ले सकता:

x & (~x+1) 

Low Level Bit Hacks You Absolutely Must Know विस्तृत विवरण प्रदान करता है।

Answer 4

फॉर्म 2^एन में एक संख्या बाइनरी में 1 से लिखा गया है जिसके बाद 0 या 0 0 की श्रृंखला है। उदाहरण के लिए, 1, 10, 100, 1000, ... आदि के लिए 2.

की सारी शक्ति 2 की सर्वोच्च शक्ति है कि दी गई संख्या बिताते हैं प्राप्त करने के लिए कर रहे हैं, तो आपको निम्न दो कदम कर सकते हैं:

1. बाइनरी रूप में संख्या लिखें। उदाहरण के लिए, यदि संख्या 168 है, तो 10101000 लिखें।

2. हड़ताल बंद दाहिने हाथ की ओर से पहली बिट है कि 168 के मामले में 1. होता है, क्या रहता है 1000 (= दशमलव में 8) है से पहले सभी बिट्स 10101000.

के पहले भाग से दूर हड़ताली के बाद

आपका परिणाम क्या रहता है - यानी, 2 की उच्चतम शक्ति जो संख्या को विभाजित करती है।

प्रोग्रामेटिक रूप से, एक्स आपका इनपुट नंबर दें। फिर अपने वांछित उत्पादन होगा: x - (x^(x-1))

स्पष्टीकरण:

x^(x-1) [अर्थ एक्स XOR एक्स 1] LSB (कम से कम महत्वपूर्ण बिट) की ओर

x - (x^(x-1)) से पहले 1 से छुटकारा हो जाता से छुटकारा मिलता है शेष भाग, और एलएसबी पक्ष से केवल पहले 1 को बरकरार रखता है।