XOR

 (chiark.greenend.org.uk)
1P by GN⁺ | ★ favorite | 댓글 1개
  • XOR는 두 비트가 서로 다를 때 1이 되는 연산으로, 배타적 OR·같지 않음·조건부 반전·mod 2 덧셈/뺄셈을 하나의 동작으로 연결해 이해할 수 있음
  • 정수에 대한 비트 단위 XOR는 각 자리를 독립적으로 처리해 비트별 차이를 드러내고, 자리올림 없는 이진 덧셈처럼 동작하면서 교환법칙·결합법칙·0 항등원·자기 역원 성질을 유지함
  • 암호에서는 평문과 키스트림을 결합하는 데 쓰이고, 과거 픽셀 그래픽에서는 같은 그림을 다시 그려 지우는 방식으로 메모리와 CPU 부담을 줄였음
  • 반가산기 항등식, 비트 교환, 세 번의 XOR 스왑, Nim 게임의 승리 조건처럼 차이를 만들고 다시 상쇄하는 계산에서 XOR의 성질이 직접 활용됨
  • 집합의 대칭차, 지수 2인 군, nim-sum, GF(2) 위 선형대수와 다항식까지 이어지며 Hamming 코드·CRC·AES·GCM·Classic McEliece 같은 오류 검출·정정 및 암호 기법과도 연결됨

XOR의 기본 의미

  • XOR는 두 입력 비트와 하나의 출력 비트를 갖는 불리언 연산이며, 진리표는 00→0, 01→1, 10→1, 11→0임
  • “exclusive OR”로 보면 두 입력 중 하나만 참일 때 1이고, 둘 다 참이면 0임
  • “not equals”로 보면 a XOR b는 a ≠ b와 같아 두 불리언 값이 다를 때 1을 냄
  • 조건부 반전으로 보면 a=0일 때 b를 그대로 두고, a=1일 때 b를 뒤집음
    • 같은 이유로 b를 제어 입력으로 보고 a를 뒤집는 해석도 가능함
  • 패리티 관점에서는 입력 중 1의 개수가 홀수인지 알려줌
    • 두 비트에서는 a+b mod 2와 같음
    • a-b mod 2와도 같음
    • 여러 값을 XOR하면 전체 입력 중 1의 개수가 홀수인지 짝수인지 알 수 있음

XOR의 대수적 성질

  • XOR는 교환법칙과 결합법칙을 만족함
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • 긴 XOR 목록에서는 순서와 묶는 방식이 결과에 영향을 주지 않음
  • 0은 XOR의 항등원임
    • a XOR 0 = 0 XOR a = a
    • 긴 XOR 목록에서 0은 제거해도 됨
  • 모든 값은 자기 자신에 대한 역원임
    • a XOR a = 0
    • 같은 변수가 두 번 나오면 두 항을 함께 제거할 수 있음
    • (a XOR b) XOR b = a처럼 이미 섞인 값에서 알고 있는 항을 한 번 더 XOR해 제거할 수 있음

정수에 대한 비트 단위 XOR

  • 정수의 비트 단위 XOR는 두 정수를 이진수로 놓고 각 자리의 비트를 독립적으로 XOR함
  • 단일 비트 XOR의 성질은 정수에도 그대로 적용됨
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • a XOR 0 = a
    • a XOR a = 0
  • 비트 단위 XOR는 두 정수의 비트별 차이를 알려줌
    • a=b이면 a XOR b = 0
    • a≠b이면 적어도 한 비트가 달라 a XOR b ≠ 0
    • 결과값의 1 비트들은 두 입력이 서로 다른 위치를 나타냄
  • 비트 단위 XOR는 조건부 비트 반전기로도 볼 수 있음
    • 제어값의 1 비트 위치에서만 데이터 비트를 뒤집음
    • ASCII와 일부 후속 인코딩에서는 라틴 대문자와 소문자가 한 비트만 달라, 문자 값에 32를 XOR하면 대소문자를 바꿀 수 있음
    • 이 규칙은 모든 Unicode 문자에 적용되지 않으며, 대소문자 개념이 없거나 규칙을 따르지 않는 문자도 많음
  • 비트 단위 XOR는 자리올림 없는 이진 덧셈과 같음
    • 각 자리에서만 mod 2 덧셈을 하고 다음 자리로 자리올림을 전달하지 않음

