진법과 고정 길이 정수

8비트 센서가 11001010이라는 비트 패턴을 보냈다면 이것은 십진수로 얼마일까요? 패턴을 수로 읽으려면 자리마다 무게를 붙여 더하면 됩니다. 그런데 컴퓨터의 레지스터는 비트 수가 정해져 있어서, 수학에서는 문제없는 계산도 결과가 자리를 넘으면 일부를 잃습니다. 이 글에서는 비트 패턴을 부호 없는 정수(unsigned integer)로 읽는 방법과, 정해진 폭 안에서 덧셈, 시프트, 곱셈, 나눗셈이 어떻게 동작하는지 다룹니다. 같은 패턴을 음수로 읽는 방법은 다음 글에서 다룹니다.

자리값으로 읽기

십진수 203은 $2\times10^2+0\times10^1+3\times10^0$입니다. 이진수도 밑이 10에서 2로 바뀔 뿐 같은 방식으로 읽습니다. 오른쪽 끝 자리부터 무게가 1, 2, 4, 8, 16, 32, 64, 128이므로 $11001010_2=128+64+8+2=202$입니다. 아래 첨자 2는 이진수라는 표시일 뿐, 저장된 데이터에 들어 있는 것은 아닙니다.

십진수를 이진수로 바꿀 때는 2로 나누어 나머지를 적는 일을 몫이 0이 될 때까지 반복하고, 나머지를 마지막 것부터 읽습니다. 13은 13 = 2 × 6 + 1, 6 = 2 × 3 + 0, 3 = 2 × 1 + 1, 1 = 2 × 0 + 1이므로 1101입니다. 8 + 4 + 1 = 13으로 거꾸로 확인할 수 있습니다. 진법을 바꾸는 방법과 그 이유는 이산수학 교재의 진법과 컴퓨터의 수 표현에서 더 자세히 다룹니다.

16진수(hexadecimal)는 0부터 9까지의 숫자와 A부터 F까지의 문자로 0부터 15까지를 나타냅니다. 이진수 4자리가 0부터 15까지를 나타내므로, 이진수를 오른쪽부터 4비트씩 끊으면 16진수 한 자리씩이 됩니다. 1100 1010은 C와 A라서 $\text{CA}_{16}$이고, 코드에서는 흔히 0xCA로 씁니다. 8진수는 한 자리가 3비트이므로 오른쪽부터 3비트씩 끊고 모자라는 왼쪽은 0으로 채워 011 001 010, 곧 312입니다. 긴 비트 패턴을 사람이 읽기 쉽게 줄여 적을 때 16진수를 많이 씁니다.

정해진 폭에서 넘친 자리는 사라진다

4비트 부호 없는 정수는 0000부터 1111까지, 곧 0부터 15까지를 나타냅니다. 1011 + 0110은 수학적으로 11 + 6 = 17이고 이진수로 10001이지만, 4비트 레지스터에는 아래 네 자리 0001만 남고 맨 앞의 1은 자리올림(carry)으로 밖으로 나갑니다. 저장된 값 1만 보고 덧셈이 맞았다고 판단하면 안 됩니다. x86이나 ARM 같은 많은 CPU는 이렇게 밖으로 나간 자리올림을 따로 플래그에 기록해 두어, 프로그램이 결과가 넘쳤는지 확인할 수 있게 합니다.

n비트 부호 없는 덧셈은 수학적인 합을 $2^n$으로 나눈 나머지를 남기는 셈입니다. 17을 16으로 나눈 나머지가 1인 것과 같습니다. 그래서 n비트 결과는 합이 $2^n$보다 작을 때만 수학적인 합과 같습니다.

비트를 한 칸씩 옆으로 옮기는 연산을 시프트(shift)라고 합니다. 부호 없는 값을 왼쪽으로 한 칸 시프트하면 2를 곱한 것과 같고, 오른쪽으로 한 칸 논리 시프트하면 2로 나눈 몫과 같습니다. 다만 왼쪽 시프트도 폭을 넘으면 맨 앞 자리가 사라집니다. 4비트 1100, 곧 12를 왼쪽으로 한 칸 옮기면 11000에서 앞자리가 사라져 1000, 곧 8이 되어 12 × 2 = 24가 아닙니다.

곱셈과 나눗셈에 필요한 폭

곱셈은 결과가 훨씬 커질 수 있습니다. 4비트 부호 없는 수의 최댓값은 15이므로 두 수의 곱은 많아야 15 × 15 = 225이고, 이것은 8비트에 들어갑니다. 일반적으로 n비트 두 수의 곱은 $(2^n-1)^2<2^{2n}$이라서 2n비트가 있으면 항상 담을 수 있습니다. 그래서 많은 CPU는 곱셈 결과를 두 배 폭의 레지스터 쌍에 남깁니다.

이진수 곱셈은 손으로 하는 십진수 곱셈과 같지만 더 단순합니다. 곱하는 수의 각 비트가 1이면 곱해지는 수를 그 자리만큼 시프트해서 더하고, 0이면 건너뜁니다. $101_2\times11_2$, 곧 5 × 3은 3의 0번 비트와 1번 비트가 1이므로, 5와 5를 한 칸 옮긴 10을 더해 $1111_2=15$입니다. 회로는 이 시프트와 덧셈을 반복하거나 한꺼번에 처리해 곱셈을 합니다.

나눗셈 13 ÷ 3은 몫 Q = 4와 나머지 R = 1을 냅니다. 이 둘은 13 = 3 × 4 + 1, 그리고 $0\le R<3$이라는 관계로 정해집니다. 나누는 수가 2의 거듭제곱이면 나눗셈이 더 간단해집니다. $2^k$로 나눈 몫은 오른쪽으로 k칸 시프트한 값이고, 나머지는 아래 k비트만 남긴 값입니다. 이 성질은 캐시에서 주소를 여러 부분으로 나눌 때 다시 쓰입니다.

