진법과 보수

본 포스팅은 ‘Mano의 컴퓨터시스템구조’ 교재를 참고했습니다.

진법

N진법은 수를 셀 때 자릿수가 올라가는 단위를 기준으로 하는 셈법으로, 위치적 기수법이라고도 한다.

우리가 일반적으로 수를 셀 때는 10진법을 사용한다. 시계에서 시간은 12진법을, 분은 60진법을 사용한다. 진법은 분명히 표시하기 위해 다음과 같이 첨자를 붙이기도 한다.

$$ (101101)2 = (45){10} $$

2진법 (Binary)

2진법은 0과 1이라는 두개의 숫자만을 사용하여 수를 나타내는 것이다. 2가 되는 순간 자리올림이 발생한다.

$$ (1011)_2=\mathtt{0b1011} $$

10진법 (Decimal)

우리가 가장 일반적으로 사용하고 있는 기수법으로, 한 자리에 0~9의 숫자로 나타낸다. 9를 넘어서면 자리올림이 발생한다.

$$ 724.5 = 7 \times 10^2 + 2 \times 10^1 + 4 \times 10^0 + 5 \times 1010^{-1} $$

16진법 (Hexadecimal)

0~F까지 사용한다. 컴퓨터 분야에서 1바이트의 크기를 쉽게 표현할 수 있어 많이 사용된다.

$$ (5A)_{16}=\mathtt{0x5A} $$

컴퓨터는 십진수를 이진화 집진법(BCD)의 형태로 저장하고 표현한다.

진법의 변환

10진수 -> N진수

10진수를 N으로 나누고, 나머지를 기록한다.
나머지를 기록한다. (뒤에서 앞으로)
나눈 몫이 N보다 작으면 멈춘다.
마지막 몫을 기록한다.

N진수 -> 10진수

1의 자리수부터 N의 0승, N의 1승, … 이렇게 차례대로 곱하여 더해주면 된다.

$$ (1011)_2 = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 11 $$

이를 수식으로 일반화하면 아래와 같다.

$$ (a_k a_{k-1} \cdots a_1 a_0)N = \sum{i=0}^{k} a_i \times N^i = (x)_{10} $$

진법 변환 C++ 구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int charToInt(char c) {
    if (c >= '0' && c <= '9') {
        return c - '0';
    } else {
        return c - 'A' + 10;
    }
}

char intToChar(int num) {
    if (num >= 0 && num <= 9) {
        return char('0' + num);
    } else {
        return char('A' + num - 10);
    }
}

int convertToDecimal(const string &num, int base) {
    int decimal = 0;

    for (int i = 0; i < num.length(); ++i) {
        decimal += charToInt(num[i]) * pow(base, num.length() - i - 1);
    }

    return decimal;
}

string convertFromDecimal(int num, int base) {
    string ret;
    while (num > 0) {
        ret += intToChar(num % base);
        num /= base;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

보수

보수(compleement)는 디지털 컴퓨터에서 뺄셈 연산과 논리 계산에 사용된다. $r$진법에는 $r$의 보수와 $(r-1)$의 보수가 있다.

(r-1)의 보수

일반적으로 $r$진법의 $n$자리수의 수 $N$에 대하여, $(r-1)$의 보수는 $(r^n-1)-N$으로 정의된다. 예를 들어 10진수 $546700$에 대한 9의 보수는 $999999 - 546700 = 453299$이다. 이진수에서 1의 보수는 각 자리 수를 뒤집는 것이다.

r의 보수

일반적으로 $r$진법의 $n$자리수의 수 $N$에 대하여, $r$의 보수는 $N \neq 0$일 때 $r^n-N$이고, $N=0$일 때는 0으로 정의된다. $r$의 보수는 $(r-1)$의 보수에 1을 더한 것과 같다.

보수의 대칭

어떤 수에 대한 보수를 다시 보수화하면 원래 수가 된다.

$r^n-(r^n-N)=N$이고, $(r^n-1)-((r^n-1)-N)=N$ 이므로, 보수의 대칭성을 만족하는 것을 확인할 수 있다.

부호 없는 숫자의 뺄셈

$r$진수 부호 없는 두 $n$자리수 사이의 뺼셈 $M-N(N \neq 0)$은 다음과 같이 계산된다.

피감수 $M$에 감수 $N$에 대한 $r$의 보수를 더한다. $M+(r^n-N)=M-N+r^n$
$M \geq N$이라면, 위의 값은 end캐리 $r^n$을 만들어내고, 이를 무시하면 $M-N$을 얻을 수 있다.
$M < N$이라면, 위의 값은 end캐리를 만들어내지 않고 그 값은 $r^n-(N-M)$이다. 이것은 $(N-M)$에 대한 $r$보수이므로, 이것에 대한 $r$의 보수를 취하고 앞에 뺄셈 기호를 붙여 뺼셈을 할 수 있다.