컴퓨터가 숫자를 기억할 때 크게 두 가지 방법이 있습니다. 부호가 있는signed 수와 부호가 없는unsigned 수인데요. C 언어와 같은 프로그래밍 언어는 이 둘을 데이터 타입으로서 명시적으로 구분합니다.

signed int a = -1; // signed integer
unsigned int b = 1; // unsigned integer

부호가 없는 수는 단순히 이진법 표현을 그대로 비트bit로 표현할 수 있습니다. 한편 부호가 있는 수의 비트 표현을 위해, 컴퓨터는 2의 보수two’s complement를 이용할 수 있습니다. 어떤 숫자 $n$ 의 2의 보수란, 충분히 크도록 선택한 2의 제곱 수 $2^M$ 에서 $n$ 을 뺀 수가 됩니다.

예를 들어 $-1$ 의 비트 표현을 얻기 위해, $2^8$ 에서 $1$ 을 뺀 수 $255$ 를 구합니다. 이는 이진수로 $1111 \thinspace 1111_{(2)}$ 이고, 이것이 곧 $-1$ 의 비트 표현이 됩니다.

그런데 왜 하필 이 표현을 $-1$ 로 선택할까요? 이것 말고 $1000 \thinspace 0001_{(2)}$ 같은 것처럼 다른 걸 고를 수는 없을까요? 만약 그럴 수 없다면 그 이유는 무엇일까요?

모듈러 연산과 2의 보수

2의 보수는 $2^M$ 를 $0$ 으로 취급하겠다는 가정이 숨어있습니다. 왜냐면 그 수 $2^M$ 은 정수 오버플로우integer overflow때문에 $0$ 으로 표현할 수 밖에 없도록 고를 테니까요.

그렇다면 모듈러 연산modular arithmetic이 이 자리에 알맞게 됩니다. 이는 모듈로module라고 하는 수를 두고, 그 수로 나눈 나머지 같으면 합동congruent인 수, 즉 같은 종류로 취급하는 연산입니다. 즉, 위 가정은 $2^M$ 과 $0$ 을 합동인 수로 보기위해 $2^M$ 을 모듈로로 선택한 것이 됩니다.

그러면 2의 보수이거나 부호가 없는 수이거나 상관없이 사실상 똑같은 모듈러 연산으로 생각할 수 있습니다. 즉 $64+65$ 는 이진수로 표현하면 다음과 같은데요.

\begin{align*} 64_{(10)} &{}+{} &65_{(10)} &{} \\ 0100 \thinspace 0000_{(2)} &{}+{} &0100 \thinspace 0001_{(2)} &{}= 1000 \thinspace 0001_{(2)} \end{align*}

위에서 한 것처럼, 프로그래밍 상에서 덧셈 64+65를 하면, 부호가 있거나 없거나 상관 없이 둘 다 모듈로 연산의 결과로 1000 0001을 낼 뿐입니다. 여기서 예를 들어 모듈로를 $2^8$ 로 합시다. 그러면 이를 부호가 없는 수로 해석했을 때 129가 되고, 부호가 있는 수는 -127이 됩니다. 아래 C 코드처럼요.

printf("%d\n", (unsigned char)(64 + 65)); // 129  (1000 0001)
printf("%d\n", (  signed char)(64 + 65)); // -127 (1000 0001)

즉 부호가 있거나 없거나 상관없이 똑같은 모듈러 연산으로 사칙연산을 할 수 있습니다. 이는 $129$ 와 $-127$ 이 합동이기 때문이 가능합니다. 다시 말해 $-127$ 의 비트 표현을 1000 0001으로 두었기 때문입니다.

아래 본문에서 여기까지의 설명을 모듈로 연산의 설명과 함께 좀더 천천히 살펴봅니다.

나머지 연산

나머지만 생각합시다. 어떤 수 $m$ 으로 나눈 나머지가 같으면 합동이라고 말할 것입니다. 여기서 $m$ 을 모듈로라고 부릅니다. 예를 들어, 모듈로가 4라면 1, 5, 9는 나머지가 1로 같으므로 합동입니다. 이런 사실을 다음과 같이 표현할 수 있습니다.

1 \equiv 5 \equiv 9 \mod 4

양의 정수에서 멈출 필요는 없습니다. 간격이 4만큼 떨어진 모든 음수 또한 합동입니다.

