XOR

 (chiark.greenend.org.uk)
1 पॉइंट द्वारा GN⁺ 2025-02-19 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • XOR वह ऑपरेशन है जिसमें दो बिट अलग होने पर 1 बनता है, और इसे exclusive OR, not-equals, conditional inversion, तथा mod 2 addition/subtraction को एक ही क्रिया के रूप में समझा जा सकता है
  • पूर्णांकों पर bitwise XOR हर बिट पोज़िशन को स्वतंत्र रूप से प्रोसेस करके बिट-स्तरीय अंतर दिखाता है, carry के बिना binary addition की तरह काम करता है, और commutativity, associativity, 0 identity, तथा self-inverse गुण बनाए रखता है
  • क्रिप्टोग्राफी में यह plaintext और keystream को मिलाने के लिए इस्तेमाल होता है, और पुराने pixel graphics में उसी चित्र को दोबारा ड्रॉ करके मिटाने की तकनीक से memory और CPU पर भार कम किया जाता था
  • अंतर बनाना और फिर उसे निरस्त करना जैसी गणनाओं में XOR के गुण सीधे उपयोग होते हैं, जैसे half-adder identity, bit swap, तीन बार वाला XOR swap, और Nim गेम की winning condition
  • यह sets के symmetric difference, exponent 2 वाले groups, nim-sum, GF(2) पर linear algebra और polynomials तक जुड़ता है, और Hamming code, CRC, AES, GCM, तथा Classic McEliece जैसी error detection/correction और cryptographic तकनीकों से भी संबंधित है

XOR का मूल अर्थ

  • XOR दो input bits और एक output bit वाला एक Boolean operation है, और इसकी truth table 00→0, 01→1, 10→1, 11→0 है
  • “exclusive OR” के रूप में देखें तो यह तब 1 देता है जब दो inputs में से केवल एक true हो, और दोनों true हों तो 0 देता है
  • “not equals” के रूप में देखें तो a XOR b का अर्थ a ≠ b के बराबर है, इसलिए दो Boolean values अलग हों तो यह 1 देता है
  • conditional inversion के रूप में देखें तो a=0 होने पर b वैसा ही रहता है, और a=1 होने पर b उलट जाता है
    • इसी वजह से b को control input मानकर a को उलटने वाली व्याख्या भी संभव है
  • parity के दृष्टिकोण से यह बताता है कि inputs में 1 की संख्या विषम है या नहीं
    • दो bits के मामले में यह a+b mod 2 के बराबर है
    • यह a-b mod 2 के भी बराबर है
    • कई values का XOR करने पर यह पता चलता है कि पूरे input में 1 की संख्या विषम है या सम

XOR के बीजगणितीय गुण

  • XOR commutativity और associativity को संतुष्ट करता है
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • लंबे XOR expression में क्रम और grouping से परिणाम नहीं बदलता
  • 0, XOR का identity element है
    • a XOR 0 = 0 XOR a = a
    • लंबे XOR expression से 0 को हटाया जा सकता है
  • हर value स्वयं अपनी inverse होती है
    • a XOR a = 0
    • वही variable दो बार आए तो दोनों terms को साथ हटाया जा सकता है
    • (a XOR b) XOR b = a की तरह, पहले से मिश्रित value में कोई ज्ञात term एक बार और XOR करके हटाई जा सकती है

पूर्णांकों पर bitwise XOR

  • पूर्णांकों का bitwise XOR दो integers को binary में लेकर हर bit position पर स्वतंत्र रूप से XOR करता है
  • single-bit XOR के गुण integers पर भी वैसे ही लागू होते हैं
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • a XOR 0 = a
    • a XOR a = 0
  • bitwise XOR दो integers के बीच बिट-स्तरीय अंतर बताता है
    • a=b हो तो a XOR b = 0
    • a≠b हो तो कम-से-कम एक bit अलग होगा, इसलिए a XOR b ≠ 0
    • परिणाम में 1 bits उन positions को दिखाते हैं जहाँ दोनों inputs अलग हैं
  • bitwise XOR को conditional bit inverter के रूप में भी देखा जा सकता है
    • control value में जहाँ 1 bits हों, वहीं data bits उलटते हैं
    • ASCII और कुछ बाद की encodings में Latin uppercase और lowercase के बीच केवल एक bit का अंतर होता है, इसलिए character value को 32 से XOR करके case बदला जा सकता है
    • यह नियम सभी Unicode characters पर लागू नहीं होता, और बहुत से characters में case की अवधारणा नहीं होती या वे इस नियम का पालन नहीं करते
  • bitwise XOR carry के बिना binary addition के बराबर है
    • हर bit position पर केवल mod 2 addition होता है और carry अगले bit तक नहीं जाता

