진법과 컴퓨터의 수 표현

십진수 13과 이진수 1101은 같은 값을 다르게 적은 것입니다. 사람은 손가락이 열 개라 십진법에 익숙하지만, 컴퓨터는 전기가 흐르는지 아닌지의 두 상태로 정보를 저장하므로 이진법을 씁니다. 같은 값을 다른 진법으로 바꾸는 방법을 알면, 컴퓨터가 수를 어떻게 저장하는지와 그 저장 방식 때문에 생기는 한계도 이해할 수 있습니다. 이 글에서는 수의 체계에서 본 수들이 컴퓨터 안에서 비트로 어떻게 표현되는지, 그리고 앞 글에서 0.1 + 0.2 같은 계산에 왜 오차가 생겼는지 차례로 살펴봅니다.

자릿값으로 읽기

십진수 352는 $3\cdot100+5\cdot10+2\cdot1$입니다. 각 자리 숫자에 그 자리의 무게, 곧 $10^2$, $10^1$, $10^0$을 곱해 더한 것입니다. 일반적으로 밑이 $b$인 진법에서는 각 자리에 0부터 $b-1$까지의 숫자를 쓰고, 정수 부분의 자리 무게는 오른쪽부터 $b^0,b^1,b^2,\ldots$, 소수점 아래의 자리 무게는 $b^{-1},b^{-2},\ldots$입니다. 그래서 이진수 $(1101.01)_2$는 $8+4+1+1/4=13.25$입니다. 소수점 아래 둘째 자리의 무게는 0.01이 아니라 $2^{-2}=1/4$라는 점에 주의해야 합니다.

16진법은 0부터 9까지와, 10부터 15까지를 나타내는 A부터 F까지의 문자를 씁니다. $(2D)_{16}=2\cdot16+13=45$입니다. 16은 $2^4$이므로 16진수 한 자리는 이진수 네 자리와 정확히 맞아떨어지고, 2는 0010, D는 1101이라 $(2D)_{16}$은 이진수 0010 1101입니다. 긴 이진수를 사람이 읽기 쉽게 줄여 쓸 때 16진수를 자주 쓰는 이유입니다.

다른 진법으로 바꾸기

십진 정수를 이진수로 바꿀 때는 2로 계속 나누며 나머지를 모읍니다. 45를 2로 나누면 몫 22, 나머지 1이고, 22는 몫 11, 나머지 0, 이어서 (5, 1), (2, 1), (1, 0), (0, 1)이 나옵니다. 나머지를 마지막 것부터 거꾸로 읽으면 101101입니다. 처음 나온 나머지가 $2^0$ 자리, 곧 가장 오른쪽 자리이기 때문에 거꾸로 읽는 것입니다. 2 대신 16으로 나누면 16진수가 됩니다.

소수 부분은 반대로 2를 곱합니다. 0.625에 2를 곱하면 1.25이므로 정수 부분 1을 떼어 소수점 아래 첫째 자리로 삼고, 남은 0.25에 다시 2를 곱하면 0.5라 둘째 자리는 0, 0.5에 2를 곱하면 1.0이라 셋째 자리는 1입니다. 남은 값이 0이 되었으므로 $(0.101)_2$로 끝납니다. 이번에는 나온 순서대로 읽습니다. 2를 곱할 때마다 소수점이 한 자리씩 오른쪽으로 옮겨 가며 다음 자리가 정수 부분으로 넘어오기 때문입니다.

from fractions import Fraction


def to_base(n, base):
    digits = "0123456789ABCDEF"
    if n == 0:
        return "0"
    result = []
    while n > 0:
        n, r = divmod(n, base)
        result.append(digits[r])
    return "".join(reversed(result))


def fraction_to_binary(x, places):
    bits = []
    for _ in range(places):
        x *= 2
        bit = int(x)
        bits.append(str(bit))
        x -= bit
    return "0." + "".join(bits)


print(to_base(45, 2), to_base(45, 16), int("101101", 2), int("2D", 16))
print(fraction_to_binary(Fraction(5, 8), 4), fraction_to_binary(Fraction(1, 10), 12))

