Nem látom át hogy a xor al két szám felcserélése miért működik, elmagyarázod?

- true = 1, false = 0

- írj le 2 számot binárisan

- XOR-ozd össze őket (bitenként ugye)

A=110101

B=101101

C = A XOR B = 011000

A XOR C = 101101 = B

B XOR C = 110101 = A

Két szám bináris alakjának XOR-olása megad egy olyan bináris számot, ami a két szám közti eltéréseket tartalmazza. (ugye a XOR kizárólag ott lesz 1, ahol az egyik 1, a másik 0)

Éppezért ha az eredményt össze XOR-olod bármelyik számmal, megkapod a másik számot. Miért?

- Ha egy adott biten a két szám értéke megegyezik, ott a XOR 0 lesz. Ha pedig a XOR 0, akkor vagy 1 XOR 0 vagy 0 XOR 0 lesz az adott biten, tehát ugyanazt kapod vissza, ami volt (A XOR 0-nál 'békénahgyja' a számot)

- Ha egy adott biten VOLT eltérés, ott a XOR értéke 1. Ezesetben szintén lehet 0 XOR 1 vagy 1 XOR 1. 0

Tök jó, hogy idő előtt kitörölte... akkor újra.

A=110101

B=101101

C = A XOR B = 011000

A XOR C = 101101 = B

B XOR C = 110101 = A

Két szám bináris alakjának XOR-olása megad egy olyan bináris számot, ami a két szám közti eltéréseket tartalmazza. (ugye a XOR kizárólag ott lesz 1, ahol az egyik 1, a másik 0)

Éppezért ha az eredményt össze XOR-olod bármelyik számmal, megkapod a másik számot. Miért?

- Ha egy adott biten a két szám értéke megegyezik, ott a XOR 0 lesz. Ha pedig a XOR 0, akkor vagy 1 XOR 0 vagy 0 XOR 0 lesz az adott biten, tehát ugyanazt kapod vissza, ami volt (A XOR 0-nál 'békénahgyja' a számot)

- Ha egy adott biten VOLT eltérés, ott a XOR értéke 1. Ezesetben szintén lehet 0 XOR 1 vagy 1 XOR 1.

0 XOR 1 = 1, és 1 XOR 1 = 0. Látod, pont az ellentétes értéket kapod ekkor meg, mint ami az eredeti számban volt.

Tehát: Ahol egyezőség volt, ott a XOR-olt érték (C) 0, és a vissza XOR-olás során változatlan marad, ahol pedig volt eltérés, ott a XOR-olt érték 1, és ott átfordul a másik értékre. Így megkapod az egyik számból a másikat.

Kicsit kapkodva írtam, szóval megértem, ha nem teljesen jött át :D

Amúgy a dologra ne úgy gondolj, mint kivonásra, mert nem egészen az.

Tehát, A XOR B = C, és azt mondom, hogy a C-ben ott lesz 0, ahol a és B értékei megegyeznek, és ott lesz 1, ahol eltérnek. Miért? Vegyük végig, hogy az XOR hol milyen értéket generál:

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

Az XOR alapvetően a szigorú VAGY művelet, tehát ott ad 1-et, ahol pontosan az egyik érték 1. Amolyan "vagy-vagy" alapú. Viszont ez azt is eredményezi, hogy mint fent is látható, az XOR ott ad 0-t eredményül, ahol a két érték egyenlő, és ott ad 1-et, ahol különbözik. Éppezért az A XOR B eredménye is azokon a biteken lesz 0, ahol A és B megegyeznek, és ott lesz 1, ahol eltérnek.

Példa:

A= 110101

B= 101100

A XOR B =

110101 XOR

101100

______

011001

Legyen ez a C értéke. Látható, hogy amelyik biten C értéke 1, ott az A és a B számokban eltérő érték van. Az egyik 0, a másik 1. Eddig oké? Namost, a másik kérdés, hogy miért lesz A XOR C = B illetve B XOR C = A ezek után. Mint mondtam, a C értéke pont ott 1, ahol eltérés van. Éppezért, ha mondjuk A XOR C-t nézem, akkor a következő történhet:

Ha C értéke 1 (baloldalon az A-ból vett érték, jobboldalt a C-ből):

0 XOR 1 = 1

1 XOR 1 = 0

Látható, hogy az 1-el való XOR-olás mindig ellentétes eredményt fog adni, mint a másik érték. És mivel ott, ahol C értéke 1, ott A értéke nem egyezik B-vel, a XOR hatására átfordul az értéke, és a művelet után ezekben a pontokban A értéke meg fog egyezni B-ével.

Másik eset, ahol C-ben 0 van:

0 XOR 0 = 0

1 XOR 0 = 1

Itt meg látható, hogy a 0-val való XOR-olás után megmaradt ugyanaz az érték, ami a baloldalon volt (azaz A-ban). Mivel ott, ahol C értéke 0, ott A és B értéke megegyeznek, és a C-vel való XOR-olás után nem változik ez az érték, ezért ezekben a pontokban továbbra is egyezni fog A és B.

