[Parallel Computing] (4-1) Binary Representation

이번 글에서는 Binary Representations에 대해서 알아보겠다.
 
 n-bit을 이용하면, 2^n개의 서로 다른 binary 숫자를 표현할 수 있다. 부호가 없는 바이너리 숫자인 경우, 0을 포함하여 2^n개의 양수로 표현 가능하다. 그러나 부호가 있는 바이너리 숫자인 경우, 음수, 0, 양수를 모두 표현해야 한다. 일반적으로 MSB(Most Significant Bit)은 부호를 나타내는 bit으로 사용하고, 나머지는 해당 숫자의 크기를 나타낸다. 컴퓨터 하드웨어를 가능하면 간단하게 만들기 위하여 2's complement 표현 방법을 주로 사용한다. 왜 2's Complement를 사용하면 하드웨어가 간단해지는지 차근차근 설명해도록 하겠다. 
 부호가 있는 바이너리를 표현하는 방법에는 여러 가지가 있다. 'Signed magnitude representation'은 MSB를 음수와 양수를 구분하는 비트(0:양수, 1:음수)로 사용하고, 나머지 비트들은 절대값 크기를 나타낸다. 'Complement number system'을 이용하는 1's/2's complement representation 방식이 있다. Complement number system은 해당 숫자의 보수(보충을 해주는 수)를 취하여 음수를 표현하는 방법이다. 예를 들어 10이 되기 위한 3의 보수 값은 3에 7만큼의 보충을 해줘야 10이 되므로 7이다. 1's/2's는 어떤 값을 만들기 위한 보수 체계를 쓰는 것이냐 따라 달라진다. 
 r's complement는 x' = (r^n - x) 이다. 그리고 (r-1)'s complement는 x' = (r^n - 1) -x로 표현된다. 
(이때, x는 숫자이며, n은 자릿수를 의미한다.) 
 예를 들어 r=2인 2's complement는 x2' = (2^n - x)이고, 1's complement는 x1' = (2^n - 1) -x로 표현된다. 2's complement의 수식을 잘 살펴보면 x' = (2^n-x) = (2^n - 1) -x + 1  = x1' + 1로 표현될 수 있다. 즉 1's complement로 표현된 숫자에 +1을 수행하면 2's complement를 구할 수 있다. 
 그럼 (r-1)'s complement를 구하는 방법을 더 알아보면, 아래와 같이 수식으로 표현될 수 있다. 
(r^n -1) - x = (r^n - 1^n) - x = (r-1)*(r^(n-1)+r^(n-2)+...+r^0) - x = (r-1) * r^(n-1) + (r-1) * r^(n-2) +... + (r-1) * r0 - x
예를 들어 decimal 값인 765의 (10-1)'s complement 값은 (10^3-1) - 765 = 999 - 765 = 234가 된다. 여기에 +1을 수행하면 235가 되고 이 숫자가 10's complement가 된다. 
 수식을 아래와 같이 다시 잘 살펴보면 각 자리수에서 r-1 값을 빼주면 쉽게 숫자를 계산할 수 있다. x를 [xn-1, xn-2, xn-3,... , x0]으로 자릿수마다 표현할 때 [(r-1) - xn-1] [(r-1) - xn-2] [(r-1) - xn-3].... [(r-1) - x0]으로 나타낼 수 있다. 
1's complement representation의 예시로 살펴보면, decial 6의 1's complement는 (2^4-1) - 6 = 15 - 6 = 9 이렇게 계산할 수도 있고, dicimal 6은 binary 0110이고 각 자리수를 1로 빼면 1001이 된다. binaray 1001은 decimal 9와 값이 같다. 
그럼 표현할 수 있는 숫자의 범위가 얼마나 되는 지 살펴보자. 예를 들어 3-bit 1's complement represenation에서의 숫자 표현은 아래와 같다.
000 :: 양수, 0
001 :: 양수, 1
010  :: 양수, 2
011  :: 양수, 3
100  :: 음수, -3 
101  :: 음수, -2
110  :: 음수, -1
111  :: 음수, 0
먼저 양수 값을 나열하고, 이에 대한 보수값을 취해서 값을 설정하였다. 숫자의 범위는 -3에서부터 +3까지 표현할 수 있다. 특이한 점은 0을 표현하는 방식이 양수 0, 음수 0으로 두 가지 방식이 존재한다. 0을 표현하는 방식은 하나만 있어도 충분하므로 이는 불필요한 방식이다. 
 위의 예시를 2' complement representation으로 표현해 보자. 마찬가지로 먼저 양수를 나열하고, 이에 대한 보수값을 취해서 값을 설정하였다. 
000 :: 양수, 0
001 :: 양수, 1
010  :: 양수, 2
011  :: 양수, 3
100  :: 음수, -4 
101  :: 음수, -3
110  :: 음수, -2
111  :: 음수, -1
순차적으로 표현을 하다보면 100을 표현할 수 있는 양수의 보수가 없는 것을 확인할 수 있다. 이 값을 정하기 위하여 살펴보면 우선 MSB가 음수이기 때문에 음수표현만 가능하므로 -3 다음 수인 -4로 정하여 표현한다.
 이를 정리하면 1's complement representation의 숫자 표현 범위는 -2^(n-1)-1 <= x <= 2^(n-1) - 1이고, 2's complement representation의 숫자 표현 범위는 -2^(n-1) <= x <= -2^(n-1) -1이다. 
 
다음 글에서는 다양한 Arithmetic Operation에 대해서 다루겠다.