음수·보수·넘침

온도 센서는 영하의 값도 보내야 합니다. 비트 패턴으로 음수를 나타내는 가장 쉬운 생각은 맨 앞 비트를 부호로 쓰는 것이지만, 그렇게 하면 덧셈 회로를 음수용으로 따로 만들어야 하는 불편이 생깁니다. 음수를 어떻게 나타내느냐가 회로의 모양과 연산 규칙까지 정하는 것입니다. 이 글에서는 앞 글의 고정 폭 정수를 부호 있는 정수(signed integer)로 넓히고, 오늘날 거의 모든 CPU가 쓰는 2의 보수를 중심으로 덧셈과 넘침을 다룹니다.

음수를 나타내는 세 가지 방법

4비트에서 +3은 0011입니다. 부호와 크기(sign-magnitude) 방식은 맨 앞 비트를 부호로, 나머지 세 비트를 크기로 써서 −3을 1011로 나타냅니다. 1의 보수(ones' complement) 방식은 모든 비트를 뒤집어 −3을 1100으로, 2의 보수(two's complement) 방식은 모든 비트를 뒤집은 뒤 1을 더해 −3을 1101로 나타냅니다.

앞의 두 방식에는 +0과 −0이라는 두 가지 0이 있어서, 0인지 확인할 때 두 패턴을 모두 봐야 합니다. 1의 보수 덧셈은 맨 앞에서 나온 자리올림을 다시 맨 아래 자리에 더해야 하는 규칙도 있습니다. 2의 보수에는 0이 하나뿐이고, 뒤에서 보듯이 부호 없는 수와 같은 덧셈 회로를 그대로 쓸 수 있어서 현대의 정수 연산은 거의 모두 2의 보수를 씁니다. 이 교재의 기본 모델도 2의 보수입니다.

2의 보수를 읽는 두 가지 방법

n비트 패턴을 먼저 부호 없는 수 u로 읽었을 때, 맨 앞 비트가 0이면 값은 u 그대로이고 1이면 $u-2^n$입니다. 4비트 1101은 13 − 16 = −3이고, 1000은 8 − 16 = −8입니다. 다른 방법으로, 맨 앞 비트의 무게를 $+2^{n-1}$ 대신 $-2^{n-1}$로 보아도 같은 값이 나옵니다. 1101은 −8 + 4 + 0 + 1 = −3입니다.

그래서 n비트 2의 보수의 범위는 $-2^{n-1}$부터 $2^{n-1}-1$까지이고, 음수가 양수보다 하나 더 많습니다. 4비트에서 −8은 1000으로 나타낼 수 있지만, 같은 크기의 +8을 나타낼 패턴은 없습니다. 맨 앞 비트가 1인 패턴 여덟 개가 모두 음수 −8부터 −1까지에 쓰이고, 맨 앞 비트가 0인 여덟 개가 0부터 +7까지에 쓰이기 때문입니다.

같은 덧셈 회로로 더하고 뺀다

2의 보수의 가장 큰 장점은 부호 없는 덧셈과 비트 수준에서 똑같이 더한다는 점입니다. 4비트에서 5 + (−3)은 0101 + 1101 = 10010이고, 아래 네 비트 0010이 정답 2입니다. 패턴 1101을 부호 없이 읽으면 13이고, 5 + 13 = 18을 16으로 나눈 나머지가 2이기 때문입니다. 음수 −3을 $16-3=13$으로 나타내 두었으니, 16을 법으로 하는 덧셈에서 −3을 더하는 것과 13을 더하는 것이 같은 셈입니다.

뺄셈 a − b는 a + (−b)로 바꾸어 계산합니다. −b는 b의 모든 비트를 뒤집고 1을 더한 것이므로, 덧셈 회로의 한쪽 입력을 비트마다 뒤집고 맨 아래 자리올림 입력에 1을 넣으면 같은 회로로 뺄셈을 할 수 있습니다. 다만 가장 작은 음수는 부호를 바꿀 수 없습니다. 4비트 −8 1000을 뒤집으면 0111, 1을 더하면 다시 1000이 되어 +8을 담지 못합니다.

