एक्स एक्सओआर (x/2) का रिवर्स फ़ंक्शन क्या है?

Question

x XOR (x/2) का रिवर्स फ़ंक्शन क्या है?

क्या बीजगणित के समान समीकरण हल करने के लिए नियमों की एक प्रणाली है, लेकिन तर्क ऑपरेटरों के साथ?

Answer 1

मान लें कि हमारे पास एन बिट्स की संख्या x है। आप लिख सकते हैं इस रूप में:

b(N-1) b(N-2) b(N-3) ... b(0) 

जहां b(i) संख्या में बिट संख्या i (जहां 0 कम से कम महत्वपूर्ण बिट है)।

x/2x जैसा ही बाएं 1 बिट के समान है। आइए हस्ताक्षरित संख्या मान लें। तो:

x/2 = 0 b(N-1) b(N-2) ... b(1) 

अब हम xx/2 साथ XOR:

x^(x/2) = b(N-1)^0 b(N-2)^b(N-1) b(N-3)^b(N-2) ... b(0)^b(1) 

ध्यान दें कि यह की सबसे दायीं ओर का सा (सबसे महत्वपूर्ण बिट) b(N-1)^0 जो b(N-1) है। दूसरे शब्दों में, आप तुरंत परिणाम से b(N-1) प्राप्त कर सकते हैं। जब आपके पास यह बिट हो, तो आप b(N-2) की गणना कर सकते हैं क्योंकि परिणाम का दूसरा बिट b(N-2)^b(N-1) है और आप पहले से ही b(N-1) जानते हैं। और इसी तरह, आप मूल संख्या x की सभी बिट्स b(N-1)b(0) पर गणना कर सकते हैं।

Answer 2

मैं तुम्हें बिट्स में एक एल्गोरिथ्म दे सकते हैं:

मान लिया जाये कि आप n बिट्स की एक सरणी है:

b = [b1 .. bn] // b1-bn are 0 or 1 

मूल सरणी है:

x0 = b0 
x1 = b1^x0 
x2 = b2^x1 

या सामान्य

में

x[i] = b[i]^x[i-1] 

Answer 3

Assum ई वाई = एक्स^(एक्स/2)

यदि आप एक्स खोजना चाहते हैं, इस

X = 0 

do 

    X ^= Y 
    Y /= 2 

while Y != 0 

मुझे आशा है कि यह मदद करता है है!

Answer 4

मुझे पता है कि यह एक पुराना विषय है, लेकिन मैं एक ही प्रश्न पर ठोकर खाई, और मुझे एक छोटी सी चाल मिली। आप n बिट्स, बजाय n बिट्स संचालन, आप log2 (एन) संख्या कार्यों के साथ यह कर सकते हैं (जेस्पर से जवाब की तरह) की आवश्यकता होती है की है, तो:

मान लीजिए है कि y कार्यक्रम की शुरुआत में एक्स XOR (एक्स/2) के बराबर है, तो आपको निम्न सी कार्यक्रम कर सकते हैं:

INPUT : y 

int i, x; 
x = y; 
for (i = 1; i < n; i <<= 1) 
    x ^= x >> i; 

OUTPUT : x 

और यहां आप समाधान है।

• ">>" सही बिट शिफ्ट ऑपरेशन है। उदाहरण के लिए बाइनरी में नंबर 13, 1101, यदि दाईं ओर 1 से स्थानांतरित किया गया है, तो बाइनरी में 110 हो जाएगा, इस प्रकार 13 >> 1 = 6. x >> मैं x/2^i के बराबर है (पूर्णांक में विभाजन, जाहिर है)
• "< <" छोड़ बिट पारी ऑपरेशन है (मैं < < = 1 2)

यह क्यों काम करता है मैं के बराबर * = है?

• initialisation:
: चलो उदाहरण के रूप में एन = 5 बिट्स लेते हैं, और साथ y = बी 4 बी 3 बी 2 बी 1 B0 (में निम्नलिखित एक्स बाइनरी में लिखा है भी, लेकिन मैं दशमलव में लिखा है बाइनरी में) शुरू करते हैं

एक्स = बी 4 बी 3 बी 2 बी 1 B0

• प्रथम चरण: i = 1

एक्स >> 1 = बी 4 बी 3 बी 2 बी 1 इसलिए हमारे पास एक्स = बी 4 बी 3 बी 2 बी 1 B0 XOR बी 3 बी 2 बी 1 B0 = बी 4 (बी 3^बी 4) (बी 2^बी 3) (बी 1^बी 2) (B0^बी 1)

• दूसरा कदम: i = 2

एक्स >> 2 = बी 4 (बी 3^बी 4) (बी 2^बी 3) तो हमारे पास x = b4 (b3^b4) (बी 2^बी 3) (बी 1^बी 2) (बी 0^बी 1) एक्सओआर बी 4 (बी 3^बी 4) (बी 2^बी 3) = बी 4 (बी 3^बी 4) (बी 2^बी 3^बी 4) (बी 1^बी 2^बी 3^बी 4) (B0^बी 1^बी 2^बी 3)

• तीसरा कदम: मैं = 4

x >> 4 = बी 4 इसलिए हमारे पास x = b4 (b3^b4) (बी 2^बी 3^बी 4) (बी 1^बी 2^बी 3^बी 4) (बी 0^बी 1^बी 2^बी 3) एक्सओआर बी 4 = बी 4 (बी 3^बी 4) (बी 2 बी 3^^ बी 4) (बी 1^बी 2 बी 3^^ बी 4) (B0^बी 1^बी 2 बी 3^^ बी 4)

• तो मैं = 8, जो अधिक से अधिक 5 है, हम बाहर निकलने के पाश।

और हमारे पास वांछित आउटपुट है।

लूप में लॉग 2 (एन) पुनरावृत्ति है क्योंकि मैं 1 से शुरू होता हूं और प्रत्येक चरण में 2 से गुणा किया जाता है, इसलिए मैं एन तक पहुंचने के लिए, हमें इसे लॉग 2 (एन) बार करना पड़ता है।