포인터 뺄셈을 컴파일했더니 나눗셈 대신 괴상한 음수를 곱하는 이유

요약 C 언어에서 7바이트 크기의 구조체 포인터 2개를 뺄셈(`a - b`)하면, 개념상 두 주소의 차이를 7로 나누는 나눗셈 연산이 수행되어야 합니다. 그런데 gcc 컴파일러로 생성된 x86 어셈블리 코드를 확인해 보면 나눗셈(div) 명령어나 비트 시프트 연산 대신 엉뚱하게도 `-1227133513`이라는 거대한 음수를 곱하는 단 한 번의 곱셈 연산(`imull`)만 나타납니다. 이 기이한 현상은 컴퓨터 비트 레지스터의 수학적 특성과 p-진수(2-adic integers) 개념에서 비롯됩니다. Intel 4004 같은 초기 4비트 CPU에서 덧셈, 뺄셈, 곱셈을 할 때 최상위 비트 오버플로를 무시하고 하위 4비트만 보면, 하위 비트 연산 결과는 상위 비트의 영향을 받지 않는 성질이 있습니다. 이는 8비트, 32비트 CPU에서도 마찬가지로 적용됩니다. 수학적으로 2의 거듭제곱으로 나뉘는 거리 개념을 반대로 정의하면(2-adic 거리), 비트 수가 늘어날수록 무한 비트 머신으로 확장되는 코시 수열(Cauchy sequence)과 완비화 과정을 거쳐 2진 정수 체계에서 1/7과 같은 분수나 음수를 곱셈 역원으로 표현할 수 있게 됩니다. 즉, 32비트 모듈로 연산 체계에서 7로 나누는 작업은 7의 2-adic 곱셈 역원인 `-1227133513`을 곱하는 것과 정확히 일치하여 컴파일러가 값비싼 나눗셈 연산 대신 초고속 단일 곱셈으로 최적화해 처리하는 것입니다.