자리올림과 부호 있는 넘침은 다르다

5 + (−3)에서는 맨 앞에서 자리올림 1이 나왔지만 부호 있는 결과 2는 정확합니다. 반대로 5 + 4는 0101 + 0100 = 1001로 자리올림은 0인데, 결과를 2의 보수로 읽으면 −7이라서 틀립니다. 수학적인 결과 9가 4비트 2의 보수의 범위 +7을 넘었기 때문이며, 이것을 부호 있는 넘침(signed overflow), 곧 오버플로라고 합니다. 자리올림은 부호 없는 수로 볼 때의 넘침을, 오버플로는 부호 있는 수로 볼 때의 넘침을 알려 주는 서로 다른 신호입니다.

부호 있는 넘침은 부호가 같은 두 수를 더했는데 결과의 부호가 다를 때만 생깁니다. 양수와 음수를 더하면 결과는 두 수 사이에 있으므로 범위를 넘을 수 없습니다. 회로에서는 같은 조건을 "맨 앞 자리로 들어간 자리올림과 맨 앞 자리에서 나온 자리올림이 다르다"로 판단합니다. CPU는 두 신호를 각각 자리올림 플래그와 오버플로 플래그에 기록하고, 프로그램이 수를 부호 없이 다루는지 부호 있게 다루는지에 따라 알맞은 플래그를 봅니다.

def signed(pattern, width):
    if not 0 <= pattern < (1 << width):
        raise ValueError("패턴이 폭을 벗어났습니다")
    return pattern - (1 << width) if pattern >> (width - 1) else pattern


def add4(a, b):
    total = a + b
    result = total & 0b1111
    carry = total >> 4
    overflow = (a >> 3) == (b >> 3) and (result >> 3) != (a >> 3)
    return f"{result:04b}", carry, overflow, signed(result, 4)


for a, b in ((0b0101, 0b1101), (0b0101, 0b0100), (0b1110, 0b0011), (0b1000, 0b1000)):
    print(f"{a:04b} + {b:04b} ->", *add4(a, b))
print(signed(0b1101, 4), signed(0b11111101, 8), signed(0b00001101, 8))
print(f"{(-6) & 0xFF:08b}", f"{(~0b1000 + 1) & 0b1111:04b}")

0101 + 1101 -> 0010 1 False 2
0101 + 0100 -> 1001 0 True -7
1110 + 0011 -> 0001 1 False 1
1000 + 1000 -> 0000 1 True 0
-3 -3 13
11111010 1000

signed는 맨 앞 비트가 1이면 $2^n$을 빼서 패턴을 2의 보수 값으로 읽습니다. add4는 4비트 덧셈의 저장 패턴, 자리올림, 오버플로, 부호 있는 값을 돌려주는데, 오버플로는 두 입력의 맨 앞 비트가 같고 결과의 맨 앞 비트가 다른지로 판단합니다. 네 줄의 덧셈은 차례로 자리올림만 있는 경우, 오버플로만 있는 경우, 자리올림만 있는 경우, 둘 다 있는 경우입니다. 마지막 줄의 −8 + −8은 수학적으로 −16인데 저장값이 0이라서 둘 다 켜집니다.

더 깊이: 플래그가 없는 RISC-V는 넘침을 어떻게 확인할까

자리올림과 오버플로를 플래그에 기록하는 것은 x86이나 ARM 같은 많은 CPU의 방식이지만, 모든 ISA가 플래그를 두지는 않습니다. RISC-V의 정수 연산 명령은 산술 예외를 일으키지 않고, 분기 명령도 조건 코드 대신 두 레지스터를 직접 비교합니다. RISC-V의 기본 정수 명령어 규격은 넘침 검사를 분기 명령으로 싸게 할 수 있어서 따로 지원하지 않았다고 설명합니다. 부호 없는 덧셈이라면 add t0, t1, t2 뒤에 bltu t0, t1, overflow 하나면 됩니다. 결과가 더한 수보다 작아졌다면 맨 앞에서 자리올림이 나가 버린 것이기 때문입니다.

