2진수의 덧셈과 2의 보수(complement, 補數)

Contents

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_1.html

컴퓨터는 비트 패턴을 사용해서 여러가지 다양한 종류의 데이터를 표현한다. 데이터에 다양한 연산(演算,operations)을 수행할 수 있다. 컴퓨터는 비트 패턴으로 연산을 수행 한다. 비트패턴으로 표현하는것을 체계적으로 잘 설계 하였다면 비트 패턴으로 데이터를 표현할 수 있고 그 비트패턴을 조작함으로 데이터에 연산(operation)을 수행할 수 있다.

이 장에서는 2진수 덧셈 알고리듬의 예를 다루고 있다. 덧셈 알고리듬을 공부한 후, 두 정수를 표현하는 두 개의 비트 패턴이 정수의 합을 표현하는 세번째 패턴을 만들기 위해 어떻게 조작되는지를 알 수 있을 것이다.

장의 주제

• 1 비트 바이너리 덧셈표 Single-bit Binary Addition Table.
• 2진수 덧셈 알고리듬 Binary Addition Algorithm.
• 16진수 덧셈하기 Addition in Hexadecimal Representation.
• 오버플로우 Overflow
• 정수 표현법(음수와 양수를 표현하는) 또는 사인 메그너튜드 표현법 Sign-magnitude Representation.
• 2의 보수 표현법 Two's complement Representation.
• 2의 보수 표현법에서 반전(negate)하는법 How to negate an integer in Two's Complement Representation.
• 2의 보수에서 사인 비트 The two's compement sign bit.
• 언사인드 2진수에서 오버플로우 감지하기 Overflow detection in unsigned binary.
• 2의 보수 2진수에서 오버플로우 감지하기 Overflow detection in two's complement binary.

대부분 프로세서는 2진수 덧셈 알고리듬을 연산 로직 유닉(ALU arithmetic logic unit)의 일부분으로써 기계적으로 구현한다. 전자학(digital electronics) 수업과정에서 이것이 어떻게 기계적으로 구현되는지 자세히 배울 수 있을것이다. 이 장에서는 알고리듬의 원리만 공부한다.

질문: 다음을 계산해서 답을 2진수로 써보자.

• 0 + 0 = ?
• 0 + 1 = ?
• 1 + 0 = ?
• 1 + 1 = ?

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_2.html 참조 : http://richardbowles.tripod.com/dig_elec/chapter3/chapter3.htm

답:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 10

대부분의 컴퓨터에서 비트 패턴을 조작하는 2진수의 덧셈 알고리듬은 기계적으로 구현된다. 모든 컴퓨터 과학자들과 공학자들이 이러한 사실을 잘알고 있다. 1 비트 정수를 더하는 법부터 시작해보자. 연산은(operation) 3가지의 연산수(operands) 또는 3가지 입력값을 연산한다. 비트들은 행 또는 컬럼(column)으로 배열된다. 푸른색으로 표현된 값을 행으로 들어가는 올림값 영어로 케리 인투(carry into column).붉은색으로 표현된 숫자를 행으로부터 나오는 출력 올림값 영어로 캐리 아웃(carry out of the column)이라고 한다.

2 개의 1 비트 정수를 더하기 위해서는 행에 있는 숫자를 더하여 계산한다 그리고 그 결과를 2진수로 쓴다. 결과를 2진수로 쓴 수의 왼쪽 비트를 케리 아웃이라고 한다.

attachment:plus2.JPG

질문: 위에 표와 같은 방식으로 다음을 덧셈하여 보십시요.

1 0 1 0 1 1 1 0 0 - - ---

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_3.html

답:

1	0	1
0	1	1
1	0	0
10	01	10