क्रिप्टोग्राफी में XOR

  • क्रिप्टोग्राफी में plaintext के समान लंबाई का keystream बनाया जाता है, और plaintext bytes या words को keystream के साथ मिलाकर ciphertext बनाया जाता है
  • इस combining step में सामान्यतः XOR का उपयोग होता है
    • receiver उसी keystream को फिर से XOR करके मूल plaintext वापस पा सकता है
    • sender और receiver दोनों का एक ही operation उपयोग करना थोड़ा सुविधाजनक भी होता है
  • keystream स्वयं बनाने का तरीका अधिक जटिल हो सकता है
    • one-time pad पूरे message के बराबर आकार का वास्तव में random data उपयोग करता है और अभेद्य होता है, लेकिन अधिकांश उद्देश्यों के लिए बहुत अव्यावहारिक है
    • आमतौर पर stream cipher या counter mode में चलने वाला block cipher छोटी key से आवश्यक लंबाई का keystream बनाता है
  • अच्छा keystream होने पर यह confidentiality दे सकता है, लेकिन message tampering का पता लगाने वाली integrity नहीं देता
    • integrity protection एक अलग समस्या है
    • शुरुआती crypto system design में integrity को छोड़ देना एक आम गलती है, और अधिक जटिल encryption schemes में भी गलत परिणाम दे सकता है
  • hardware में addition की तुलना में XOR अधिक सरल है
    • addition में bits के बीच carry propagation चाहिए, इसलिए chip area और time अधिक लगता है
    • XOR में carry नहीं होता, इसलिए custom circuits में यह सस्ता पड़ता है

XOR drawing और pixel graphics

  • 1980 के दशक के home computers में प्रति स्क्रीन pixel bit count और RAM सीमित थी, इसलिए पूरी स्क्रीन की दो प्रतियाँ रखना कठिन था
  • किसी moving object को XOR से ड्रॉ करने पर उसी object को दोबारा ड्रॉ करके मूल स्क्रीन बहाल की जा सकती थी
    • pixel value S और moving object का pixel M XOR करके C बनाया जाता है, और बाद में उसी M को फिर XOR करके S वापस पाया जाता है
  • जिन screens में कई pixels एक byte में packed होते थे या bit plane संरचना होती थी, वहाँ addition-आधारित compositing कठिन थी
    • सामान्य addition में एक pixel का carry अगले pixel तक जा सकता है
    • XOR में बिल्कुल carry नहीं होता, इसलिए यह समस्या नहीं आती
  • XOR से line ड्रॉ करने पर जहाँ दो lines एक-दूसरे को काटती हैं, वहाँ pixel दो बार उलटकर background color पर लौट सकता है और छोटा दोष जैसा दिख सकता है
    • यह दोष इस लाभ के बदले स्वीकार किया जाता था कि एक line मिटाने पर दूसरी line खराब नहीं होती
  • XOR drawing साधारण animation के लिए भी उपयोगी थी
    • नई line ड्रॉ करो और पुरानी line दोबारा ड्रॉ करके मिटा दो, तो अगला frame तैयार हो जाता है
    • स्क्रीन के सभी pixels या सभी lines दोबारा ड्रॉ करने की ज़रूरत नहीं होती, इसलिए memory और CPU का उपयोग कम रहता है
    • 1981 के गेम Qix की moving line और शुरुआती GUI में window moving outlines में यह तकनीक उपयोग हुई थी