부호 있는 덧셈은 조금 더 필요합니다. 한쪽 피연산자의 부호를 알 때, 예를 들어 양수 상수를 더할 때는 결과가 원래 값보다 작아졌는지 보는 분기 하나로 충분합니다. 일반적인 경우에는 합이 한 피연산자보다 작아지는 것은 다른 피연산자가 음수일 때, 그리고 그때뿐이라는 성질을 씁니다. 다른 피연산자가 음수인지와 합이 첫 피연산자보다 작은지를 각각 slti와 slt로 구하고, 둘이 다르면 넘침으로 판단하므로 덧셈 뒤에 명령 세 개가 더 듭니다.

폭을 늘릴 때는 부호를 복제한다

4비트 값을 8비트 레지스터로 옮길 때, 부호 없는 수는 앞을 0으로 채우는 0 확장(zero extension)을 합니다. 2의 보수 값은 맨 앞 비트를 복제해 채우는 부호 확장(sign extension)을 해야 같은 값이 유지됩니다. 4비트 −3 1101을 8비트로 옮기면 11111101이고, 출력의 다섯째 줄처럼 둘 다 −3으로 읽힙니다. 앞을 0으로 채운 00001101은 +13이 되어 값이 바뀝니다. 같은 비트 패턴이라도 부호 있는 값인지 아닌지에 따라 넓히는 방법이 달라지므로, CPU에는 두 가지 확장 명령이 따로 있습니다.

마지막 줄의 앞 값은 Python의 음수 −6을 8비트로 잘라 본 2의 보수 패턴 11111010이고, 뒤 값은 −8의 부호를 바꾸려고 뒤집고 1을 더한 결과가 다시 1000이라는 것을 보여 줍니다. Python의 정수는 폭이 없으므로 ~로 비트를 뒤집은 뒤에는 & 0b1111처럼 원하는 폭으로 잘라야 고정 폭 레지스터와 같은 결과를 얻습니다.

정리

• 음수를 나타내는 방법에는 부호와 크기, 1의 보수, 2의 보수가 있으며, 2의 보수만 0이 하나이고 범위가 $-2^{n-1}$부터 $2^{n-1}-1$까지입니다.
• 2의 보수 패턴은 맨 앞 비트가 1이면 부호 없는 값에서 $2^n$을 빼서 읽거나, 맨 앞 비트의 무게를 $-2^{n-1}$로 보아 읽습니다.
• 2의 보수는 부호 없는 수와 같은 덧셈 회로를 쓰며, 뺄셈은 한쪽 입력을 뒤집고 1을 더해 덧셈으로 바꿉니다.
• 자리올림은 부호 없는 넘침을, 오버플로는 부호 있는 넘침을 알리며, 오버플로는 부호가 같은 두 수의 합의 부호가 달라질 때 생깁니다.
• 폭을 늘릴 때 부호 없는 값은 0 확장을, 2의 보수 값은 부호 확장을 합니다.

연습 문제

1. 두 가지 넘침

4비트 덧셈 1001 + 1100을 부호 없는 수로 볼 때와 2의 보수로 볼 때 각각 수학적인 결과, 저장되는 값, 넘침 여부를 쓰세요.

2. 음수의 패턴과 부호 확장

8비트 2의 보수로 −6의 패턴을 구하고, 그것을 16비트로 부호 확장한 패턴을 16진수로 쓰세요.

3. 회로가 오버플로를 판단하는 방법

4비트 덧셈 1000 + 1000에서 맨 앞 자리로 들어간 자리올림과 맨 앞 자리에서 나온 자리올림을 구하고, 오버플로인지 판단하세요.

비트 패턴을 볼 때는 맨 앞 비트가 언제나 부호라고 단정하지 말고, 그 값을 부호 없이 다루는지 부호 있게 다루는지부터 확인해 보세요. 다음 글 소수·부동소수점·문자에서는 정수가 아닌 수와 문자를 비트로 나타내는 방법을 다룹니다.