दो संख्याओं के एक एक्सओआर और एसयूएम को देखते हुए, उन्हें संतुष्ट करने वाले जोड़े की संख्या कैसे प्राप्त करें?

Question

मुझे लगता है कि सवाल थोड़ा उलझन में हो सकता है। तो, मैं इसे पहले समझाऊंगा।

मान लें कि दो नंबरों के एक्सओआर और एसयूएम दिए गए हैं। (नोट कई जोड़े है कि इस को पूरा कर सकते हैं देखते हैं कि।)

उदाहरण के लिए, XOR 5 है और योग 9 है वहाँ 4 जोड़े योग और XOR संतोषजनक रहे हैं। वे (2, 7), (3, 6), (6, 3), (7, 2) हैं। तो 2+7=9 और 2^7=5।

मैं सिर्फ संख्या जोड़ना चाहता हूं जो एसयूएम और एक्सओआर को संतुष्ट करता है। तो उदाहरण में मैंने उत्तर दिया कि 4 उत्तर पर्याप्त है। मुझे यह जानने की जरूरत नहीं है कि कौन से जोड़े उन्हें संतुष्ट करते हैं।

मैंने इस समस्या को here से लिया।

मैंने here उत्तर के लिए चेक किया। यह एक ओ (एन) समाधान प्रदान करता है जो पर्याप्त नहीं है।

एक संपादकीय है जो इस समस्या पर समाधान प्रदान करता है। यह here पाया जा सकता है। (627 ए के समाधान की तलाश करें)

समस्या यह है कि मैं समाधान को समझ नहीं पा रहा हूं। मैं क्या कर सकता है योग से वे इस तरह एक सूत्र का उपयोग किया
(यदि वहाँ दो नंबर एक रहे हैं और ख) तो, a+b = (a XOR b) + (a AND b)*2

कैसे मुझे लगता है कि करने के लिए पहुंचते हैं? बाकी के कदम मेरे लिए अस्पष्ट हैं।

यदि कोई इसे हल करने या उनके समाधान की व्याख्या करने के बारे में कोई विचार प्रदान कर सकता है, तो कृपया मदद करें।

Answer 1

के रूप में वास्तव में क्या हो सकता है जब आप द्विआधारी इसके अलावा कर a+b = (a XOR b) + (a AND b)*2 की Think। अपने उदाहरण, a = 010 और b = 111 से:

010 
111 
--- 
1001 = 101 + 100 

प्रत्येक बिट के लिए, आप a और b (0+0=0, 0+1=1, 1+0=1, 1+1=0 से बिट्स जोड़ने के लिए, जो वास्तव में है a XOR bप्लस कैरी-में थोड़ा पिछले से इसके अलावा, यानी अगर a और b के लिए दोनों पिछले बिट्स 1 हैं, तो हम जोड़ने यह भी। यह ठीक (a AND b)*2 है। (2 से कि गुणा याद रखें एक पारी को छोड़ दिया है।)

उस समीकरण के साथ हम a AND b की गणना कर सकते हैं।

अब आप जिस नंबर को चाहते हैं उसकी गणना करने के लिए, हमऔर a AND b प्रत्येक-एक-एक के प्रत्येक बिट्स को देखते हैं और सभी संभावनाओं को गुणा करते हैं। (मुझे a की i वें बिट के लिए लिखने a[i] चलो)

• तो a[i] XOR b[i] = 0 और a[i] AND b[i] = 0, तो a[i] = b[i] = 0। इस बिट के लिए केवल एक संभावना है।

• यदि a[i] XOR b[i] = 0 और a[i] AND b[i] = 1, तो a[i] = b[i] = 1। इस बिट के लिए केवल एक संभावना है।

• यदि a[i] XOR b[i] = 1 और a[i] AND b[i] = 0, तो a[i] = 1 और b[i] = 0 या इसके विपरीत। दो संभावनाएं

• a[i] XOR b[i] = 1 और a[i] AND b[i] = 1 होना संभव नहीं है।

अपने उदाहरण से

, a XOR b = 101 और a AND b = 010। हमारे पास जवाब 2*1*2 = 4 है।

Answer 2

a AND b दोनों संख्याओं में मौजूद बिट्स हैं। तो ये राशि में दोगुना हो गया है। a XOR b बिट्स हैं जो केवल संख्याओं में से एक में मौजूद हैं, इसलिए इन्हें केवल एक बार योग में गिना जाना चाहिए। अंतिम पंक्ति कैसे बिट दोनों संख्या में है कि (2^2) दो बार गिना जाता है पर

• a = 4 = 1*2^2 + 0*2^1 + 0*2^0 (or just 100)
• b = 13 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 (or just 1101)
• a + b = (1*2^2 + 0*2^1 + 0*2^0) + (1*2^3 + 1*2^2 + 0*2^1 + 1*2^0) = 1*2^3 + 2*2^2 + 0*2^1 + 1*2^0

नोट:

यहाँ एक उदाहरण है योग में जबकि शेष केवल एक बार गिना जाता है!

अपनी समस्या को हल करने के लिए आपको सभी जोड़ों (ए, बी) को खोजने की आवश्यकता है जो योग को जोड़ती हैं। आप क्या करना चाहते हैं यह है:

1. एसयूएम से एक्सओआर मूल्य घटाएं। आपको 2*(a AND b) के साथ छोड़ दिया गया है।
2. 2 से विभाजित करें। अब आपके पास सभी बिट्स हैं जिन्हें ए और बी दोनों में सेट किया जाना चाहिए।
3. आप XOR मूल्य क्या आप जानते हैं कि वास्तव में क्या बिट्स, ए और बी के ठीक एक में सेट किया जाना चाहिए, जबकि और मूल्य तुम सिर्फ गणना बिट्स कि उन दोनों में सेट किया जाना चाहिए रहे हैं के बाद से। तो आप क्रमशः ए या बी में बिट्स सेट करने के सभी क्रमपरिवर्तन सूचीबद्ध करते हैं।

मेरे पिछले उदाहरण के लिए:

• a AND b = 0100 (दोनों हमेशा में सेट)
• a XOR b = 1001

हम इन क्रमपरिवर्तन के रूप में मिलता है (हम इन के सभी क्रमपरिवर्तन प्रयास करने की आवश्यकता) समाधान:

• a = 0100 + 0000 = 0100, b = 0100 + 1001 = 1101 => (4, 13)
• a = 0100 + 0001 = 0101, b = 0100 + 1000 = 1100 => (5, 12)
• a = 0100 + 1000 = 1100, b = 0100 + 0001 = 0101 => (12, 5)
• a = 0100 + 1001 = 1101, b = 0100 + 0000 = 0100 => (13, 4)