[CS] 컴퓨터의 음수 표현 (ft. Complement)

 

늘 알고 있다고 생각하지만, 

조금만 호벼파보면 얼마 못가서 그 얕음이 낱낱이 드러나는 파트가 또 이 부분이 아닐까 싶다ㅠ

 

확실히 이해하고자 스스로 정리하는 컴퓨터의 음수 표현 (ft. 보수)

 

 

 

 

 

 

 

0. 보수

보수는 영어로 complement, 즉 '보충' 해주는 수 다.

 

이 수를 좀 더 깊이 이해하기 위해선 진법을 이해해야 하는데,

N진법에서 보수를 이야기함에 있어서는 크게 N의 보수와 N-1의 보수로 나누어 볼 수 있다.

 

사전적 정의를 풀어보며 출발하자면 다음과 같다

어떤 수 a에 {무언가}를 더했을 때, 깔끔한 [N진법의 수]를 만들어 냈다면

                                                                    -> 그 {무언가}를 'a의 N의 보수'라고 부르자

어떤 수 a에 {무언가}를 더했을 때, 깔끔한 [N진법의 수 - 1]를 만들어 냈다면

                                                                    -> 그 {무언가}를 'a의 N-1의 보수'라고 부르자

 

좀 더 쉽게 대입해보자, 10진법

어떤 수 4에 {무언가}를 더했을 때, 깔끔한 [10]을 만들어 냈다면

                                                                    -> 그 {무언가, 6} 을 '4의 10의 보수'라고 부르자

어떤 수 4에 {무언가}를 더했을 때, 깔끔한 [9]를 만들어 냈다면

                                                                    -> 그 {무언가, 5} 를 '4의 9의 보수'라고 부르자

 

연장 시켜보자

423 + ? = 1000    ->   577은 423의 10의 보수

423 + ? = 999     ->    576은 423의 9의 보수

라고 이해하면 되겠다

 

후를 위해 좀 더 나아가보자면,

보수를 b라고 했을 때 (bosu의 약자 b 아님 주의)

423 + b100 = 1000

           b100 = 1000 - 423   ... (1)

 

423 + b99 = 999

                   = (1000 - 1)

           b99 = 1000 - 423 - 1   ... (2)

           b99 = b100 - 1   from (1)

                   or

          b100 = b99 + 1

 

N의 보수는 N-1의 보수에 1을 더한 값

=

N-1의 보수는 N의 보수에 1을 제한 값

으로 이해할 수 있겠다

 

 

 

 

 

 

1. SMR

컴퓨터에서 처음 bit를 활용한 수를 표현하기 시작하면서

맨 앞자리 bit를 부호로 활용하는 SMR (Signed magnitude reporesentation)이 개발되었다

2번째~n번째 bit는 그대로 활용하되, MSB에 따라 양/음을 결정하는 방식이다

 

0000     0

0001     1

0010     2

...

0110     6

0111     7

1000    -0

1001    -1

...

1110    -6

1111     -7

 

대략 2진법의 표현 순서상 0~7 -> -0~-7 순으로 진행된다

 

이 표현방식은

• +0, -0이 존재
• MSB를 확인하고 음수임을 인지한 후 계산해야하는 번거로움
• 또한 뺄셈을 위한 별도의 뻴셈기를 만들어야 하는 번거로움 (위에랑 같은건가;)
• 음수의 두 수 비교연산에 다소 어려움 (-2 > -3   ->  1010 < 1011) 

와 같은 단점을 갖고 있었다 

 

 

 

 

 

 

2. 1's Complement

(누구의 아이디어였는지) bitwise NOT을 활용하여 음수를 표현하자는 획기적인 제안...

 

더해서 111...11을 만드는 맞대응의 1의 보수를 음수로 치게 되면 다음과 같이 표현되는데

 

0000     0

0001     1

0010     2

...

0110     6

0111     7

1000    -7