half-adder identity

  • one-bit addition में a+b का low bit a XOR b होता है और high bit a AND b होता है
  • यही संबंध integers के bitwise operations पर भी लागू होता है
    • a + b = (a XOR b) + 2 × (a AND b)
    • a XOR b carry के बिना जोड़ा गया मान है, और a AND b हर bit position पर बनने वाले carry bits को रखता है
  • इस संबंध को half-adder identity के रूप में देखा जा सकता है
    • hardware half-adder, AND और XOR gates से दो-bit addition का carry और low bit बनाता है
    • यह पूरी integer addition को केवल simple operations से नहीं बना देता; दाहिने पक्ष का + carry propagation को पूरा करता है
  • overflow के बिना दो integers का average निकालने में इस identity का उपयोग हो सकता है
    • केवल a+b के बाद right shift करने पर 33-bit sum का सबसे ऊपरी bit खो सकता है
    • जिन CPUs में carry flag या RRX/RCR जैसे instructions नहीं हों या असुविधाजनक हों, वहाँ (a XOR b) >> 1 + (a AND b) रूप एक विकल्प हो सकता है
    • उदाहरण के लिए MIPS, RISC-V, और DEC Alpha में carry flag नहीं होता, और शुरुआती Arm Thumb में RRX नहीं था
  • जिन CPUs में XOR instruction न हो, वहाँ इस identity को उलटकर XOR बनाया जा सकता है
    • a XOR b = (a + b) − 2 × (a AND b)
    • 1970 के दशक के Data General CPU में AND था, लेकिन bitwise XOR नहीं था

bits और values का swap

  • दो bits को swap करने की समस्या इस बात तक सिमटती है कि यदि दोनों समान हों तो कुछ न करो, और यदि अलग हों तो दोनों bits उलट दो
  • XOR और shift की मदद से यह पता लगाया जा सकता है कि दो bits अलग हैं या नहीं, और ज़रूरत होने पर दोनों positions को उलटा जा सकता है
    • diff_all = input XOR (input >> distance) से निश्चित दूरी पर स्थित bit-pairs का अंतर निकाला जाता है
    • AND से केवल रुचिकर positions चुने जाते हैं
    • चुने गए अंतर को दूसरी position पर कॉपी करके input से XOR किया जाता है, ताकि केवल आवश्यकता होने पर दोनों bits उलटें
  • समान दूरी पर स्थित कई bit-pairs को एक साथ swap करने में भी यही तरीका इस्तेमाल किया जा सकता है
    • single-bit mask की जगह multi-bit mask का उपयोग होता है
    • Beneš network कई stages में समान दूरी वाले अनेक pairs को swap करके किसी भी permutation को व्यक्त कर सकता है
  • पूरे दो values को swap करने के लिए तीन बार वाला XOR swap भी संभव है
    • a = a XOR b
    • b = b XOR a
    • a = a XOR b
    • बिना temporary variable के भी दोनों values आपस में बदल जाती हैं
  • तीन बार वाले XOR swap में aliasing की समस्या होती है
    • दो अलग variables के बीच यह काम करता है
    • लेकिन यदि दो नाम एक ही storage location की ओर इशारा करें, जैसे array के उसी element को उसी से swap करना, तो value 0 हो सकती है

Nim गेम और XOR

  • Nim कई heaps वाला खेल है जिसमें खिलाड़ी बारी-बारी से एक heap चुनकर उसमें से 1 या अधिक, इच्छानुसार किसी भी संख्या में pieces हटाता है; और जब कोई चाल बाकी न रहे तो हार होती है
  • Nim के सरल संस्करण में हारने वाली स्थिति वह होती है जहाँ सभी heap sizes का bitwise XOR 0 हो
  • XOR 0 होने वाली स्थिति में यदि किसी heap का size a बदलकर b किया जाए, तो कुल XOR a XOR b जितना बदलता है, और a≠b होने से वह 0 नहीं रहेगा
  • XOR 0 न होने वाली स्थिति में कुल XOR x का सबसे ऊँचा 1 bit देखें; जिस heap में वह bit 1 हो, उसे pile XOR x तक घटाने से कुल XOR 0 बनाया जा सकता है
  • उदाहरण के लिए heap sizes 12, 10, 3 की binaries 1100, 1010, 0011 हैं और इनका XOR 0101 है
    • सबसे बड़ा heap 12, 0101 से XOR करने पर 9 बन जाता है
    • इसलिए winning move है 12 से 3 pieces हटाकर उसे 9 करना