Tehát végül arra jutottunk, hogy ahol C-ben 1 van, ott is A felvette a B-ben levő értéket, és ahol C-ben 0 van, ott is.

A= 110101

B= 101100

C= 011001

A XOR C =

110101 XOR

011001

______

101100 = B

B XOR C =

101100 XOR

011001

______

110101 = A

Más irányból megközelítve:

Mivel a XOR akkor 0 ha a két bit azonos és akkor 1 ha a két bit különbözik, ha valamit össze XORolsz önmagával 0 lesz:

A XOR A = 0

Azért lesz 0 mert "A" minden bitje azonos önmagával. (ezt a tulajdonságot használja ki a CPU a regiszterek kinullázásához)

A következő tulajdonság is fontos:

0 XOR A = A

Ezt egyszerű belátni, mert

0 XOR 1 = 1

és

0 XOR 0 = 0

(ezt te is leírtad a kérdésedben)

Innentől kezdve igaz hogy:

A XOR A XOR B = 0 XOR B = B

Más szavakkal ha valamit kétszer XORzol be egy kértékkel az "kiüti" önmagát és megmarad az eredeti szám. Fentebb az A "kiütötte" önmagát és megmaradt a B.

Az egyszerűbb titkosítási algoritmusok is így működnek: valamilyen "titkos kulcsot" alkalmazol egy értéken XOR művelettel, azt csak az tudja visszaállítani akinek megvan a "titkos kulcs" és újra alkalmazza vele a XOR műveletet az elkódolt értéken, így visszakapva az eredetit:

érték XOR kulcs = titok -> titok XOR kulcs = érték

hiszen ha a titokba behelyettesítesz, ezt kapod: "érték XOR kulcs XOR kulcs = érték"

ami igaz.

Most vissza az értékcseréhez:

(1) A := A XOR B

(2) B := A XOR B

(3) A := A XOR B

Játsszuk le lépésenként:

1. lépés után az A egyenlő lesz (A XOR B)-vel,

2. lépés után a B egyenlő lesz [(A XOR B) XOR B]-vel ahol a B-k kiütik egymást és ez marad:

B = A

3. lépés után az A egyenlő lesz [(A XOR B) XOR A] ahol az A-k fogják kiütni egymást és az "eredeti" B marad meg:

A = B

Közelítsük meg logikai oldalról:

Pár alapvető dolog, ami kell hozzá:

Mi az a xor (jelöljük x -el most): kizáró vagy, azaz értéke akkor igaz, hogy a két operandus értéke különböző, azaz az egyik igaz, a másik hamis. Ha a két érték megegyik, akkor hamis lesz, azaz:

A x A = hamis

A x B = igaz, ha A nem egyenlő B

és még fontos szabály, ami ebből következő:

hamis x A = A, hiszen ha A igaz, akkor (hamis x igaz) = igaz, ha hamis, akkor (hamis x hamis) = hamis

Ebből következnek a következő szabályok: (xor-t jelöljük X-el)

Kommutatív: A x B = B x A azaz a sorrend nem számít

Asszociatív: A x (B x C) = (A x B) x C azaz átzárójelezhető sőt, a zárójel így el is hagyható, hiszen az (AXB)XC műveletet ebben a sorrendben kell elvégezni: AXBXC ==> ezt végig próbálhatod minden esetre, mindig így lesz. Ezeket felhasználva csináljuk:

Na most van a két szám (érték): A és B

1. lépés: a jobb oldalihoz hozzá xor-oljuk a bal oldalit, ekkor lesz:

A és B x A

2. lépés: a bal oldalhoz hozzá xor-oljuk azt, mi most a jobb oldalon van.

ekkor: A x (B x A) és B x A

3. lépés: a jobb oldalhoz hozzá xor-oljuk azt, ami most a bal oldalon van

ekkor: A x (B x A) és B x A x (A x (B x A))

És már meg is cseréltük...

Hogy miért?

Nézzük a jobb oldalt:

Tudjuk, hogy a zárójel elhagyható, a sorrend felcserélhető, ez alapján:

A x (B x A) = A x A x B

Most az AXA = hamis szabály alapján:

A x A x B = hamis x B

A hamis x A = A alapján:

hamis x B = B

Tehát a bal oldali értéket beláttuk, hogy B-vé változott, nézzük a jobb oldalit:

A zárójel elhagyható, felcserélhető, tehát:

B x A x (A x (B x A)) = A x A x A x B x B

mivel A x A = hamis és B x B = hamis, ezért:

A x A x A x B x B = hamis x A x hamis

ez átrendezve:

hamis x A x hamis = hamis x hamis x A

és itt azért, mert két azonos xor-olása az hamis:

hamis x hamis x A = hamis X A

és mivel hamis X = A, ezért itt pedig A marad