암호에서의 XOR

  • 암호에서는 평문과 같은 길이의 키스트림을 만들고, 평문 바이트나 워드와 키스트림을 결합해 암호문을 만드는 방식이 쓰임
  • 이 결합 단계에는 XOR가 일반적으로 사용됨
    • 수신자는 같은 키스트림을 다시 XOR해 원래 평문을 복원할 수 있음
    • 송신자와 수신자가 같은 연산을 쓴다는 점도 약간 더 편리함
  • 키스트림 자체를 만드는 방식은 더 복잡할 수 있음
    • one-time pad는 전체 메시지 크기만큼의 진짜 무작위 데이터를 쓰며 깨지지 않지만, 대부분의 목적에는 매우 비실용적임
    • 보통은 스트림 암호나 counter mode로 동작하는 블록 암호가 작은 키에서 필요한 길이의 키스트림을 만듦
  • 이 방식은 좋은 키스트림이 있을 때 기밀성을 제공할 수 있지만, 메시지 변조를 검출하는 무결성은 제공하지 않음
    • 무결성 보호는 별도 문제임
    • 초보 암호 시스템 설계에서 무결성을 빼는 것은 흔한 실수이며, 더 복잡한 암호화 방식에서도 잘못된 결과를 낳음
  • 하드웨어에서는 덧셈보다 XOR가 더 단순함
    • 덧셈은 비트 사이 자리올림 전파가 필요해 칩 공간과 시간이 더 듦
    • XOR는 자리올림이 없어 맞춤형 회로에서 더 저렴함

XOR 드로잉과 픽셀 그래픽

  • 1980년대 가정용 컴퓨터는 화면 픽셀당 비트 수와 RAM이 제한되어 화면 전체를 두 벌 저장하기 어려웠음
  • 움직이는 객체를 XOR로 그리면, 같은 객체를 다시 그리는 것만으로 원래 화면을 복원할 수 있음
    • 픽셀 값 S와 움직이는 객체의 픽셀 M을 XOR해 C를 만들고, 나중에 같은 M을 다시 XOR해 S를 회복함
  • 여러 픽셀이 한 바이트에 packed되거나 bit plane 구조를 쓰는 화면에서는 덧셈 기반 합성이 까다로움
    • 일반 덧셈은 한 픽셀의 자리올림이 다음 픽셀로 넘어갈 수 있음
    • XOR는 자리올림이 전혀 없어 이런 문제가 없음
  • XOR로 선을 그리면 두 선이 교차한 픽셀은 두 번 뒤집혀 배경색으로 돌아가 작은 흠처럼 보일 수 있음
    • 이 흠은 선 하나를 지울 때 다른 선을 망가뜨리지 않는 대가로 받아들여졌음
  • XOR 드로잉은 간단한 애니메이션에도 유리했음
    • 새 선 하나를 그리고 오래된 선 하나를 다시 그려 지우면 다음 프레임이 됨
    • 현재 화면의 모든 픽셀이나 모든 선을 다시 그릴 필요가 없어 메모리와 CPU 사용이 적음
    • 1981년 게임 Qix의 움직이는 선, 초기 GUI의 창 이동 윤곽선에도 이런 방식이 쓰였음

