[Chapter 2] 불 연산 (Boolean Arithmetic)

(밑바닥부터 만드는 컴퓨팅 시스템 2판,  인사이트(insight), 2023)을 학습하고 개인 학습용으로 정리한 내용입니다.

 

 

 

 

 

1. 산술연산

범용 컴퓨터 시스템은 부호 있는 정수에 대해 최소한 다음과 같은 산술 연산을 수행할 수 있어야한다.

• 덧셈
• 부호 변환
• 뺄셈
• 비교
• 곱셈
• 나눗셈

2. 2진수

컴퓨터 내부에서 모든 것은 2진 코드로 표현된다.

예를 들어, 10진수 19는, 2진수 10011로 표현된다. 이때, 2진수의 가장 오른쪽에 있는 숫자를 최하위 비트(least significant bit, LSB)라 하고, 가장 오른쪽에 있는 숫자를 최상위 비트(most significant bit, MSB)라 한다.

컴퓨터는 모든 것을 2진수로 처리하기 때문에 10진수는 전혀 신경 쓰지 않는다. 하지만 인간은 숫자를 10진수로 보거나 입력하기를 원하기 때문에, 컴퓨터는 필요할 때마다 '2진수 ↔ 10진수' 또는 '10진수  ↔  2진수' 변환을 뒤에서 열심히 수행해야 한다. 그 외의 경우에는 2진수로만 처리한다.

 

3. 고정 단어 크기

정수는 무한하다. 하지만 컴퓨터는 유한한 기계다.

단어 크기(word size)란? 일반적인 하드웨어 용어로, 컴퓨터가 기본 정보 단위를 표현하는데 사용하는 비트 수를 가리킨다.

보통 정수를 표현하는 데 8-bit(byte), 16-bit(short), 32-bit(int), 64-bit(long) 레지스터가 사용된다.

고정 단어 크기는 이 레지스터가 표현 가능한 값의 개수에 한계가 있음을 의마한다.

일반적으로 n-bit가 있으면 음수가 아닌 정수는 0에서 \( 2^{n}-1 \)까지 표현할 수 있다.

 

4. 2진 덧셈

두 개의 2진수를 더하려면, 가장 오른쪽 숫자 둘부터 더한다.

0	0	0	1		자리올림 비트 (carry)	1	1	1	1
	1	0	0	1	x		1	0	1	1
+	0	1	0	1	y	+	0	1	1	1
0	1	1	1	0	x + y	1	0	0	1	0
오버플로 없음						오버플로

모든 덧셈이 끝났을 때, 자리올림수가 1이라면, 오버플로(overflow)가 발생한다.

오버플로를 어떻게 처리할지는 결정에 따른 문제로, nand2tetris에서는 오버플로를 무시한다.

기본적으로 어떤 두 n-bit 숫자를 더했을 때, 그 결과가 명확하고 뚜렷하다면 그냥 무시하는것도 방법이다.

 

5. 부호가 있는 2진수

n-bit 2진법 체계는 \( 2^{n} \)개 코드를 표현할 수 있다. 만약 2진 코드로 부호(양수 혹은 음수)가 있는 숫자를 나타내야 한다면, 코드 공간을 나누어서, 하나는 음수를 표현하도록 해야한다.

오늘날 거의 모든 컴퓨터에서 사용되는 방식은 2의 보수법(two's complement)으로 기수의 보수법(radix complement)이라고도 한다. 

단어 크기가 n-bit인 체계에서, 2의 보수법으로 음수 x를 표현하는 값은 \( 2^{n}-x \)이 된다.

예를 들어 4-bit 2진법 체계에서 -7은, \( 2^{4} -7 = 9 \)인, 1001로 표현된다. +7은 0111로, 1001 + 0111 = 0000(오버플로 무시)이 됨을 알 수 있다.

0	0	0	0	:	0
0	0	0	1	:	1
0	0	1	0	:	2
0	0	1	1	:	3
0	1	0	0	:	4
0	1	0	1	:	5
0	1	1	0	:	6
0	1	1	1	:	7
1	1	0	0	:	-8	(16 - 8)
1	0	0	1	:	-7	(16 - 7)
1	0	1	0	:	-6	(16 - 6)
1	0	1	1	:	-5	(16 - 5)
1	1	0	0	:	-4	(16 - 4)
1	1	0	1	:	-3	(16 - 3)
1	1	1	0	:	-2	(16 - 2)
1	1	1	1	:	-1	(16 - 1)

             < 4-bit 2진법 체계에서,  2의 보수법 표현 >

 

2의 보수법 표현은 다음과 같은 특징을 가진다.

• \( -(2^{n-1}) \) 부터 \( 2^{n-1} \)까지 \( 2^{n} \)개의 부호 있는 숫자를 표기할 수 있다.
• 음수 아닌 수의 코드는 모드 0으로 시작한다.
• 음수의 코든느 1로 시작한다.
• x의 코드에서 -x의 코드를 구하려면, x의 최하위 0-bit와 처음으로 나타나는 최하위 1-bit는 그대로 두고, 나머지 비트들을 모두 뒤집으면 된다.(0은 1, 1은 0으로) 또는 x의 모든 비트를 뒤집고 그 결과에 1을 더해주면 된다.