비트의 행(column)을 덧셈하는 것은 비트의 갯수를 셈하는 것만큼 쉽다. 전자적 관점에서도 쉽다. 전자 논리 회로 과목에서 덧셈하는 회로 만드는 방법을 배울 수 있다. 이제 n-비트 이진수 덧셈 알고리듬에 대하여 공부해 보자. 알고리듬은 2개의 연산수(operands)를 입력받아 하나의 결과를 산출한다. 연산수(operand)는 알고리듬을 통해 연산과정을 거치는 데이터이다. 2개의 N비트의 정수를 더하기 위해서는 오른쪽에서부터 왼쪽으로 각각의 행을 가장 왼쪽의 행까지 계산한다. 각각의 행(column)은 1 비트 덧셈을 수행한다. 각각의 행의 첫번째 열은 올림값을 보여준다. 계산하는 행에 있어서 다음 왼쪽 칼럼의 가장 첫번째 행에 오른쪽 칼럼의 캐리 아웃(carry out) 값을 쓴다. 칼럼을 왼쪽에서 오른쪽으로 옴겨서 그 행을 계산할때는 그 캐리아웃 값이 캐리 인(carry in) 값이 된다.

attachment:plu22.JPG

질문: 다음 덧셈이 정확한지 다음 방법으로 검산해 보십시요.

1. 덧셈 알고리듬이 정확하게 수행됐는지 확인하자.

2. 연산수(operands)를 10진수로 전환 확인하자. 3. 10진수로 덧셈 연산을 하여보자.

0110 = _____<10> 0111 = _____<10>

1101 = _____<10>

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_4.html

답: 0110 = 6<10> 0111 = 7<10>

1101 = 13<10>

또다른 예이다 2진수 덧셈은 일반적인 10진수 덧셈 알고리듬과 같다. 차이점이란 덧셈표에서 각행에 사용된것이 2진수 일뿐이다.

attachment:plus3.JPG