1001    -6

...

1110    -1

1111    -0

 

2진법의 표현 순서상 0~7 -> -7~-0 의 대칭 형태로 나타난다

 

• +0, -0이 여전히 존재
• 뺄셈을 음수의 덧셈으로 전환할 수 있음 (1의 보수 계산 후 덧셈)
• 각 1의 보수와 더했을 때, -0(111...11)이 나옴
• 음수 역시 내려가면서 커지므로 음수 간 비교연산도 용이

의 특징을 가질 수 있는데,

 

 

또 하나 특이한 점이라면 덧셈 후 표현 범위 외로 벗어나는 Carry가 발생했을 경우,

이를 그대로 LSB에 하나 더해주는 형태를 취해야 정확한 수식의 답을 얻을 수 있다

(이 carry를 end-around carry라고 부름)

 

 

이 부분을 조금 더 설명하자면,

 

0000     0

0001     1

0010     2

...

0110     6

0111     7

1000    -7

1001    -6

...

1110    -1

1111    -0

0000    0

0001    1

0010    2

...

0110    6

0111    7

 

계속 1씩 더해가며 두 cycle을 붙여 표현하면

계속 숫자가 커나가는 것을 알 수 있는데, (7 -> -7 일단 제외)

 

1111 (-0)에서 0000 (+0)으로 더해져 넘어가는 상황에서

더했는데, -0에서 0이 되어버리는 셈이므로,

이 때에는                                               ( = 즉 end-around carry가 발생했을 때에는 )
1을 한번 더 더해주는 것으로 하자    ( = carry를 LSB에 더하자 )

는 보완 규칙을 얻어낼 수 있었다.

 

 

 

 

 

 

 

 

3. 2's Complement

1945년에 노이만이 처음 제안한 2의 보수

 

앞서 살펴 보았듯이,

2의 보수는 1의 보수에 1을 더한 값으로 simplify할 수 있다

 

곧,

 

0000 0

0001 1

0010 2

...

0110 6

0111 7

1000 -8

1001 -7

...

1110 -2

1111 -1

 

표현할 수 있는 음수의 범위가 하나씩 밀려 늘어나게 되면서

순서대로 보자면, 0~7  -> -8~-1의 순서로 표현이 가능하다

 

이 아이는, 

• 0이 오직 1개만 존재 (00...00)
• 여전히 뻴셈을 음수의 덧셈으로 전환할 수 있음 (2의 보수 계산 후 덧셈)
• 각 2의 보수와 더했을 때, 온전한 0 (00...00)이 나옴
• 역시 음수간 비교도 가능
• 심지어 -1 다음에 0이 순환형태로 표현되므로 계산 시,
  end-around carry를 신경쓸 필요 없음

 

 이 결과, 현대의 컴퓨터(라고 해봐야 1945년 부터;)는 2의 보수를 실제 정수 표현에 사용하고 있다.

 

 

 

 

2의 보수를 통한 표현을 쓰면서 몇 가지 확실한 특성과 재미난 일이 있다.

 

• n bit로 표현 가능 범위는 +2^(n-1)-1 ~ 0 ~ -2^(n-1)  (음수가 하나 더 많이 표현 가능)
• 100....00이 가장 작은 (음)수를 나타냄 (순환하는 형태를 이해하자)
• 가장 작은 (음)수의 절대값을 씌우면 자기 자신이 리턴된다 (!!!)

 

abs 함수는 2의 보수를 만들어 리턴하도록 대부분 설계되어있다 (당연한 이야기?)

100...00 의 2의 보수는 1의 보수에 1을 더하는 값이므로

 

011...11 + 1 = 100...00 

 

 

본인 자신이 된다 ㅋ

(순환 형태를 꼭 기억하자... 1의 보수는 데칼코마니 대칭, 거기에 1칸 아래로)

 

 

 

재미지네 ㅋㅋ 보수 ㅋㅋ