๋นํธ XOR ๊ณ์ฐ๊ธฐ๋?
๋นํธ XOR(๋ฐฐํ์ ๋ ผ๋ฆฌํฉ) ๊ณ์ฐ๊ธฐ๋ ๋ ์ ์๋ฅผ ๋ฐ์ ๋นํธ ๋จ์๋ก ๊ฒฐํฉํฉ๋๋ค. ๊ฐ ์๋ฆฟ์์์ ๋ ์ ๋ ฅ ๋นํธ๊ฐ ์๋ก ๋ค๋ฅด๋ฉด ๊ฒฐ๊ณผ ๋นํธ๋ 1์ด ๋๊ณ , ๋ ๋นํธ๊ฐ ๊ฐ์ผ๋ฉด 0์ด ๋ฉ๋๋ค. XOR์ ํ๋ก๊ทธ๋๋ฐ, ๋์งํธ ๋ ผ๋ฆฌ ํ๋ก, ์ํธํ, ์ค๋ฅ ๊ฒ์ถ์์ ์ฐ์ด๋ ๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ธ ์ฐ์ฐ ์ค ํ๋์ ๋๋ค.
์ฌ์ฉ ๋ฐฉ๋ฒ
์ฒซ ๋ฒ์งธ ์ ์(A)์ ๋ ๋ฒ์งธ ์ ์(B)๋ฅผ ์ ๋ ฅํ ๋ค ์คํ ๋ฒํผ์ ๋๋ฅด์ธ์. ๊ณ์ฐ๊ธฐ๋ XOR ๊ฒฐ๊ณผ๋ฅผ 10์ง์๋ก ๋ณด์ฌ์ฃผ๊ณ , ๋นํธ ๋จ์๋ก ์ง์ ํ์ธํ ์ ์๋๋ก 2์ง์์ 16์ง์ ํํ๋ ํจ๊ป ์ ๊ณตํฉ๋๋ค. ์์ ์ ์์ ์์ ์ ์ ๋ชจ๋ ์ ๋ ฅํ ์ ์์ต๋๋ค.
๊ณต์ ์ค๋ช
XOR์ ๋๋ถ๋ถ์ ํ๋ก๊ทธ๋๋ฐ ์ธ์ด์์ A ^ B๋ก, ์ํ ํ๊ธฐ๋ฒ์์๋ A โ B๋ก ํ๊ธฐํฉ๋๋ค.
ํ ๋นํธ์ ๋ํ ์ง๋ฆฌํ๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค: \(0\oplus0=0\), \(0\oplus1=1\), \(1\oplus0=1\), \(1\oplus1=0\). ์ด ์ฐ์ฐ์ ๋ชจ๋ ๋นํธ ์์ ๋
๋ฆฝ์ ์ผ๋ก ์ ์ฉ๋ฉ๋๋ค. ์ ์ฉํ ์ฑ์ง๋ก A ^ A = 0๊ณผ A ^ 0 = A๊ฐ ์๋๋ฐ, ๋ฐ๋ก ์ด ๋๋ฌธ์ XOR์ด ๊ฐ ๊ตํ(swap)์ด๋ ํ๋๊ทธ ํ ๊ธ์ ํ์ฉ๋ฉ๋๋ค.
์์ ๋ก ํ์ด๋ณด๊ธฐ
A = 12, B = 10์ด๋ผ๊ณ ํด๋ด
์๋ค. 2์ง์๋ก ๋ํ๋ด๋ฉด 12 = 1100, 10 = 1010์
๋๋ค. ๊ฐ ์๋ฆฟ์๋ฅผ ๋น๊ตํ๋ฉด \(1\oplus1=0\), \(1\oplus0=1\), \(0\oplus1=1\), \(0\oplus0=0\) ์ด ๋์ด 0110 = 6 ์
๋๋ค. ๋ฐ๋ผ์
์ ๋๋ค.
๋นํธ ์ฐ์ฐ ๋น๊ต
๋ชจ๋ ๋นํธ ์ฐ์ฐ์ ํ ๋ฒ์ ํ ๋นํธ์ฉ ์๋ํฉ๋๋ค. ์ ๋ ฅ ๋นํธ \(A\)์ \(B\)์ ๊ฐ ์์ ๋ํด ์ฐ์ฐ์ ๋จ์ผ ์ถ๋ ฅ ๋นํธ๋ฅผ ์์ฑํฉ๋๋ค. ์๋ ํ๋ ๊ฐ์ฅ ์ผ๋ฐ์ ์ธ 6๊ฐ์ง ์ฐ์ฐ์ ์์ ํ ๋จ์ผ ๋นํธ ์ง๋ฆฌํ๋ฅผ ๋ณด์ฌ์ค๋๋ค. XOR(๋ฐฐํ์ OR, \(A \oplus B\)๋ก ํ๊ธฐ)์ ๋ ์ ๋ ฅ ๋นํธ๊ฐ ๋ค๋ฅผ ๋๋ง 1์ ์ถ๋ ฅํฉ๋๋ค.
| A | B | AND (A&B) | OR (A|B) | XOR (A^B) | NAND ~(A&B) | NOR ~(A|B) | XNOR ~(A^B) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
XOR์ XNOR์ ์ ํํ ์ฌ์งํฉ์ด๋ฉฐ, XOR์ ์ ๋ ฅ์ด ์ผ์นํ์ง ์๋ ์ ํํ ๋ ํ์์ 1๊ณผ ๊ฐ์ต๋๋ค. ์ด "์ฐจ์ด ๊ฐ์ง" ํน์ฑ์ด XOR์ ํจ๋ฆฌํฐ ๊ฒ์ฌ, ๋จ์ ์ํธํ ๋ฐ ๋นํธ ํ ๊ธ์ ์ ์ฉํ๊ฒ ๋ง๋๋ ๊ฒ์ ๋๋ค.
๊ณตํต ์ ๋ ฅ ์์ ๋ํ XOR
๋ค์ ํ๋ ๋นํธ XOR ์ฐ์ฐ์ ํตํด ์ฌ๋ฌ ๋ํ์ ์ธ ์์ ์ฒ๋ฆฌํ๋ฉฐ, ๊ฐ ํผ์ฐ์ฐ์๋ฅผ ์ด์ง๋ฒ์ผ๋ก ํ์ํ ๋ค์ ๊ฒฐ๊ณผ๋ฅผ ์ญ์ง๋ฒ, ์ด์ง๋ฒ ๋ฐ ์ญ์ก์ง๋ฒ์ผ๋ก ํ์ํฉ๋๋ค. XOR์ ๋นํธ๋ณ๋ก ์ํ๋ฉ๋๋ค: ๋ ์ด์ง ์๋ฅผ ์ ๋ ฌํ๊ณ ๋นํธ๊ฐ ๋ค๋ฅธ ๋ชจ๋ ์์น์์ 1์ ์ถ๋ ฅํฉ๋๋ค.
| A | B | A (์ด์ง๋ฒ) | B (์ด์ง๋ฒ) | A ^ B (์ญ์ง๋ฒ) | A ^ B (์ด์ง๋ฒ) | A ^ B (์ญ์ก์ง๋ฒ) |
|---|---|---|---|---|---|---|
| 5 | 3 | 0101 | 0011 | 6 | 0110 | 0x6 |
| 255 | 15 | 11111111 | 00001111 | 240 | 11110000 | 0xF0 |
| 12 | 12 | 1100 | 1100 | 0 | 0000 | 0x0 |
| 7 | 0 | 0111 | 0000 | 7 | 0111 | 0x7 |
| 10 | 6 | 1010 | 0110 | 12 | 1100 | 0xC |
| -1 | 1 | โฆ11111111 | โฆ00000001 | -2 | โฆ11111110 | 0xโฆFE |
๋ ๊ฐ์ง ํจํด์ด ๋๋๋ฌ์ง๋๋ค. ํผ์ฐ์ฐ์๊ฐ 0์ผ ๋, XOR์ ๋ค๋ฅธ ํผ์ฐ์ฐ์๋ฅผ ๋ณ๊ฒฝํ์ง ์๊ณ ๋ฐํํฉ๋๋ค(\(7 \oplus 0 = 7\)). ๋ ํผ์ฐ์ฐ์๊ฐ ๋์ผํ ๋, XOR์ 0์ ๋ฐํํฉ๋๋ค(\(12 \oplus 12 = 0\)). ์์ ์์ ๋ 2์ ๋ณด์ ํํ์ ์ฌ์ฉํฉ๋๋ค: \(-1\)์ ๋ชจ๋ 1๋นํธ์ด๋ฏ๋ก, ์ด๋ฅผ ์์์ ๊ฐ๊ณผ XORํ๋ฉด ๋ชจ๋ ๋นํธ๋ฅผ ๋ฐ์ ์ํต๋๋ค(์ด๋ ๋นํธ NOT๊ณผ ๋์ผํจ). \(-1 \oplus 1 = -2\)๋ฅผ ์ค๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
XOR์ ๋ฌด์จ ๋ป์ธ๊ฐ์? ๋ฐฐํ์ ๋ ผ๋ฆฌํฉ(Exclusive OR)์ ์๋ฏธํ๋ฉฐ, ๋ ์ ๋ ฅ ์ค ์ ํํ ํ๋๋ง ์ฐธ(1)์ผ ๋๋ง ๊ฒฐ๊ณผ๊ฐ ์ฐธ์ด ๋ฉ๋๋ค.
์ XOR์ด ์ํธํ์์ ์ฐ์ด๋์? ๋ฐ์ดํฐ๋ฅผ ํค์ XORํ๋ ์ฐ์ฐ์ ๊ฐ์ญ์ ์ด๊ธฐ ๋๋ฌธ์ ๋๋ค. ๊ฐ์ ํค๋ฅผ ํ ๋ฒ ๋ ์ ์ฉํ๋ฉด ์๋ ๋ฐ์ดํฐ๊ฐ ๋ณต์๋ฉ๋๋ค(\(A \oplus K \oplus K = A\)).
์์๋ ์ฒ๋ฆฌํ ์ ์๋์? ๋ค. ์์๋ 2์ ๋ณด์(two's complement) ํํ์ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์, ์์์ 2์ง์ ํ์์๋ ๋ง์ ๋นํธ๊ฐ ํฌํจ๋ ์ ์์ต๋๋ค.