Signed and Unsigned Numbers | Two's Complement

Base

컴퓨터가 숫자를 어떻게 나타낼까? 사람은 보통 숫자를 셀 때 10진법(Base 10)을 사용한다. 아래 예시를 보자

123 = 1111011

놀랍게도 이 둘은 같은 숫자이다. 물론, 123은 base 10, 즉 10진법을 이용해 나타내었고, 1111011은 base 2, 즉 2진법을 이용해 나타내었다. 앞에서 말했듯, 컴퓨터의 트랜지스터는 0과 1만 표현할 수 있다. 그렇기때문에 모든 정보는 binary digit, 즉 bit로 구성된다. 어떤 기수의 숫자이든, 이 숫자를 구하려면 아래와 같이 계산할 수 있다.

$$ d * Base^i $$

여기서 i 는 0부터 시작해서 왼쪽으로 갈수록 1씩 증가한다. 예를들어 아래 binary bit를 base10 으로 계산해보자

$ 1011_{two} \\
= (1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (1 * 2^0) \\
= (1 * 8) + (0 * 4) + (1 * 2) + (1 * 1) \\
= 8 + 0 + 2 + 1 \\
= 11 $

 

RISC-V의 double word의 길이는 64 비트이므로, $2^64$가지의 패턴을 나타낼 수 있는데, 0부터 시작하면 $2^64 - 1$까지 나타낼 수 있다. 앞의 0은 생략하곤 하지만, 0을 표현하면 아래와 같다.

$ {00000000\;
00000000\;
00000000\;
00000000\;
00000000\;
00000000\;
00000000\;
00000000} $

그리고 RISC-V에서 가장 큰 숫자는 아래와 같은데 이는 18,446,744,073,709,551,615 라는 아주 커다란 숫자이다.

$ {11111111\;
11111111\;
11111111\;
11111111\;
11111111\;
11111111\;
11111111\;
11111111} $

그런데 이 제일 큰 숫자에 1을 더하면 어떻게 될까? 이런 경우, 표현이 불가능하게 되어서 overflow가 발생했다고 말한다. 

 

Two's Complement

https://slideplayer.com/slide/5062097/

그런데, 프로그램을 생각했을 때, 컴퓨터는 양수와 음수를 모두 계산한다. 그렇다면 이것을 어떻게 표현할 수 있을까? 여러가지 대안속에서, 0들이 앞에 나요면 positive, 1들이 앞에나오면 negative로 표현하는 two's complement 표현법이 등장한다. 

 

전체 숫자의 절반인 0부터 $2^63-1$까지는 앞에서 설명한것과 같은 방식으로 숫자를 나타내지만, 그다음 비트(가장 왼쪽자리의 비트가 1인)부터 시작한 비트 패턴은 -1부터 시작해서 가장 큰 음수 $-2^63$까지를 나타낸다. 양수에는 0을 포함하기때문에는 음수와 매칭이 되지 않는 음수(-9,223,372,036,854,775,808)가 존재한다. 프로그램을 할 때, 이것이 문제였지만, 현재까지도 모든 컴퓨터는 이 방식으로 숫자를 표현하고 있다. 이 방식은 굉장히 효율적이다. 왜냐하면 Most Segnificant Bit, 그러니까 가장 왼쪽에 자리하는 bit만 확인하면 음수인지(0) 양수인지(1)판별할 수 있기 때문이다. 아래 문제를 보자

 

이 Two's Complement의 계산법은 처음에는 조금 헷갈릴 수 있는데, MIT에서 무료로 제공하는 유투브 채널에서 쉽게 설명해주고 있다.

Binary to Decimal Conversion

What is the decimal value of this 64-bit two’s complement number?

$ 11111111\;
11111111\;
11111111\;
11111111\;
11111111\;
11111111\;
11111111\;
11111111_{two}
$

아래와 같이 계산할 수 있다.

$
(1 * -2^{63}) + (1 * 2^{62}) + (1 * 2^{61}) + ... + (1 * 2^2) + (1 * 2^1) + (1 * 2^0) \\
= -2^{63} + 2^{62} + 2^{61} + ... + 2^2 + 0 + 0 \\
= -4_{ten}
$

 

2를 -2로 바꾸거나, 1232를 -1232로 바꾸었을 때, 비트를 계산하는 방법, 즉 sign extention을 하는 방법에 대해 알아보기 위해 다음 문제를 보자.

Negation Shortcut

Negate $ 2_{ten} $, and then check the result by negating $ -2_{ten} $.

$2_{ten}$은 다음과 같이 나타낼 수 있다.

$ 00000000\;
00000000\;
00000000\;
00000000\;
00000000\;
00000000\;
00000000\;
00000010_{two} $

이 숫자를 negate 하려면, 모든 bit를 뒤집어준 후, 1을 더해주면 된다.

다시, 뒤집어주려면, 똑같이 모든 비트를 뒤집어준 후, 1을 더해주면 된다.

 

 

그렇다면, bit의 길이가 다른 숫자는? 다음 문제를 보자.

Sign Extension Shortcut

Example

Convert 16-bit binary versions of 2_{ten} and −2_{ten} to 64-bit binary numbers.

 

2와 -2가 있는데 이는 16-bit binary version으로 되어있고, 이를 64-bit로 변환하라는 문제이다. 먼저 2를 16-bit로 표현하자.

$00000000\;00000010_{two} = 2_{ten}$

 

Most Significant Bit, 즉 맨 왼쪽에 있는 0을 48번 복사하고, 더블워드(64-bit)의 오른쪽 16비트는 기존과 같이 복사하면 64bit의 이진수로 만들 수 있다. 

$00000000\;00000000\;00000000\;00000000\;00000000\;00000000\;00000000\;00000010_{two} = 2_{ten}$

 

그렇다면, 16bit의 2를 부호를 바꿔서 -2를 하려면, 다음과 같이 모든 부호를 바꿔준 후 1을 더하면 된다.

 

그 후, 64-bit로 변환하려면, MSB(Most Significant Bit), 맨 왼쪽의 1을 48번 복사해서 왼쪽에 넣고, 오른쪽 16자리는 그대로 복사해서 넣어주면 된다. 최종 값은 아래와 같다.

$
11111111\;
11111111\;
11111111\;
11111111\;
11111111\;
11111111\;
11111111\;
11111110_{two} \\
= −2_{ten}
$

 

 

Reference

David A. Patterson and John L. Hennessy. 2013. Computer Organization and Design, Fifth Edition: The Hardware/Software Interface (5th. ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

 

LaTeX help 1.1 - Spacing in Math Mode