1 \equiv -3 \equiv -7 \mod 4

예시: 32비트 오버플로우

2의 보수를 $2^M$ 를 모듈로로 한 것으로 볼 수 있는데요. 예를 들어 $2^{32}$ 를 모듈로로 합시다. 그러면 $2^{32}-1$ 을 보세요.

2^{32}-1 \equiv -1 \mod 2^{32}

위와 같이 $-1$ 와 합동이 됩니다. 그래서 많은 프로그래밍 언어에서 32비트 크기의 값 $2^{32}-1$ 이 -1이라는, 엉뚱해 보이는 값을 갖게 됩니다. 정수 오버플로우라고 불리는 이 현상은 대표적으로 C 언어의 int 자료형에서 볼 수 있습니다. (물론 int 자료형이 32비트를 쓴다면요.)

int a = 4294967295;  // 2^32 - 1
printf("%d", a); // -1

비트 표현과 해석

메모리에 담긴 비트는 그 자체로는 아무런 의미도 갖지 않습니다. 그 비트를 사용하는 입장에서 그것을 어떻게 해석할지 결정합니다.

4비트 해석 규칙 만들기

4비트 메모리가 있다고 해봅시다. 예를 들어 여기에 1111이 들어있다면, 이진수 $1111_{(2)}$ 로 해석할 수 있는데요. $2^4=16$ 을 모듈로로 하면, 이와 합동인 수는 다음과 같이 모든 정수 $n$ 에 대해 $15+16n$ 이 됩니다.

1111_{(2)} \equiv 15 + 16n \mod 16

위 식에서 $n=0$ 인 경우, $15$ 가 합동이라는 걸 쉽게 알 수 있는데요.

1111_{(2)} \equiv 15 + 0 \equiv 15 \mod 16

한편 $n=-1$ 이라면 $-1$ 도 합동임을 알 수 있습니다.

1111_{(2)} \equiv 15 - 16 \equiv -1 \mod 16

이를 이용해 비트 표현 1111은, 부호가 없는 수로서 $15$ 로, 부호가 있는 수로서 $-1$ 로 해석할 수 있습니다. 다시 말해, 같은 비트 표현이라도 상황에 따라 이렇게 달리 이해하기로 약속할 수 있습니다.

다른 비트 표현도 마찬가지입니다. 네 개의 비트는 16가지 경우를 만들 수 있고, 따라서 각 16종류의 합동마다 하나의 숫자를 선택할 수 있습니다. 그렇게 숫자를 16개 모았을 때, 비트 표현의 해석 규칙을 만들 수 있습니다.

예를 들어, 부호가 없는 수는 앞서 언급한대로 $n=0$ 일 때의 합동 수를 선택하고요.

unsigned number — 그림 1. 부호가 없는 수로 해석하는 비트 표현.

부호가 있는 수는 가장 왼쪽 비트가 1인 비트 표현에 대해 $n=1$ 일 때의 합동 수를 선택합니다. 그러면 가장 왼쪽 비트가 마치 부호를 결정하는 것처럼 보이게 됩니다.

signed number — 그림 2. 부호가 있는 수로 해석하는 비트 표현.

이는 비트 표현 1000의 해석을, 많은 음수 중에 하필 $-8$ 로 선택한 이유가 됩니다.

예시: 8비트 값

몇 개의 비트를 사용하더라도 이런 규칙을 똑같이 만들어낼 수 있습니다. 실제로 2의 보수에서는 8비트 값 1111 1000을 부호가 있는 수로서 -8로, 부호가 없는 수로서 248로 해석합니다. 이는 아래 C 코드가 보여줍니다.

printf("%d\n", (unsigned char)( -8)); // 248
printf("%d\n", (  signed char)(248)); // -8

이 두 수는 $2^8$ 을 모듈로로 합동입니다.

모듈러 연산과 오버플로우

이제 프로그래밍에서 숫자를 더한다고 해봅시다. 아까처럼 4비트 메모리 공간을 생각하고요.

예를 들어, 부호가 없는 숫자로서 $8$ 과 $9$ 를 더하면 $1$ 이 될 텐데요. 왜냐면 비트가 네 개인 메모리 공간에서 $2^4=16$ 은 오버플로우로 인해 버릴 수 밖에 없으니까요.