101101 2D 45 45
0.1010 0.000110011001

divmod(n, base)는 몫과 나머지를 한꺼번에 돌려줍니다. 나머지를 차례로 모은 뒤 reversed로 뒤집는 것이 손으로 거꾸로 읽은 것과 같습니다. 거꾸로, 진법으로 적힌 문자열은 int(문자열, 밑)으로 십진수 값으로 바꿀 수 있습니다. fraction_to_binary는 정확한 계산을 위해 Fraction을 받아 2를 곱하고 정수 부분을 떼는 일을 정해진 자리만큼 되풀이합니다. 5/8은 셋째 자리에서 끝나 넷째 자리가 0이지만, 1/10은 0011이 끝없이 되풀이되어 12자리로는 끝나지 않습니다. 이 사실이 뒤에서 볼 부동소수 오차의 원인입니다.

이진 덧셈의 올림

이진 덧셈도 십진 덧셈과 같은 방식으로 합니다. 다만 한 자리의 합이 2가 되면 0을 쓰고 다음 자리로 1을 올립니다. 십진법에서 합이 10이 되면 올리는 것과 같은 규칙에서, 기준이 밑인 2로 바뀌었을 뿐입니다. $(1011)_2+(0110)_2$를 오른쪽부터 계산하면 다음과 같습니다.

마지막 올림 1이 새로운 $2^4$ 자리가 되어 결과는 $(10001)_2$, 곧 17입니다. 11 + 6 = 17이므로 맞습니다. 뺄셈에서 윗자리에서 빌려 오는 값도 밑만큼입니다. $(10000)_2-1$을 계산하려면 $2^4$ 자리의 1을 빌려 아래 자리들로 내려보내야 하고, 결과는 $(01111)_2=15$입니다. 16진법이라면 F + 1 = 16이 밑에 닿으므로 $(10)_{16}$으로 올라갑니다.

비트 수가 정해진 정수

컴퓨터는 정수를 정해진 개수의 비트로 저장합니다. 비트가 $w$개이면 만들 수 있는 비트열은 $2^w$가지이므로, 0 이상의 정수만 나타낸다면 0부터 $2^w-1$까지를 담을 수 있습니다. 4비트라면 0000부터 1111까지, 곧 0부터 15까지입니다. 이렇게 0 이상의 정수만 나타내는 방식을 부호 없는 정수(unsigned integer)라고 합니다.