XOR जैसी दिखने वाली गणितीय संरचनाएँ

  • set theory में symmetric difference X∆Y वह operation है जिसमें कोई element तभी शामिल होता है जब वह दोनों sets में से ठीक एक में हो
    • element membership को Boolean value मानें तो symmetric difference, XOR के बराबर है
    • इसलिए यह XOR के commutativity और associativity जैसे गुण साझा करता है
  • group theory में exponent 2 group वह group है जिसमें हर element स्वयं अपनी inverse हो
    • ऐसे group का operation associativity को संतुष्ट करता है, और मानक अभ्यास के रूप में यह commutativity भी देता है
    • एक जैसे दो elements साथ हों तो वे निरस्त हो जाते हैं; यह XOR जैसा है
    • हर exponent 2 group को किसी {0,1}-valued functions के bitwise XOR के रूप में समझा जा सकता है
  • Sprague-Grundy analysis में कई impartial games की positions को Grundy number दिया जाता है
    • कई subgames को जोड़कर बने composite की Grundy number, उनके अलग-अलग Grundy numbers के bitwise XOR से निकाली जाती है
    • game theory में nonnegative integers के bitwise XOR को nim-sum भी कहा जाता है
  • field GF(2) एक finite field है जिसके केवल 0 और 1 दो elements होते हैं
    • इसमें addition और subtraction, XOR की तरह काम करते हैं
    • multiplication, AND की तरह काम करता है
    • इसलिए a AND (b XOR c) = (a AND b) XOR (a AND c) सही होता है

GF(2) पर linear algebra और error correction

  • GF(2) पर vectors और matrices ऐसी संरचनाएँ हैं जिनके components 0 या 1 होते हैं, और vector या matrix addition component-wise XOR होती है
  • matrix M को vector v से गुणा करना, v के 1 components द्वारा चुने गए M के columns को XOR से जोड़ने के बराबर है
  • error-correcting code एक m-bit message को लंबा n-bit codeword बनाता है ताकि कुछ bit errors का detection या correction किया जा सके
    • यदि valid codewords एक-दूसरे से बहुत से bits में अलग हों, तो कम संख्या के bit errors किसी codeword को दूसरे valid codeword में नहीं बदलते
    • यदि दो valid codewords कम-से-कम k bits में अलग हों, तो k से कम errors detect किए जा सकते हैं, और k/2 से कम errors nearest codeword खोजकर correct किए जा सकते हैं
  • linear codes, GF(2) पर generator matrix और check matrix का उपयोग करते हैं
    • sender, generator matrix से m-bit message को n-bit codeword में फैलाता है
    • receiver, check matrix से जाँचता है कि प्राप्त codeword valid है या नहीं, और error होने पर syndrome प्राप्त करता है
    • वही error pattern, message से स्वतंत्र रूप से वही syndrome उत्पन्न करता है
  • Hamming code इसका उदाहरण है जहाँ code length n, 2^d−1 होती है
    • n=15 होने पर 15 bit positions को 0001 से 1111 तक के 4-bit nonzero numbers से नंबर दिया जाता है
    • receiver उन सभी indices का XOR करता है जिनकी bits 1 हैं; यदि परिणाम 0 हो तो वह valid codeword है
    • यदि एक bit उलट गई हो, तो XOR का परिणाम सीधे उसी flipped bit का index देता है, इसलिए lookup table के बिना 1-bit error ठीक की जा सकती है
    • 15-bit Hamming code में 11 bits data के लिए और 4 bits error correction के लिए होते हैं