그런데 모듈러 연산은 이런 오버플로우의 효과가 자연스럽게 나타납니다.

8 + 9 \equiv 1 \mod 2^4

비트 표현을 이진수 그대로 옮기더라도, 모듈러 연산으로 똑같은 사실을 나타낼 수 있습니다.

1000_{(2)} + 1001_{(2)} = 10001_{(2)} \equiv 1_{(2)} \mod 10000_{(2)} \tag{A}

그런데 1000과 1001은 부호가 있는 수로 생각하면 각각 $-8$ , $-7$ 이 되는데요. 이 두 수의 합은 $1$ 과 합동입니다. 다음처럼 모듈러 연산이 말해주듯이요.

-8 + -7 \equiv 1 \mod 2^4

이진수 그대로 옮겼을 때도 또한 같은 사실을 말해줍니다.

1000_{(2)} + 1001_{(2)} = 10001_{(2)} \equiv 1_{(2)} \mod 10000_{(2)} \tag{A}

방금 얻었던 식 $\textrm{A}$ 가 다시 나타나는데요. 정확히 말하면 그 어떤 식에도 달라진 부분은 없었습니다. 왜냐면 $8 + 9$ 나 $-8 + -7$ 은 모듈러 연산에서 같은 것이니까요.

8 + 9 \equiv -8 + -7 \equiv 1 \mod 2^4

이는 비트 표현으로 모듈러 연산을 하는 것과, 비트 표현을 우리가 어떤 숫자로 해석하는지는 별개이기 때문입니다.

2의 보수 구하기

2의 보수라고 하면, 어떤 양수 $n$ 이 있을 때, 음수 $-n$ 을 구하는 방법이 다음과 같이 많이 소개됩니다.

비트 표현에서 0과 1을 서로 바꾼다.
하나를 더한다.

예를 들어, 숫자 $7$ 에서 음수 $-7$ 의 비트 표현을 구해야 한다고 해봅시다. 그러면 $7$ 의 비트 표현이 0111이기 때문에, 1000에서 1을 더해 1001로 답을 얻게 됩니다.

모듈러 연산에서 유도하기

이 계산법은 모듈러 연산으로부터 얻을 수 있는데요. 모듈로로 선택한 수, 즉 $2^M \equiv 0$ 으로부터 다음과 같이 나옵니다.

어떤 수 $n$ 이 있다고 해봅시다. 그리고 이 수의 비트 표현에서 0과 1을 서로 바꾼 수를 $\bar{n}$ 라고 부릅시다. 이는 1로 채워진 비트 111...1에서 $n$ 을 뺀 것입니다. 그런데 1로 채워진 비트란 곧 $2^M-1$ 입니다. 따라서 $\bar{n}$ 의 식을 얻습니다.

\bar{n} = 2^M - 1 - n

그러면 $-n$ 을 모듈러 연산으로 다음처럼 구할 수 있습니다.

\begin{align*} & \bar{n} = 2^M - 1 - n \equiv -n - 1 \mod 2^M \\ \therefore \quad & {-n} \equiv \bar{n} + 1 \mod 2^M \end{align*}

이 식이 말해주는 대로, $-n$ 은 $n$ 의 비트 표현에서 0과 1을 바꾸고 1을 더한 것이 됩니다. 즉 2의 보수를 얻는 계산법은 곧 모듈러 연산이 가진 하나의 성질임을 알 수 있습니다.

마치며

여기까지 모듈러 연산으로 2의 보수를 구해봤습니다. 그리고 이 연산을 2의 보수 뿐만 아니라, 부호가 없는 수에도 일반적으로 적용할 수 있었습니다. 즉 부호가 있거나 없거나 나머지를 구한다고 생각해보면, 항상 똑같은 방법으로 계산이 가능했습니다.

정수integer를 취급하는 컴퓨터는 이런 정수와 관련된 이론, 즉 정수론number theory과 밀접한 관련이 있을 수 밖에 없는데요. 모듈러 연산은 정수론에서 흔하게 사용되는 연산이기 때문에, 모듈러 연산에 대한 참고 자료는 정수론을 다루는 자료에서 쉽게 찾아볼 수 있습니다.

레퍼런스

Elementary Number Theory (Kenneth H. Rosen, 2011)
Computer Organization and Design (David Patterson, John Hennessy, 2013), 또는 컴퓨터 구조 및 설계 (2015)