width = 4
mask = (1 << width) - 1


def add(a, b):
    total = a + b
    return total & mask, total >> width


print(add(0b1011, 0b0110))
print(format((0b1100 << 1) & mask, "04b"), 0b1100 >> 1)


def multiply(a, b):
    product = 0
    for i in range(width):
        if (b >> i) & 1:
            product += a << i
            print(f"{i}번 비트가 1: {a:04b}을 {i}칸 옮겨 더함 → {product:08b}")
    return product


print(multiply(0b0101, 0b0011))
print(divmod(13, 3), divmod(45, 8), 45 >> 3, 45 & 0b111)

(1, 1)
1000 6
0번 비트가 1: 0101을 0칸 옮겨 더함 → 00000101
1번 비트가 1: 0101을 1칸 옮겨 더함 → 00001111
15
(4, 1) (5, 5) 5 5

1 << width는 1을 왼쪽으로 4칸 옮긴 16이고, 여기서 1을 뺀 mask는 아래 네 비트가 모두 1인 1111입니다. & mask는 아래 네 비트만 남겨 4비트 레지스터에 담기는 값을, >> width는 그 위로 넘친 자리올림을 꺼냅니다. 첫 줄은 11 + 6이 저장값 1과 자리올림 1이 된다는 것을, 둘째 줄은 12를 왼쪽으로 시프트하면 4비트에서 8이 되고 오른쪽으로 시프트하면 6이 된다는 것을 보여 줍니다. multiply는 곱하는 수의 비트를 하나씩 보면서 시프트한 값을 더하는 과정을 출력하고, 마지막 줄은 45를 8로 나눈 몫과 나머지가 3칸 시프트와 아래 3비트로도 똑같이 나온다는 것을 보여 줍니다. Python의 정수는 크기 제한이 없으므로, 고정 폭을 흉내 내려면 이처럼 mask로 직접 잘라야 합니다.

더 깊이: RISC-V의 곱셈과 나눗셈 명령

RISC-V의 M 확장은 두 배 폭의 곱을 레지스터 쌍에 한꺼번에 남기지 않고 명령 둘로 나눕니다. mul은 레지스터 폭(XLEN)의 두 수를 곱한 2×XLEN비트의 결과 가운데 아래 XLEN비트를, mulhu는 부호 없는 곱의 위 XLEN비트를 돌려줍니다. 부호 있는 곱에는 mulh를, 한쪽만 부호 있는 곱에는 mulhsu를 씁니다. 규격은 위와 아래가 모두 필요하면 같은 피연산자로 mulh와 mul을 이어 쓰라고 권하는데, 그러면 마이크로아키텍처가 두 명령을 곱셈 하나로 합쳐 실행할 수 있기 때문입니다.

나눗셈에서는 0으로 나누는 경우가 눈에 띕니다. RISC-V는 0으로 나누어도 예외를 일으키지 않고, 몫으로 모든 비트가 1인 값을, 나머지로 나누어지는 수를 그대로 돌려줍니다. 규격은 예외를 두면 이것이 표준 ISA에서 유일한 산술 트랩이 된다는 점을 이유로 듭니다. 또 0으로 나누면 곧바로 예외로 넘어가야 하는 언어라도, 나눗셈 뒤에 거의 언제나 건너뛰지 않는 분기 명령 하나만 넣으면 되므로 실행 비용이 작다고 설명합니다.

정리

• 이진수는 오른쪽 끝부터 1, 2, 4, 8, … 의 무게를 붙여 더해 읽고, 16진수 한 자리는 4비트, 8진수 한 자리는 3비트에 대응합니다.
• n비트 부호 없는 정수는 0부터 $2^n-1$까지를 나타내며, 덧셈 결과가 이 범위를 넘으면 넘친 자리는 자리올림으로 빠지고 나머지만 남습니다.
• 부호 없는 값의 왼쪽 시프트는 2를 곱하고 오른쪽 논리 시프트는 2로 나눈 몫을 내지만, 폭을 넘는 자리는 사라집니다.
• n비트 두 수의 곱은 2n비트에 담기며, 이진 곱셈은 시프트와 덧셈의 반복입니다.
• 나눗셈의 몫과 나머지는 나누어지는 수 = 나누는 수 × 몫 + 나머지, 그리고 나머지가 0 이상이고 나누는 수보다 작다는 조건으로 정해지며, $2^k$로 나누는 것은 시프트와 마스크로 할 수 있습니다.

연습 문제

1. 저장되는 값과 수학적인 값

6비트 부호 없는 레지스터에서 45 + 27을 계산합니다. 수학적인 결과, 저장되는 비트 패턴과 값, 자리올림을 구하세요. 이어서 29를 8로 나눈 몫과 나머지를 관계식과 함께 쓰세요.

2. 세 가지 진법으로 적기

0xCA를 이진수, 십진수, 8진수로 바꾸세요.

3. 곱셈 결과의 폭

8비트 부호 없는 정수 두 개를 곱한 결과를 항상 담으려면 몇 비트가 필요한가요?

결과가 이상하면 계산 전에 레지스터의 폭과 범위를 먼저 적어 두고, 넘친 자리가 어디로 갔는지 따라가 보세요. 다음 글 음수·보수·넘침에서는 같은 비트 패턴을 부호 있는 정수로 읽고, 자리올림과 부호 있는 넘침이 어떻게 다른지 다룹니다.