GF(2) polynomials, CRC, और बड़े finite fields

  • GF(2) पर polynomials ऐसे formal polynomials हैं जिनके coefficients 0 या 1 होते हैं, और addition का अर्थ समान degree के coefficients का XOR करना है
  • polynomial multiplication में सामान्य polynomials की तरह partial products बनते हैं, और coefficients को mod 2 में घटाया जाता है
    • bit string के रूप में देखें तो यह integer multiplication जैसा है, लेकिन partial products को जोड़ते समय सामान्य addition के बजाय carry-less XOR उपयोग होता है
    • x86, CLMUL सहित carryless multiplication instructions देता है, और Arm polynomial multiplication family के instructions देता है
  • CRC GF(2) polynomial division के remainder को checksum की तरह उपयोग करता है
    • भेजे गए message bit string को बड़े polynomial M के रूप में देखकर, सहमत polynomial P से भाग देने पर M mod P remainder रखा जाता है
    • यह Ethernet और समान network packet validation में उपयोग होता है
    • CRC errors को correct नहीं करता, केवल detect करता है, और उन स्थितियों के लिए उपयुक्त है जहाँ लगभग सभी transmissions सही हों और कभी-कभी bit flips या noise आए
  • बड़े finite fields, GF(p) पर polynomials को irreducible polynomial Q से mod करने पर मिलने वाली remainder संरचना से बनाए जा सकते हैं
    • यदि Q की degree d हो, तो नया finite field p^d elements रखता है
    • p=2 होने पर irreducible polynomials को bit patterns के रूप में integers की तरह लिखा जा सकता है, और ऐसी sequence OEIS A014580 में दर्ज है
  • 2 की power आकार वाले finite fields कई cryptographic techniques में आते हैं
    • 2^8 आकार का finite field, AES और Twofish का मुख्य building block है
    • 2^128 आकार का finite field, bulk encryption और integrity protection को जोड़ने वाले GCM में उपयोग होता है
    • 2 की power आकार वाले finite fields कुछ elliptic-curve cryptography और post-quantum scheme Classic McEliece के decoding algorithms में भी आते हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-02-19