음수도 나타내려면 비트열의 일부를 음수에 써야 합니다. 오늘날 거의 모든 컴퓨터가 쓰는 방법은 2의 보수(two's complement)로, 가장 왼쪽 비트의 무게를 $2^{w-1}$이 아니라 $-2^{w-1}$로 읽습니다. 4비트에서 1111은 부호 없이 읽으면 15이지만 2의 보수로 읽으면 $-8+4+2+1=-1$입니다. 같은 비트열이라도 어떻게 읽기로 정했느냐에 따라 값이 다르므로, 비트열만 보고는 값을 알 수 없고 해석 방식을 함께 알아야 합니다.

2의 보수로 어떤 수의 음수를 만들려면 모든 비트를 뒤집고 1을 더합니다. 4비트에서 +3은 0011이므로, 뒤집으면 1100이고 1을 더하면 1101입니다. 1101을 2의 보수로 읽으면 $-8+4+1=-3$으로 맞습니다. 이 방법이 통하는 것은, 어떤 비트열과 그것을 뒤집은 비트열을 더하면 1111, 곧 -1이 되므로 뒤집은 값이 $-x-1$이고, 여기에 1을 더하면 $-x$가 되기 때문입니다. 4비트 2의 보수가 나타낼 수 있는 범위는 -8부터 7까지입니다.

def to_twos(value, width):
    return format(value % (1 << width), f"0{width}b")


def from_twos(bits):
    value = int(bits, 2)
    return value - (1 << len(bits)) if bits[0] == "1" else value


print(to_twos(-3, 4), to_twos(-1, 4), from_twos("1101"), from_twos("1111"))
print(to_twos(7 + 1, 4), from_twos(to_twos(7 + 1, 4)))

1101 1111 -3 -1
1000 -8

1 << width는 1을 왼쪽으로 width자리 밀어 $2^w$를 만듭니다. 음수를 $2^w$로 나눈 나머지를 구하면 그 수의 2의 보수 비트열이 나오는데, -3을 16으로 나눈 나머지 13이 이진수로 1101이기 때문입니다. from_twos는 거꾸로 맨 앞 비트가 1이면 부호 없는 값에서 $2^w$를 빼 음수로 되돌립니다.

마지막 줄은 7에 1을 더한 8을 4비트에 담으려 한 결과입니다. 8은 4비트 2의 보수의 범위 밖이라, 아래 네 비트 1000만 남고 이것은 -8로 읽힙니다. 수학에서는 7 + 1 = 8이지만 고정된 비트 수 안에서는 가장 큰 수 다음이 가장 작은 수로 돌아간 것입니다. 이처럼 계산 결과가 정해진 비트 수로 나타낼 수 있는 범위를 넘는 것을 오버플로(overflow)라고 합니다. C나 Java의 정수는 이렇게 범위가 정해져 있어서 오버플로가 일어날 수 있습니다. Java는 이때 위처럼 아래 비트만 남겨 값이 돌아가도록 정해 두었지만, C에서 부호 있는 정수가 오버플로하면 정의되지 않은 동작(undefined behavior)이 되므로 값이 돌아간다고 기대하면 안 됩니다. 반면 Python의 정수는 필요한 만큼 자릿수를 늘려 저장하므로 일반적인 계산에서는 오버플로가 일어나지 않습니다.

부동소수는 유한한 이진 소수다

실수를 저장할 때는 $1.25\times2^3$처럼 부호, 유효숫자, 지수로 나누어 저장하는 부동소수(floating-point) 방식을 씁니다. 지수 덕분에 매우 큰 수와 매우 작은 수를 함께 다룰 수 있지만, 유효숫자의 비트 수는 정해져 있습니다. Python의 float은 대부분의 컴퓨터에서 유효숫자를 53비트로 저장합니다.

그래서 이진 소수로 끝나지 않는 수는 정확히 담을 수 없습니다. 기약분수가 이진 소수로 끝나려면 분모가 2의 거듭제곱이어야 하는데, $1/10$의 분모 10에는 5가 들어 있어서 앞에서 본 것처럼 0011이 끝없이 되풀이됩니다. 그래서 0.1을 저장할 때는 53비트에서 반올림한 가장 가까운 값을 대신 저장합니다. 이것은 0.1이 무리수가 되었다는 뜻이 아닙니다. 유리수 1/10을 유한한 이진 소수로 나타낼 수 없다는 뜻입니다.

from fractions import Fraction
import math

print(0.1 + 0.2 == 0.3, 0.1 + 0.2)
print(Fraction(0.1))
print(Fraction(1, 10) + Fraction(2, 10))
print(math.isclose(0.1 + 0.2, 0.3))

False 0.30000000000000004
3602879701896397/36028797018963968
3/10
True

Fraction(0.1)은 float 0.1에 실제로 저장된 값을 정확한 분수로 보여 줍니다. 분모 36028797018963968은 $2^{55}$이고, 이 분수는 1/10보다 아주 조금 큽니다. 0.1, 0.2, 0.3이 모두 이렇게 조금씩 어긋난 값으로 저장되어 있어서, 0.1 + 0.2의 결과가 저장된 0.3과 같지 않습니다. 반면 Fraction(1, 10)처럼 처음부터 분수로 계산하면 정확히 3/10이 나옵니다.

그래서 실수를 비교할 때는 == 대신 math.isclose처럼 정해 둔 허용 오차 안에 있는지를 비교합니다. 허용 오차는 다루는 값의 크기와 단위에 맞게 정해야 합니다. 금액처럼 원 단위까지 정확해야 하는 계산에서는 float을 쓰지 않고 원 단위의 정수로 계산하거나, 십진 소수를 정확히 다루는 decimal 모듈을 씁니다.

더 깊이: 반올림의 규칙과 정수를 정확히 담는 범위

정확히 가운데인 값을 반올림하는 규칙도 하나가 아닙니다. Python의 round()는 공식 문서에 적힌 대로 두 후보가 똑같이 가까우면 짝수 쪽을 고르므로, round(0.5)와 round(-0.5)는 0이고 round(1.5)와 round(2.5)는 모두 2입니다. 가운데 값을 늘 위로 올리면 많은 값을 더할 때 결과가 한쪽으로 쏠리지만, 짝수 쪽으로 보내면 올림과 내림이 비슷하게 섞여 그 쏠림이 줄어듭니다.

같은 문서는 round(2.675, 2)가 2.68이 아니라 2.67이 되는 예도 듭니다. 앞에서 본 0.1처럼 2.675도 이진 소수로 끝나지 않아, 실제로 저장된 값이 2.675보다 아주 조금 작기 때문입니다. 반올림이 가운데 값을 어떻게 처리하든, 그 전에 이미 값이 가운데에서 비켜나 있었던 것입니다.

유효숫자가 53비트라는 것은 정수에도 한계가 된다는 뜻입니다. 절댓값이 $2^{53}$ 이하인 정수는 모두 float으로 정확히 담기지만, 그보다 크면 이웃한 두 float 사이의 간격이 2 이상으로 벌어져 홀수를 담지 못하는 구간이 생깁니다. 그래서 $2^{53}+1$을 float으로 바꾸면 $2^{53}$이 되며, 아주 큰 정수 아이디를 float으로 읽는 프로그램에서 서로 다른 아이디가 같은 값으로 바뀌는 일이 이 때문에 생깁니다.

정리

• 밑이 $b$인 진법에서 정수 부분의 자리 무게는 $b^0,b^1,\ldots$, 소수 부분은 $b^{-1},b^{-2},\ldots$이며, 16진수 한 자리는 이진수 네 자리와 맞아떨어집니다.
• 정수는 밑으로 계속 나누어 나머지를 거꾸로 읽고, 소수는 밑을 계속 곱해 정수 부분을 나온 순서대로 읽어 다른 진법으로 바꿉니다.
• 이진 덧셈은 자리의 합이 2가 되면 올리며, 십진법과 같은 규칙에서 기준만 밑으로 바뀝니다.
• $w$비트 부호 없는 정수는 0부터 $2^w-1$까지, 2의 보수는 $-2^{w-1}$부터 $2^{w-1}-1$까지를 나타냅니다. 음수는 비트를 뒤집고 1을 더해 만들며, 범위를 넘으면 오버플로가 일어납니다.
• 부동소수는 유효숫자의 비트 수가 정해져 있어 0.1처럼 이진 소수로 끝나지 않는 수를 반올림해 저장하므로, 실수는 허용 오차로 비교하고 정확해야 하는 계산에는 정수나 분수를 씁니다.

연습 문제

1. 이진 소수를 십진수로

$(10110.11)_2$를 십진수로 바꾸세요.

2. 같은 비트열을 두 가지로 읽기

8비트 11111011을 부호 없는 정수와 2의 보수 정수로 각각 읽으세요.

3. 정확히 담을 수 있는 소수

0.5, 0.25, 0.75, 0.1, 0.2 가운데 float에 정확히 저장되는 것은 무엇인가요? 그렇게 판단한 이유를 분모로 설명하세요.

진법 계산이 헷갈리면 자리마다 $b^k$의 무게를 적어 두고 다시 더해 보세요. 이 비트들이 회로에서 실제로 어떻게 저장되고 계산되는지는 컴퓨터구조 교재의 음수·보수·넘침과 소수·부동소수점·문자에서, 참과 거짓을 1과 0으로 계산하는 방법은 부울 대수에서 다룹니다. 다음 장의 명제와 논리 연산에서는 참과 거짓을 판단하는 문장을 다루기 시작합니다.