반가산기 항등식

  • 한 비트 덧셈에서 a+b의 낮은 비트는 a XOR b, 높은 비트는 a AND b임
  • 같은 관계는 정수의 비트 단위 연산에도 성립함
    • a + b = (a XOR b) + 2 × (a AND b)
    • a XOR b는 자리올림 없이 더한 값이고, a AND b는 각 자리에서 발생해야 했던 자리올림 비트들을 담음
  • 이 관계는 반가산기 항등식으로 볼 수 있음
    • 하드웨어 반가산기는 AND와 XOR 게이트로 두 비트 덧셈의 자리올림과 낮은 비트를 만듦
    • 전체 정수 덧셈을 단순 연산만으로 만든 것은 아니며, 오른쪽 식의 +가 자리올림 전파를 마무리함
  • 오버플로 없이 두 정수 평균을 구할 때 이 항등식을 쓸 수 있음
    • 단순히 a+b 후 오른쪽 시프트하면 33비트 합의 최상위 비트를 잃을 수 있음
    • carry flag나 RRX/RCR 같은 명령이 없거나 불편한 CPU에서는 (a XOR b) >> 1 + (a AND b) 형태가 대안이 됨
    • 예시로 MIPS, RISC-V, DEC Alpha는 carry flag가 없고, 초기 Arm Thumb은 RRX가 빠져 있었음
  • XOR 명령이 없는 CPU에서는 이 항등식을 뒤집어 XOR를 만들 수 있음
    • a XOR b = (a + b) − 2 × (a AND b)
    • 1970년대 Data General CPU는 AND는 있었지만 bitwise XOR가 없었음

비트와 값의 스왑

  • 두 비트를 바꾸는 문제는 두 비트가 같으면 아무 작업도 필요 없고, 다르면 두 비트를 모두 뒤집는 문제로 줄어듦
  • XOR와 시프트를 쓰면 두 비트가 다른지 찾고 필요한 경우 두 위치를 모두 뒤집을 수 있음
    • diff_all = input XOR (input >> distance)로 일정 거리만큼 떨어진 비트쌍의 차이를 계산함
    • AND로 관심 있는 위치만 골라냄
    • 선택된 차이를 다른 위치로 복제한 뒤 입력에 XOR해 필요한 경우에만 두 비트를 뒤집음
  • 같은 거리만큼 떨어진 여러 비트쌍을 한꺼번에 바꾸는 데도 같은 방식이 쓰일 수 있음
    • 한 비트 마스크 대신 여러 비트를 담은 마스크를 사용함
    • Beneš network는 여러 단계에서 같은 거리의 많은 쌍을 교환해 임의의 순열을 표현할 수 있음
  • 두 값 전체를 바꾸는 세 번의 XOR 스왑도 가능함
    • a = a XOR b
    • b = b XOR a
    • a = a XOR b
    • 임시 변수가 없어도 두 값이 서로 교환됨
  • 세 번의 XOR 스왑에는 별칭(aliasing) 문제가 있음
    • 서로 다른 변수를 바꿀 때는 동작함
    • 배열의 같은 원소를 자기 자신과 바꾸는 경우처럼 두 이름이 같은 저장 위치를 가리키면 값이 0이 될 수 있음

Nim 게임과 XOR

  • Nim은 여러 더미에서 차례로 하나의 더미를 골라 1개 이상 원하는 수만큼 말을 제거하는 게임이며, 더 이상 움직일 수 없으면 짐
  • 단순 버전의 Nim에서 지는 위치는 모든 더미 크기의 비트 단위 XOR가 0인 위치임
  • XOR가 0인 위치에서 한 더미 크기 a를 다른 값 b로 바꾸면 전체 XOR는 a XOR b만큼 바뀌며, a≠b이므로 0이 아니게 됨
  • XOR가 0이 아닌 위치에서는 전체 XOR값 x의 가장 높은 1 비트를 보고, 그 비트가 1인 더미를 골라 크기를 pile XOR x로 줄이면 전체 XOR를 0으로 만들 수 있음
  • 예시로 더미 크기 12, 10, 3은 이진수 1100, 1010, 0011이고 XOR는 0101임
    • 가장 큰 더미 12만 0101을 XOR했을 때 9로 줄어듦
    • 승리 수는 12에서 3개를 제거해 9로 만드는 것임