Hacker News की राय

  • मेरी पसंदीदा cursed XOR तकनीक XOR doubly linked list है: https://en.m.wikipedia.org/wiki/XOR_linked_list
    हर node में next/previous pointers अलग-अलग store करने के बजाय, दोनों का XOR किया हुआ एक ही value store किया जाता है। जाहिर है यह valid pointer नहीं होता, लेकिन traverse करते समय previous node pointer और combined pointer को XOR करने पर next node pointer मिल जाता है, और दोनों दिशाओं में traversal भी संभव होता है। कुछ illegal-सा लगता है

    • सामान्य doubly linked list की तुलना में, जब आपके पास सिर्फ item का address हो या insertion/deletion के दौरान stable रहने वाला iterator ही हो, तो उस item को हटाने की क्षमता खो जाती है। जबकि अक्सर doubly linked list इस्तेमाल करने की यही मुख्य वजह होती है
      एक कम मूलभूत कमी यह है कि standard को सख्ती से follow करने वाले C में XOR linked list लिखना बेहद झंझट भरा है। standard यह guarantee नहीं देता कि same pointer को integer में cast करने पर same integer मिलेगा, इसलिए practically normalized integer-cast version बनाए रखने के लिए सब कुछ uintptr_t बनाना पड़ता है
    • 64-bit processors पर भी अगर मान लें कि ज़्यादातर apps के लिए 4GB से कम RAM काफी है, तो सिर्फ 32-bit address space से storage और घटाया जा सकता है
      आगे जाकर 16-bit near/relative pointers भी संभव हो सकते हैं। यह data-oriented design के साथ अच्छी तरह fit हो सकता है, जैसे 64K elements का block रखकर अंदर के elements को uint16 index से point करना
    • ऐसा करने पर garbage collector इसे पसंद नहीं करेगा। या कम से कम इस data structure को garbage मान लेगा
    • उत्सुकता है कि कोई यह तकनीक क्यों इस्तेमाल करना चाहेगा
    • यह pointer से ज्यादा दो pointers के difference को store करने जैसा ही है। difference store करने पर भी जाहिर तौर पर bidirectional traversal संभव है

  • एक चीज़ छूट गई है। XOR एक 3-wise independent linear hash function भी है, इसलिए इसे boolean function solutions की probabilistic approximate uniform sampling और counting में इस्तेमाल किया जा सकता है। यह वाकई उपयोगी है, और probabilistic लेकिन proven count देने वाले counter बनाने में इस्तेमाल होता है। इसे समझने में आसान explanation मैंने यहां लिखी है https://www.msoos.org/2018/12/how-approximate-model-counting...
    मूल रूप से यह हर बार solution space को लगभग ठीक आधा कर देता है। इसलिए XOR conditions जोड़ते जाते हैं और मान लें जब 10 solutions बचते हैं, तो जोड़े गए XOR की संख्या k हो तो 10 को 2^k से multiply कर दें। हर बार आधा होने से 10 के स्तर तक जल्दी पहुंच जाते हैं, इसलिए scalability अच्छी है
    संबंधित papers https://arxiv.org/abs/1306.5726 और https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf पर हैं, और tools https://github.com/meelgroup/approxmc और https://github.com/meelgroup/unigen पर हैं। पिछले model counting competition में, exact counter के साथ combine किए जाने पर इसने बाकी competitors को बहुत पीछे छोड़ दिया था, और slides https://mccompetition.org/assets/files/2024/MC2024_awards.pd... पर हैं

  • मेरी पसंदीदा XOR anecdotes में से एक Oxide, Joyent, Sun के Bryan Cantrill की यह कहानी है, जो उन्होंने इस presentation https://speakerdeck.com/bcantrill/oral-tradition-in-software... और इस video https://www.youtube.com/watch?v=4PaWFYm0kEw में सुनाई थी
    लिंक न खोलना चाहें तो सार यह है: Sun में रहते हुए उन्होंने अपने colleague Roger Faulkner से बात की कि C में logical XOR क्यों नहीं है। Faulkner ने कहा कि क्योंकि उसमें short-circuit evaluation नहीं हो सकता, और Brian को यह अजीब लगा। फिर Roger ने Dennis Ritchie को email करके पूछा, और Ritchie ने confirm किया कि Faulkner सही हैं। Cantrill की delivery भी मजेदार है, लेकिन यह बात चौंकाने वाली है कि वे सीधे संबंधित व्यक्ति से पूछ सकते थे

    • DMR आश्चर्यजनक रूप से दयालु, मददगार और approachable व्यक्ति थे। 80s के मध्य में undergraduate रहते हुए मैंने PDP-11 के बजाय Interdata 8/32 पर Unix v6 port करने के “पहले” मामले के बारे में पढ़ा, और architecture के बारे में और जानकारी है क्या यह पूछते हुए dmr@research.att.com पर सीधे email भेज दिया
      उस समय Google नहीं था और university library में भी material नहीं था, लेकिन कुछ दिनों बाद उन्होंने physical address पूछा और कुछ हफ्तों बाद instruction set summary manual की एक copy मेरे mailbox में आ गई। वह IBM 360 family जैसा लगता था और वह अब भी मेरे पास है
    • C में logical XOR है, और वह सीधे != operator है। दूसरे logical operators के विपरीत, इसे arguments को single truth value में normalize करना पड़ता है, और यह C के boolean conversion idiom !! के साथ अच्छी तरह fit बैठता है
    • “क्योंकि short-circuit evaluation नहीं हो सकता” यह operator जोड़ने में बाधा क्यों है, समझ नहीं आता। काश कोई समझा दे
    • संबंधित विषय 37:18 से शुरू होता है
    • C में 40 साल से ज्यादा समय से bitwise XOR operator ^ मौजूद है: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

  • आज पता चला कि अगर automobile emoji को 0x20 के साथ XOR करें, यानी उसे “lowercase” करें, तो वह no pedestrians emoji बन जाता है। संयोग के हिसाब से यह कुछ ज़्यादा ही सटीक लगता है; जानना चाहूंगा कि क्या किसी को पता है कि यह जानबूझकर किया गया था या नहीं
    अगर बात को बहुत आगे बढ़ाएँ, तो यह अजीब विचार भी बन सकता है कि automobile emoji का lowercase ‘no pedestrians’ sign है

    • HN के emoji हटाने वाले comment handler से बचना हो, तो इसे ऐसे verify कर सकते हैं:
      >>> from unicodedata import lookup, name
      >>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
      'NO PEDESTRIANS'
    • automobile का lowercase शायद go-kart होना चाहिए
    • :tada: → :tophat:, :rocket: → :mountain_cableway: भी संभव है

  • XOR समझाने के लिए एक अच्छा real-world analogy घर की सीढ़ियों पर लगा light switch है। नीचे एक switch, ऊपर एक switch होता है, और दोनों एक ही light को control करते हैं
    शुरुआत में दोनों off position में होते हैं; नीचे वाला switch on करने पर light जलती है। सीढ़ियाँ चढ़कर ऊपर वाला switch on करने पर, दोनों switches “on” position में होने के बावजूद light बंद हो जाती है। सिर्फ जब एक switch “on” और दूसरा “off” हो तभी light जलती है; बाकी cases में बंद रहती है

    • शायद हमारे office के electrician ने wiring गलत की हो। कमरे में दो switches हैं, और सोचने पर वे XOR से ज़्यादा AND gate की तरह काम करते हैं। living room के दो switches पक्का XOR की तरह काम करते हैं

  • इस logic function के लिए आम तौर पर XOR, यानी “exclusive OR” नाम इस्तेमाल होना मुझे बिल्कुल पसंद नहीं है। वजह यह है कि लगभग हमेशा उसका असली मतलब “sum modulo 2”, यानी parity होता है, exclusive OR नहीं
    “sum modulo 2”/parity और “exclusive OR” अलग-अलग logic functions हैं, और सिर्फ 2 input operands होने पर ही संयोग से समान निकलते हैं। क्योंकि 2 या उससे कम में केवल एक ही odd number होता है
    जब inputs 3 या अधिक हों, तो जिसे ज़्यादातर लोग XOR कहते हैं, वह असल में parity है, जो odd number of inputs के 1 होने पर 1 बनता है। इसके उलट exclusive OR वह function है जो 3 या अधिक inputs होने पर तभी 1 बनता है जब ठीक एक ही input 1 हो और बाकी सभी 0 हों
    computer hardware में parity, exclusive OR से कहीं ज़्यादा important है। मुख्य कारण यह है कि modulo-2 addition बड़े numbers के addition implementation के building block के रूप में इस्तेमाल होता है। उल्टा, mathematics में exclusive OR, parity से कहीं ज़्यादा important है
    उदाहरण के लिए, कोई predicate किसी set के कुछ elements, सभी elements, या unique element के लिए true है—यह बताने वाले quantifiers क्रमशः OR, AND, और exclusive OR पर आधारित होते हैं। natural language का “or” हमेशा inclusive OR या exclusive OR का अर्थ देता है, वह parity नहीं जिसे कई programmers XOR कहते हैं
    programming में exclusive OR logic function compute करने की ज़रूरत कम पड़ती है, लेकिन program behavior समझाने में इसका इस्तेमाल अक्सर होता है। जैसे select/case/switch compound statement में पहला या दूसरा या तीसरा statement में से कोई एक execute होता है, या union/sum type variable के current value के possible types समझाते समय

    • electrical technology symbols standard IEC 60617 इस हिस्से को ठीक से handle करता है। XOR gate को =1, और parity gate को 2k + 1 से दिखाता है। लेकिन PCB या FPGA के लिए circuit design software इस्तेमाल करते समय आपको expected से अलग चीज़ मिल सकती है और आप फिर भी फँस सकते हैं
    • mathematics में जिस चीज़ की बात की गई है उसे unique existential quantification कहते हैं, और उसका अपना symbol ∃! है
    • 3 या अधिक inputs होने पर “exclusive OR” ठीक एक ही 1 होने पर true होता है—इस व्याख्या के लिए आधार चाहिए
    • यह interpretation main essay में भी discuss की गई है

  • Kademlia distributed hash table भी है: kademlia distributed hash table. बड़ा idea यह है कि हर node को [0, 2^m) range के random bits मिलते हैं, और distance को XOR से define किया जाता है। मकसद ऐसा distributed algorithm ढूँढना है जो पूरी network जानकारी के बिना X से Y तक information जल्दी भेज सके
    सिर्फ mathematics देखकर भी इसका काम करना prove किया जा सकता है, लेकिन मेरी पसंदीदा visual intuition यह है। मान लें starting node X, node k को ढूँढना चाहता है। “X-distance tree” को एक binary tree के रूप में define करें जिसके leaf indices 0, 1, 2... हैं, और हर leaf पर X से distance दिखाने के लिए X^leaf_index label लगाया गया है। उदाहरण के लिए dist(x, x) = x^x = 0, इसलिए original node X label सबसे बाएँ leaf 0 पर रखा जाता है
    interval [2^i, 2^(i+1)), X-distance tree का कोई subtree है। अगर पता है कि k की distance उस interval में आती है, तो उसके अंदर किसी node Y को approximate neighbor के तौर पर query करते हैं
    चाहे कोई भी Y चुनें, Y-distance tree में result prefix हमेशा X-distance tree में चुने गए [2^i, 2^(i+1)) subtree का कोई permutation बनता है। और ठीक कहें तो labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)) के रूप में देखा जा सकता है। indices distance के आधार पर होते हैं, लेकिन labels बदल सकते हैं
    Chord जैसे दूसरे distributed hash tables से comparison पर mathematically और empirically कहीं ज़्यादा rigorous material मौजूद है। लेकिन यह visual intuition Kademlia की “symmetry” क्या है, और यह एहसास देती है कि हर किसी के अपने local neighbors और अपना subtree होता है
    दूसरी तरफ Chord को bidirectional implement करें तो भी memory 2x लगती है, implementation भी ज़्यादा risky लगती है, और इस level की “isolation” पाना मुश्किल है। size S की neighbor sliding window हमेशा move करती रहती है, और हर bit के लिए 2^m अलग-अलग neighbors मौजूद होते हैं। ज़्यादातर neighbors similar दिखें तो भी यह साफ-सुथरा नहीं है
    Kademlia में 1 + 2 + 4 ... + 2^m-1 neighbors होते हैं, और पूरी चीज़ व्यवस्थित है

  • जिन लोगों को जिज्ञासा हो, उनके लिए: यह व्यक्ति Simon Tatham's Portable Puzzle Collection वाले वही Simon Tatham हैं। अगर आप नहीं जानते, तो offline खाली समय में try करने लायक है
    high school में मैंने इन्हें करते हुए काफी समय खर्च किया था: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

    • और ये PuTTY बनाने वाले वही Simon Tatham भी हैं: https://www.chiark.greenend.org.uk/~sgtatham/putty/
    • सबसे अच्छी बात यह है कि minesweeper algorithm ऐसे games बनाता है जिनमें guessing की ज़रूरत नहीं होती

  • आजकल कई custom optimization solvers, जैसे Ising Machine, XOR समस्याओं पर benchmark किए जाते हैं। असल में, कई XOR clauses को हल करना Gaussian elimination से polynomial time में संभव है, इसलिए इसकी उपयोगिता थोड़ी कम हो जाती है, लेकिन चूँकि सभी solvers में exponential scaling दिखती है, इसलिए performance का अंदाज़ा लगाने का यह अच्छा तरीका बन जाता है
    दूसरा दिलचस्प implementation McEliece cryptosystem से जुड़ा है। यह 70 के दशक का public-key cryptosystem है, जो आजकल quantum resistance की वजह से फिर ध्यान खींच रहा है। Decryption attack, XOR equations के set का solution खोजने की समस्या है; यह भी polynomial time में है, लेकिन इसमें यह शर्त जुड़ जाती है कि Hamming distance public key में शामिल किसी संख्या के बराबर होना चाहिए

  • TI-83 programming करने के लिए Z80 assembly सीखते समय machine code का हर 1 byte मायने रखता था। वजह यह थी कि calculator की कुल storage space सिर्फ 24KB थी
    main accumulator register a को 0 से initialize करने के लिए LD a, 0 की जगह XOR a इस्तेमाल किया जाता था। math instructions में a automatic operand होता है, इसलिए XOR a, a को उसी के साथ XOR करता है, और पूरी instruction सिर्फ 1 byte की होती है। इसके उलट 0 को explicitly a में load करने के लिए literal 0 को opcode में शामिल करना पड़ता है, इसलिए LD a, 0 2-byte instruction है