이 경우에 최종 행(column)의 합에서 나온 올림 출력값(carry out)은 버려진다. 하지만 일반적으로 버리는 값에 주의를 기울여야 한다. 다음 페이지를 보자. 10진수 표현으로 전환해서 검산해보자. (같은 숫자가 더해졌다 표현만 다를 뿐이지 결과값은 같다.

attachment:plus4.JPG

질문: 다음을 계산하자.

10 + 01 http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_5.html 답:

캐리값	0	0
		1	0
	+	0	1
	=
		1	1

위의 계산에서는 2개의 비트로 결과 값을 표현할 수 있다.

다음은 몇가지 유념할 세부사항이다.

1. 일반적으로 연산수(operands)와 결과값은 정해진 갯수의 비트(8,16,32 또는 64)를 가지고 있다. 프로세서가 정수를 표현하는데 사용하는 비트의 갯수들이다.

2. 결과값이 연산수(operands)와 같은 비트수를 유지하기 위해서는 왼쪽으로 0비트들을 붙여야 할지도 모른다.

3. 가장 왼쪽행의 캐리아웃(carry-out) 또는 올림 출력수는 계산한다. 하지만 제한된 숫자의 비트갯수로 표현해야 하기 때문에 답으로 쓰지는 않는다.

4. 연산수(operands)를 언사인드(unsigned) 2진수 표현법으로 표현할 경우(앞에 두장을 다시보자) 가장 왼쪽행의 캐리아웃 값이 1이라는 것은 결과값을 제한된 비트의 갯수로 제대로 표현할 수 없다는 의미이다. 이것을 오버플로우(overflow)라고 한다.

5. 연산수(operands)를 2의 보수 표현법을 사용해 표현할 경우(이 장의 마지막 부분에서 공부한다)에는 가장 왼쪽행의 캐리아웃(carry-out) 값이 1이라는 것은 꼭 오버플로우를 의미하는 것은 아니다.

정수는 언사인드(unsigned) 이진수를 사용하거나 2의 보수를 사용하여 표현할 수 있다. 2진수 덧셈 알고리듬은 두가지 표현법에 모두 적용된다. 하지만 결과값을 해석하기 위해서는 어떤 표현법이 사용되었는지 알아야 한다. 두표현법이 각기 다른방법을 사용하야 오버ㅤㅍㅡㅍ로우를 감지한다.

질문: MIPS R2000같은 특정한 프로세서에서 레지스터의 크기는 32 비트 입니다. 2진수의 덧셈을 연산하는 경우에 이러한 프로세서는 일반적으로 몇개의 비트를 사용할까요?

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_6.html

답:

32 비트

다음은 4비트 연산수(operands) 덧셈 입니다.

캐리값	1	111
		0111
		1001
		=

|| || ||0000 ||

오버플로우의 경우 입니다.

2개의 4비트 숫자를 위와같이 더했다. 위의 덧셈의 결과는 4개의 비트로 다표현할 수 없다. 만약 5개의 비트를 사용하였다면 덧셈의 결과는 10000이다. 하지만 4비트로는 1을 표현할 비트의 공간이 없다. 합한 결과값의 가장 왼쪽에 있는 행의 캐리아웃(carry out)값이 1이므로, 4비트로 표현할때 위의 덧셈의 결과는 유효한 값이 아니다.

컴퓨터의 전자 회로는 가장 왼쪽에 있는 행의 캐리아웃(carry out)값이 0인지 1 인지를 확인 함으로써 오버플로우가 발생하였는지 안하였는지 쉽게 확인할 수 있다. 프로그램은 오버플로우가 감지 되었을 경우 에러 핸들링 루틴(error handling routine)을 실행하도록 분기(branch)될 수 도 있습니다.

질문: 8비트로 표현된 다음 숫자를 더해보자.

0010 1100 0101 0101

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_7.html

답:

캐리값	0		1111		100
			0010		1100
			0101		0101
	=
			1000		0001

오버플로우가 발생하지 않습니다.

컴퓨터처럼 이 알고리듬을 사용하여 좀더 연습하여 보자. 가장 왼쪽에 있는 행(column)의 캐리아웃(carry out)값을 살펴봄으로써 오버플로우가 발생하는지 안하는지 알아보자. 이것을 알아보기위해 이진수 표현을 십진수로 바꿀 필요는 없다.

질문: 다음 8비트 숫자를 더하여 보자. 0110 1100 1001 1111 http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_8.html

답:

1	1111	100
	0110	1100
	1001	1111
	=
	0000	1011

(overflow detected)

때로는 16진수로 2숫자의 덧셈을 표현할 필요가 있다. 대개의 경우에는 2진수로 전환하여 덧셈을 하는것이 가장 쉬운 방법이다. 2진수로 전환하여 계산한 후 다시 16진수로 전환한다.

16진수와 16진수 비트패턴 이름이 같다는 점을 이용해 16 진수를 2진수로 쉽게 전환하는 방법을 기억해 보자.

질문 다음 덧셈을 해보자

0F4A 420B

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_9.html 답: attachment:hexplus.JPG

위의 답에서, 가장 왼쪽 행의 캐리아웃 값은 0이므로 오버플로우는 발생하지 않았다. 때때로 어떤 16진수 덧셈 문제는 2진수로 전환할 필요없이 직접 쉽게 풀 수 있다.

014A 4203 = 434D

이런 계산을 할때 손가락을 사용하는 것이 도움이 될 수있다. A+3의경우 손가락 3개를 더해서 "A...B...C..D"를 셈해보라.

질문: 다음 8 비트를 사용해서 덧셈을 해보자. 오버플로우가 발생하였는가?

1101 0010 0110 1101 http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_11.html

attachment:overflow.JPG

언사인드 숫자라는 가정하에서 가장 왼쪽에 비트 또는 하이 오더(high order) 비트가 1이므로 오버플로우(overflow) 입니다.

언사인드 2진수 표현법으로는 음수를 표현할 수 없다. 종이와 연필로 숫자를 표현하는 경우 숫자앞에 음수 기호를 집어넣음으로써 음수를 표현한다. 10진수 24를 음수로 표현한것이 -24이다. 여러분은 그냥 음수 기호를 써서 2진수 음수를 표현하고자 할지도 모른다.

종이와 연필을 사용한다면 0001 1000을 10진수 처럼 -0001 1000으로 표현할 수 도 있을 것이다.

하지만 컴퓨터 메모리의 비트패턴에 음수 기호를 집어넣을 수 는 없다. 메모리에는 오직 0과1의 패턴만이 저장된다. 어떤식으로든 비트패턴을 사용하여 음수를 표현 하여야만 한다. 비트패턴을 사용하여 음수를 표현하는 것은 가능한일이다. 바이너리의 장점에 대해 다시한번 생각해보자.

1. 쉽게 비트패턴을 만들 수 있다. Easy to build.

2. 신호가 명확하다.그러므로 잡음에 영향을 받지 않는다. Unambiguous signals (hence noise immunity). 3. 완벽한 복사(copy)가 가능하다. Can be copied flawlessly. 4. 상징 또는 심볼로 표현될 수 있는 어떤 것이든 비트패턴으로 표현할 수 있다. Anything that can be represented with symbols can be represented with patterns of bits.

만일 종이와 연필을 사용해서 심볼로 음수를 표현할 수 있다면 당연히 비트 패턴으로 음수를 표현할 수 있다.

질문: 8비트로 음수와 양수를 똑같이 표현해야만 한다고 가정해 봅시다. 얼마나 많은 음수를 표현할 수 있습니까? 양수는 얼마나 많이 표현할 수 있을까요?

재미삼아 종이에 8비트 패턴들을 쓰면서 생각해 봅시다.

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_12.html

답: 8 비트로 256개의 비트 패턴이 가능합니다. 그러므로 128개의 양수와 128개의 음수가 가능합니다.

사인 매그너튜드(sign magnitude) 표현법에 대해 이미 생각해 보셨을지도 모르다. 사인 매그너튜드(sign magnitude) 표현법에 대해 알아보자.

비트 패턴으로 음수를 표현할 수 있는 여러가지 방법이 있다. 한가지 방법이 사인 매그너튜드(sign magnitude) 표현법이다. 사인 매그너튜드(sign magnitude) 표현법은 대개의 경우 가장 왼쪽에 있는 1개의 비트를 음수와 양수를 나타내는 신호로 사용한다. 이 비트가 "0"일 경우 양수를 의미한다. "1"의 경우는 음수를 의미한다. 나머지 비트들은 숫자의 크기(magnitude)를 표현하는데 사용한다. 그러므로 10진수 -24를 1001 1000으로 표현할 수 있다.

1001 1000에서 가장 왼쪽의 비트 1은 음수를 의미한다. 크기(magnitude)는 2진수 7비트 0011000을 10진수로 표현할때 24이다.

질문: 8 비트 사인 매그너 튜드(sign magnitude) 표현법을 사용할 때, 어떤 양수와 어떤 음수가 표현 가능하겠습니까?

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_13.html

답:

-127<10> ... 0 ... +127<10>

사인 매그너튜드(sign magnitude) 표현법으로 정수를 표현할 때 몇가지 문제점이 있다. 8 비트로 사인 매그너 튜드 표현법을 사용한 예를 들어보자. 가장 왼쪽에 비트가 음수와 양수를 나타내는 기호또는 사인으로 사용되고 나머지 7 비트는 크기 또는 매그너튜드(magnitude)를 나타내기 위해 남겨진다. 매그너튜드를 표현하기위해 7 비트의 언사인드 2진수가 사용되고 7비트의 언사인드 2진수로 0<10> 000 0000<2>부터 127<10> 111 1111<2>까지 표현할 수 있다. 8번째 비트는 음수와 양수를 표현할 수 있다. 그 결과로 -127<10>,.... -0,0,...,127<10>이 가능하다.

1000 0000은 음수 0에 해당하고 0000 0000은 양수 0에 해당한다.

사인 매그너 튜드 표현법에는 몇가지 문제가 있다. 비록 2개의 0이 존재하지만 나름대로 음수와 양수를 잘표현할 수 있다. 하지만 컴퓨터 연산에는 적합하지 않다. 정수나 다른 어떤것을 표현할 때 좋은 표현하는 방법은 표현하고자 하는 대상자체를 잘표현해야할 뿐만아니라 또한 표현하는 오브젝트의 연산또는 작동도 잘 표현할 수있어야 한다.

이것이 로마 숫자의(I,II,III,IV,...) 문제점이다. 로마숫자는 양의정수를 원하는 대로 다표현할 수 있다. 하지만 그런 표현법을 가지고 연산을 하는것은 굉장히 어렵다.

질문: 이진수 덧셈 알고리듬을 사인 매그너튜드 표현법에 맞추어 사용할 수 있습니까? +16과 -24를 덧셈해 보자.

0001 0000 16 1001 1000 -24

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_14.html

답:

attachment:comp1.JPG

2진수 바이너리 덧셈 알고리듬을 사인 매그너튜드 표현법에 잘 적용하기 힘들다. 사인 매그너퓨드 표현법에 맞추어 작동하는 덧셈알고리듬을 만들 수는 있다. 초창기 컴퓨터들은 그런 알고리듬을 사용하여 만들어 졌다.(다른 초창기 컴퓨터들은 그것보다 더 이상한 알고리듬을 사용하여 만들어졌다.) 컴퓨터 공학에서 더좋은 방법을 찾기까지는 몇년의 세월과 경험이 필요했다.

사인 매그너튜드 표현법 보다 더좋은 방법이 있다. 몇장전에 했던 답을 생각해보자.

attachment:comp2.JPG

질문: 1을 더해서 0이 될 수 있는 수가 있습니다. 그것이 무슨 수 입니까?

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_15.html 답: -1 이 답이 될 수 있다.

-1에 1을 더하면 결과값은 0이다. 1을 더했을때 그 결과로 0이 되는 특정한 비트 패턴이 있다면 그 패턴을 사용해서 음수 1을 표현할 수 있다.

11111	111
0000	0001	=	1<10>
1111	1111	=	-1
0000	0000	=	0<10>

가장 왼쪽행(high order column)의 캐리아웃(carry out)값이 1이지만 정상적인 결과값을 산출한다. 2진수 덧셈알고리듬을 적용해서 8비트의 정확한 결과값을 산출할 수 있다. 다음의 경우를 생각해 보자.

11111	11
0000	1110	=	14<10>
1111	0010	=	?
0000	0000	=	0<10>

질문: 14<10>를 더해서 0이 될 수 있는 숫자가 있다. 그것이 무슨 수 입니까?

http://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_16.html 답: -14.

패턴 "1111 0010"이 음수 14(negative fourteen)를 나타내는 표현이다. 밑에 그림에서 미스터리 넘버(mystery mumber)의 답은 음수 14 이다.

attachment:number.gif

N개의 비트의 전체 비트 패턴에는 2진수 덧셈알고리듬을 사용해서 2개의 패턴을 연산수(operands)로 더할때 N 비트 0을 산출하는 비트 패턴이 항상 존재한다. 이와같이 더해서 0이되는 패턴을 음수를 나타내는 패턴이라고 할 수 있다. 질문: 8비트 패턴 중에서 6<10>에 어떤 수를 더해서 8개의 비트를 0으로 만들수 있는 패턴이 무었입니까? (힌트 우측에서 시작해서 좌측으로 가면서 ?가 무었이 되야할지 생각해 보자)

0000 0110 = 6<10> ???? ???? = -6<10> ------- -- 0000 0000 0<10>

• 비트다루기 C 버전