XOR처럼 보이는 수학 구조

  • 집합론의 대칭차 X∆Y는 어떤 원소가 두 집합 중 정확히 하나에만 속할 때 포함하는 연산임
    • 원소 포함 여부를 불리언 값으로 보면 대칭차는 XOR와 같음
    • 따라서 교환법칙과 결합법칙 같은 XOR 성질을 공유함
  • 군론에서 지수 2인 군은 모든 원소가 자기 역원인 군임
    • 이런 군의 연산은 결합법칙을 만족하고, 표준 연습으로 교환법칙도 따름
    • 같은 원소 두 개가 함께 있으면 상쇄되는 점이 XOR와 닮음
    • 모든 지수 2인 군은 어떤 {0,1}값 함수들의 비트 단위 XOR 형태로 이해할 수 있음
  • Sprague-Grundy 분석에서는 많은 impartial game 위치에 Grundy number를 부여함
    • 여러 하위 게임을 하나로 합친 composite의 Grundy number는 각 구성 게임의 Grundy number를 bitwise XOR한 값으로 계산됨
    • game theory에서는 비음수 정수의 bitwise XOR를 nim-sum이라고 부르기도 함
  • 체 GF(2)는 원소가 0과 1뿐인 유한체임
    • 덧셈과 뺄셈은 XOR처럼 동작함
    • 곱셈은 AND처럼 동작함
    • 따라서 a AND (b XOR c) = (a AND b) XOR (a AND c)가 성립함

GF(2) 위 선형대수와 오류 정정

  • GF(2) 위 벡터와 행렬은 성분이 0 또는 1인 구조이며, 벡터나 행렬의 덧셈은 성분별 XOR임
  • 행렬 M에 벡터 v를 곱하는 것은 v의 1 성분이 선택한 M의 열들을 XOR로 합치는 것과 같음
  • 오류 정정 코드는 m비트 메시지를 더 긴 n비트 코드워드로 확장해 일부 비트 오류를 검출하거나 정정할 수 있게 함
    • 유효한 코드워드들이 서로 많은 비트에서 다르면, 적은 수의 비트 오류는 다른 유효 코드워드로 바뀌지 않음
    • 두 유효 코드워드가 최소 k비트 다르면 k보다 적은 오류는 검출 가능하고, k/2보다 적은 오류는 가장 가까운 코드워드를 찾아 정정 가능함
  • 선형 코드는 GF(2) 위 generator matrix와 check matrix를 사용함
    • sender는 generator matrix로 m비트 메시지를 n비트 코드워드로 확장함
    • receiver는 check matrix로 수신 코드워드가 유효한지 확인하고, 오류가 있으면 syndrome을 얻음
    • 같은 오류 패턴은 메시지와 무관하게 같은 syndrome을 생성함
  • Hamming code는 코드 길이 n이 2^d−1인 경우의 예시임
    • n=15이면 15비트 위치를 0001부터 1111까지의 4비트 비영 숫자로 번호 매김함
    • 수신자는 1인 비트의 인덱스를 모두 XOR하며, 결과가 0이면 유효 코드워드임
    • 한 비트가 뒤집히면 XOR 결과가 바로 뒤집힌 비트의 인덱스가 되어 lookup table 없이 1비트 오류를 고칠 수 있음
    • 15비트 Hamming code는 11비트 데이터를 담고 4비트를 오류 정정에 사용함

