Vraag Logisch bewijs van associatief eigendom voor XOR


Ik kwam een ​​gemeenschappelijk probleem met programmeervragen tegen: geef een lijst van niet-ondertekende gehele getallen en zoek het ene integer dat een oneven aantal keren in de lijst voorkomt. Bijvoorbeeld, als de lijst wordt gegeven:

{2,3,5,2,5,5,3}

de oplossing zou het gehele getal 5 zijn, omdat dit 3 keer in de lijst voorkomt, terwijl de andere gehele getallen zelfs een aantal keren voorkomen.

Mijn oorspronkelijke oplossing betrof het instellen van een gesorteerde array en vervolgens het herhalen van de array: voor elk oneven element zou ik het gehele getal toevoegen, terwijl ik voor elk even element zou aftrekken; de eindsom was de oplossing aangezien de andere gehele getallen zouden worden geannuleerd.

Ik ontdekte echter dat er een efficiëntere oplossing bestond door simpelweg een XOR op elk element uit te voeren - je hebt zelfs geen gesorteerde array nodig! Het is te zeggen:

2^3^5^2^5^5^3 = 5

Ik herinner me van een klasse Discrete Structures die ik heb genomen dat de Associate Property van toepassing is op de XOR-bewerking en daarom werkt deze oplossing:

a^a = 0

en:

a^a^a = a

Hoewel ik me herinner dat de Associatieve Property voor XOR werkt, heb ik problemen met het vinden van een logisch bewijs voor deze eigenschap die eigen is aan XOR (de meeste logica-bewijzen op internet lijken meer gericht op de AND- en OR-bewerkingen). Weet iemand waarom de associatieve eigenschap van toepassing is op de XOR-bewerking?

Ik vermoed dat het gaat om een ​​XOR-identiteit die AND en / of OR bevat.


11
2017-11-07 14:02


oorsprong


antwoorden:


De associatieve eigenschap zegt dat (a^b)^c = a^(b^c). Omdat XOR bitsgewijze is (de bits in de nummers worden parallel behandeld), hoeven we slechts XOR voor één bit te beschouwen. Dan kan het bewijs worden geleverd door alle mogelijkheden te onderzoeken:

abc (a^b) (a^b)^c (b^c) a^(b^c)
000   0      0      0      0
001   0      1      1      1
010   1      1      1      1
011   1      0      0      0
100   1      1      0      1
101   1      0      1      0
110   0      0      1      0
111   0      1      0      1

Sinds de derde kolom, (a^b)^c, is identiek aan de vijfde kolom, a^(b^c), de associatieve eigenschap geldt.


8
2017-11-07 14:11



Zo lang als a ^ b == ~a & b | a & ~b, je kunt bewijzen dat:

(a ^ b) ^ c = ~((~a & b) | (a & ~b)) & c | ((~a & b) | (a & ~b)) & ~c

en

a ^ (b ^ c) = a & ~((~b & c) | (b & ~c)) | ~a & ((~b & c) | (b & ~c))

Zijn gelijken.


1
2017-11-07 14:36