GF(2) 다항식, CRC, 더 큰 유한체

  • GF(2) 위 다항식은 계수가 0 또는 1인 형식적 다항식이며, 덧셈은 같은 차수 계수끼리 XOR하는 것과 같음
  • 다항식 곱셈은 일반 다항식처럼 부분곱을 만들고 계수를 mod 2로 줄이는 방식임
    • 이 표현을 비트열로 보면 정수 곱셈과 비슷하지만, 부분곱을 합칠 때 일반 덧셈 대신 carry 없는 XOR를 씀
    • x86은 CLMUL을 포함한 carryless multiplication 명령을 제공하고, Arm은 polynomial multiplication 계열 명령을 제공함
  • CRC는 GF(2) 다항식 나눗셈의 나머지를 체크섬으로 쓰는 방식임
    • 송신 메시지 비트열을 큰 다항식 M으로 보고, 합의된 다항식 P로 나눈 나머지 M mod P를 유지함
    • Ethernet과 유사한 네트워크 패킷 검증에 사용됨
    • CRC는 오류를 정정하지 않고 검출만 하며, 거의 모든 전송이 정상이고 드물게 비트 뒤집힘이나 노이즈가 생기는 상황에 맞음
  • 더 큰 유한체는 GF(p) 위 다항식을 irreducible polynomial Q로 나눈 나머지 구조로 만들 수 있음
    • Q의 차수가 d이면 새 유한체는 p^d개의 원소를 가짐
    • p=2인 경우 irreducible polynomial은 비트 패턴을 정수처럼 적을 수 있으며, 해당 수열은 OEIS A014580에 등록되어 있음
  • 2의 거듭제곱 크기 유한체는 여러 암호 기술에 등장함
    • 2^8 크기 유한체는 AES와 Twofish의 핵심 구성 요소임
    • 2^128 크기 유한체는 bulk encryption과 integrity protection을 결합하는 GCM에 쓰임
    • 2의 거듭제곱 크기 유한체는 일부 elliptic-curve cryptography와 post-quantum 방식인 Classic McEliece의 decoding 알고리듬에도 등장함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 내가 좋아하는 저주받은 XOR 기법은 XOR 이중 연결 리스트임: https://en.m.wikipedia.org/wiki/XOR_linked_list
    각 노드가 다음/이전 포인터를 따로 저장하는 대신 둘을 XOR한 단일 값을 저장함. 당연히 유효하지 않은 포인터지만, 순회할 때 이전 노드 포인터와 결합 포인터를 XOR하면 다음 노드 포인터가 나오고, 양방향 순회도 가능함. 불법 같은 느낌이 듦

    • 일반 이중 연결 리스트에 비해, 항목의 주소만 가지고 있거나 삽입/삭제에도 안정적인 반복자만 있을 때 그 항목을 제거하는 능력을 잃어버림. 그런데 이게 이중 연결 리스트를 쓰는 핵심 이유인 경우가 많음
      덜 본질적인 결점으로는, 표준을 엄격히 따르는 C에서 XOR 연결 리스트를 짜는 게 몹시 귀찮음. 표준은 같은 포인터를 정수로 캐스팅했을 때 같은 정수가 된다고 보장하지 않아서, 사실상 정규화된 정수 캐스팅 버전을 유지하려고 모든 것을 uintptr_t로 만들어야 함
    • 64비트 프로세서에서도 대부분의 앱은 4GB 미만 RAM이면 충분하다고 보면, 32비트 주소 공간만으로 저장 공간을 더 줄일 수 있음
      더 나아가 16비트 근거리/상대 포인터도 가능할지 모름. 데이터 지향 설계와 잘 맞을 수도 있고, 64K 요소 블록을 두고 내부 요소는 uint16 인덱스로 가리키는 식이 가능함
    • 이렇게 하면 가비지 컬렉터가 싫어할 것임. 아니면 최소한 이 자료구조를 쓰레기로 판단할 듯함
    • 이 기법을 왜 쓰고 싶어지는지 궁금함
    • 이건 포인터라기보다 두 포인터의 차이를 저장하는 것과 별로 다르지 않음. 차이를 저장해도 당연히 양방향 순회가 가능함

  • 빠뜨린 게 있음. XOR는 3-wise 독립 선형 해시 함수이기도 해서, 불리언 함수 해의 확률적 근사 균등 표본추출과 개수 세기에 쓸 수 있음. 정말 유용하고, 확률적이지만 증명된 개수를 주는 계수기를 만드는 데 사용함. 더 이해하기 쉬운 설명은 여기 적어둠 https://www.msoos.org/2018/12/how-approximate-model-counting...
    기본적으로 매번 해 공간을 거의 정확히 반으로 줄임. 그래서 XOR 조건을 계속 추가하다가 예컨대 해가 10개 남으면, 추가한 XOR 개수를 k라고 할 때 10에 2^k를 곱하면 됨. 매번 반씩 줄어드니 10개 수준까지도 금방 도달해서 확장성이 좋음
    관련 논문은 https://arxiv.org/abs/1306.5726와 https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf에 있고, 도구는 https://github.com/meelgroup/approxmc와 https://github.com/meelgroup/unigen에 있음. 지난 모델 카운팅 대회에서는 정확한 계수기와 결합했을 때 다른 경쟁자를 압도했고, 슬라이드는 https://mccompetition.org/assets/files/2024/MC2024_awards.pd...에 있음

  • 내가 좋아하는 XOR 일화 중 하나는 Oxide, Joyent, Sun의 Bryan Cantrill이 이 발표 https://speakerdeck.com/bcantrill/oral-tradition-in-software...와 이 영상 https://www.youtube.com/watch?v=4PaWFYm0kEw에서 한 이야기임
    링크를 안 눌러도 되게 요약하면, Sun에 있을 때 동료 Roger Faulkner와 C에 논리 XOR가 없는 이유를 얘기했는데, Faulkner는 단락 평가를 할 수 없기 때문이라고 했고 Brian은 그게 이상하다고 생각함. 그러자 Roger가 Dennis Ritchie에게 이메일로 물었고, Ritchie가 Faulkner 말이 맞다고 확인해줌. Cantrill의 전달도 웃기지만, 당사자에게 직접 물어볼 수 있었다는 점이 놀라움

    • DMR은 놀랄 만큼 친절하고, 잘 도와주고, 접근하기 쉬운 사람이었음. 80년대 중반 학부생 때 PDP-11이 아닌 Interdata 8/32로 Unix v6를 이식한 “첫” 사례를 읽고, 아키텍처 정보가 더 있는지 dmr@research.att.com으로 무작정 이메일을 보냄
      당시엔 Google도 없고 대학 도서관에도 자료가 없었는데, 며칠 뒤 물리 주소를 물어보더니 몇 주 후 명령어 집합 요약 매뉴얼 사본이 우편함에 도착함. IBM 360 계열 느낌이었고 아직도 가지고 있음
    • C에는 논리 XOR가 있고, 바로 != 연산자임. 다른 논리 연산자와 달리 인수를 단일 참값으로 정규화해야 하며, C의 불리언 변환 관용구 !!와 잘 맞음
    • “단락 평가를 할 수 없기 때문”이라는 게 왜 연산자를 추가하는 데 장애가 되는지 이해가 안 됨. 누가 설명해줬으면 함
    • 해당 주제는 37:18부터 시작함
    • C에는 40년 넘게 비트 XOR 연산자 ^가 있었음: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

  • 자동차 이모지를 0x20과 XOR하면, 즉 “소문자화”하면 보행자 금지 이모지가 된다는 걸 오늘 알았음. 우연치고는 너무 딱 맞는 것 같은데, 의도적으로 된 건지 아는 사람이 있는지 궁금함
    너무 밀고 나가면 자동차 이모지의 소문자가 ‘보행자 금지’ 표지판이라는 이상한 생각도 가능함

    • HN의 이모지 제거 댓글 처리기를 피하려면 이렇게 확인 가능함:
      >>> from unicodedata import lookup, name
      >>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
      'NO PEDESTRIANS'
    • 자동차의 소문자는 고카트일 것 같음
    • :tada: → :tophat:, :rocket: → :mountain_cableway:도 가능함

  • XOR를 설명할 때 쓰기 좋은 현실 비유는 집 계단 위의 조명 스위치임. 아래쪽에 스위치 하나, 위쪽에 스위치 하나가 있고 둘 다 같은 조명을 제어함
    처음엔 둘 다 꺼짐 위치에 있다가, 아래 스위치를 켜면 불이 켜짐. 계단을 올라가 위 스위치를 켜면 두 스위치가 모두 “켜짐” 위치인데도 불은 꺼짐. 한 스위치만 “켜짐”이고 다른 하나가 “꺼짐”일 때만 불이 켜지고, 그 외에는 꺼짐

    • 우리 사무실 전기공이 배선을 잘못했을지도 모르겠음. 방에 스위치가 둘 있는데 생각해보니 XOR보다 AND 게이트처럼 동작함. 거실의 스위치 두 개는 확실히 XOR처럼 동작함

  • 이 논리 함수에 XOR, 즉 “배타적 OR”라는 이름을 흔히 쓰는 게 정말 마음에 안 듦. 거의 항상 실제 의미는 “2로 나눈 나머지 합”, 즉 패리티이지 배타적 OR가 아니기 때문임
    “2로 나눈 나머지 합”/패리티와 “배타적 OR”는 서로 다른 논리 함수이고, 입력 피연산자가 2개일 때만 우연히 일치함. 2 이하의 홀수가 하나뿐이기 때문임
    입력이 3개 이상일 때 대부분이 XOR라고 부르는 것은 실제로는 홀수 개의 입력이 1일 때 1이 되는 패리티임. 반면 배타적 OR는 입력이 3개 이상일 때 정확히 하나의 입력만 1이고 나머지가 모두 0일 때만 1이 되는 함수임
    컴퓨터 하드웨어에서는 패리티가 배타적 OR보다 훨씬 중요함. 주된 이유는 2로 나눈 나머지 덧셈이 더 큰 수의 덧셈 구현을 위한 구성 요소로 쓰이기 때문임. 반대로 수학에서는 배타적 OR가 패리티보다 훨씬 중요함
    예를 들어 어떤 술어가 집합의 일부 원소, 모든 원소, 또는 유일한 원소에 대해 참임을 표현하는 양화사는 각각 OR, AND, 배타적 OR에 기반함. 자연어의 “or”는 항상 포괄적 OR나 배타적 OR를 뜻하지, 많은 프로그래머가 XOR라고 부르는 패리티를 뜻하지 않음
    프로그래밍에서 배타적 OR 논리 함수를 계산할 일은 드물지만, 프로그램 동작 설명에는 자주 쓰임. 예컨대 select/case/switch 복합문에서 첫 번째 문장 또는 두 번째 문장 또는 세 번째 문장 중 하나가 실행된다거나, 유니언/합 타입 변수의 현재 값이 가질 수 있는 타입을 설명할 때가 그렇다

    • 전기기술 기호 표준인 IEC 60617은 이 부분을 제대로 처리함. XOR 게이트는 =1, 패리티 게이트는 2k + 1로 표시함. 하지만 PCB나 FPGA용 회로 설계 소프트웨어를 쓰다 보면 기대한 것과 다른 것을 받아서 여전히 당할 수 있음
    • 수학에서 말한 것은 유일 존재 양화라고 부르고, 자체 기호 ∃!가 있음
    • 입력이 3개 이상일 때 “배타적 OR”가 정확히 하나만 1일 때 참이라는 설명에는 근거가 필요함
    • 이 해석은 본문 에세이에서도 다뤄짐

  • Kademlia 분산 해시 테이블도 있음: kademlia distributed hash table. 큰 아이디어는 각 노드가 [0, 2^m) 범위의 임의 비트를 받고, 거리를 XOR로 정의하는 것임. 전체 네트워크를 모른 채 X에서 Y로 정보를 빠르게 보내는 분산 알고리즘을 찾고자 함
    수학만 봐도 동작을 증명할 수 있지만, 내가 좋아하는 시각적 직관은 이렇다. 시작 노드 X가 노드 k를 찾고 싶다고 하자. “X-거리 트리”를 잎 인덱스가 0, 1, 2...인 이진 트리로 정의하되, 각 잎에는 X와의 거리를 나타내도록 X^leaf_index 라벨을 붙임. 예를 들어 dist(x, x) = x^x = 0이므로 원래 노드 X 라벨은 가장 왼쪽 잎 0에 놓임
    구간 [2^i, 2^(i+1))는 X-거리 트리의 어떤 하위 트리임. k의 거리가 그 구간에 속한다고 알면, 그 안의 어떤 노드 Y를 근사 이웃으로 질의함
    어떤 Y를 고르든, Y-거리 트리에서 결과 접두부는 항상 X-거리 트리에서 고른 [2^i, 2^(i+1)) 하위 트리의 어떤 순열이 됨. 더 정확히는 labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i))라고 볼 수 있음. 인덱스는 거리 기준이지만 라벨은 달라질 수 있음
    Chord 같은 다른 분산 해시 테이블과의 비교는 수학적·경험적으로 훨씬 엄밀한 자료가 많음. 하지만 이 시각적 직관은 Kademlia의 “대칭성”이 무엇인지, 모두가 자기만의 지역 이웃과 자기 하위 트리를 가진다는 감각을 줌
    반면 Chord는 양방향으로 구현해도 메모리가 2배 들고 구현도 더 위험해 보이며, 이런 수준의 “고립성”을 얻기 어려움. 크기 S의 이웃 슬라이딩 윈도우가 항상 움직이고, 비트마다 2^m개의 서로 다른 이웃이 존재함. 대부분의 이웃이 비슷해 보이더라도 깔끔하진 않음
    Kademlia에는 1 + 2 + 4 ... + 2^m-1개의 이웃이 있고, 전체가 정돈되어 있음

  • 궁금해할 사람을 위해 덧붙이면, 이 사람은 Simon Tatham's Portable Puzzle Collection의 그 Simon Tatham임. 모른다면 오프라인에서 심심할 때 해볼 만함
    고등학교 때 이것들 하느라 시간을 많이 태웠음: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

  • 요즘 많은 맞춤형 최적화 해법기, 예를 들어 Ising Machine은 XOR 문제로 벤치마크를 함. 실제로는 XOR 절 여러 개를 푸는 일이 가우스 소거법으로 다항 시간에 가능해서 쓸모가 좀 떨어지지만, 해법기들이 모두 지수적 확장을 보이기 때문에 성능을 가늠하는 좋은 방법은 됨
    두 번째 흥미로운 구현은 McEliece 암호계와 관련됨. 70년대 공개키 암호로, 요즘은 양자 내성 때문에 다시 주목받고 있음. 복호 공격은 XOR 방정식 집합의 해를 찾는 문제인데, 역시 다항 시간이지만 해밍 거리가 공개키에 포함된 어떤 수와 같아야 한다는 조건이 붙음

  • TI-83 프로그래밍을 하려고 Z80 어셈블리를 배울 때는 기계어 1바이트가 모두 중요했음. 계산기 전체 저장 공간이 24KB뿐이었기 때문임
    주 누산기 레지스터 a를 0으로 초기화하려면 LD a, 0 대신 XOR a를 썼음. 수학 명령에서는 a가 자동 피연산자라서 XOR a는 a를 자기 자신과 XOR하고, 전체 명령이 1바이트뿐임. 반면 0을 명시적으로 a에 로드하려면 리터럴 0이 opcode에 들어가야 해서 LD a, 0은 2바이트 명령임

답변달기