Lecture 03: Bits, Bytes, and Integers (cont.)

Addition

---

두 정수 $u$, $v$를 더한 값 $s_{ideal}$이 $w$ 비트로 표현 가능한 범위를 벗어나는 경우, $w$ 비트로 정수를 표현하는 컴퓨터에서는 $s_{ideal}$의 하위 $w$ 비트만을 취한 값 $s$가 나타나며, 이러한 현상을 오버플로(Overflow)라 한다.

Unsigned Addition

$s_{ideal} \geq 2^w$인 경우 오버플로가 발생한다. $w = 4$인 경우를 예로 들면,

	Binary	Decimal
$u$	1101	$13$
$v$	0101	$5$
$s$	10010	$18 \ \mathrm{mod} \ 2^4 = 2$

Two’s Complement Addition

비트 수준의 동작은 unsigned와 동일하다.

	Binary	Decimal
$u$	1101	-3
$v$	0101	5
$s$	10010	2

$s_{ideal} < -2^{w-1}$인 경우 음의 오버플로(Negative overflow)가 발생한다.

	Binary	Decimal
$u$	1101	-3
$v$	1010	-6
$s$	10111	7

$s_{ideal} \geq 2^{w-1}$인 경우 양의 오버플로(Positive overflow)가 발생한다.

	Binary	Decimal
$u$	0111	7
$v$	0101	5
$s$	1100	-4

Multiplication

---

덧셈과 마찬가지로, 연산의 결괏값이 $w$ 비트로 표현 가능한 범위를 벗어나면 하위 $w$ 비트만을 취하여 나타낸다.

Unsigned Multiplication in C

	Binary	Decimal
$u$	0101	$5$
$v$	0101	$5$
$s$	00011001	$25 \ \mathrm{mod} \ 2^4 = 9$

Signed Multiplication in C

	Binary	Decimal
$u$	0101	5
$v$	0101	5
$s$	00011001	-7

	Binary	Decimal
$u$	1101	-3
$v$	1110	-2
$s$	10110110	6

Power-of-2 Multiply with Shift

숫자 $x$를 각 비트 $x_i$의 합으로 나타내 보자.

\[x = \sum_{i=0}^{w-1} {x_i 2^i}\]

$x$를 왼쪽으로 $k$만큼 시프트한 것은, $x$에 $2$를 $k$번 곱한 것과 같다.

\[\sum_{i=0}^{w-1} {x_i 2^{i+k}} = 2^k \sum_{i=0}^{w-1} {x_i 2^i} = 2^k x\]

따라서, 2의 거듭제곱을 시프트 연산으로 치환할 수 있다.

시프트 연산을 수행하는 데 1 클럭 사이클(clock cycle)이 소요된다면, 곱셈 연산에는 3 클럭 사이클 이상 소요된다. 이 때문에 컴파일러가 어셈블리 코드를 생성할 때, 최적화를 위해 곱셈 연산을 시프트 연산으로 치환하기도 한다.

Power-of-2 Divide with Shift

위와 같은 원리로, unsigned를 $2^k$으로 나누는 것은 오른쪽으로 $k$만큼 시프트하는 것과 같다.

Division	Shift	Binary	Decimal
x	x	0110	6
x / 2	x >> 1	0010	3
x / 4	x >> 2	0001	1

signed의 경우 양수를 나누는 것은 오른쪽 산술 시프트(arithmetic shift)와 동일하나, 음수를 나누는 것은 조금 다르다.

Division	Shift	Binary	Decimal
x	x	1010	-6
x / 2	x >> 1	1101	-3
	x >> 2	1110	-2
x / 4	x + bias >> 2	1111	-1

정수의 나눗셈에서 나누어떨어지지 않는 경우 결괏값이 0에 가까워지도록 반올림한다. 그런데 $x$가 음수이면서 나누어떨어지지 않을 때 단순히 시프트하면 0이 아닌 음의 무한대에 가까워지도록 반올림한 셈이 되기 때문에, 이를 방지하기 위해 바이어스(bias)를 더해준 뒤 시프트한다.

나눗셈 연산은 30 클럭 사이클 이상 소요될 정도로 굉장히 느리기 때문에, 곱셈과 마찬가지로 컴파일러가 최적화를 위해 시프트 연산으로 치환하기도 한다.

Memory Organization

---

Byte-Oriented Memory Organization

메모리를 번호(주소)가 매겨진 대규모 바이트 배열이라고 생각할 수 있다.

운영체제는 프로세스가 각각 메모리의 특정 영역만 참조할 수 있도록 허용하며, 그 외의 영역에 접근 시 세그멘테이션 오류(segmentation fault)를 발생시킨다.

Machine Words

워드(word)의 크기는 해당 시스템에서 가장 큰 숫자 또는 포인터의 크기와 같다.
기본적으로 하드웨어에 의해 결정되며, 컴파일러를 통해 하위 호환되는 크기로 변경할 수도 있다. (예: 64비트 → 32비트)

Word-Oriented Memory Organization

메모리 자체는 바이트의 배열로 볼 수 있지만, 이를 다시 워드 단위로 그룹화할 수 있다.
각 워드의 주소는 해당 워드에 속해 있는 가장 낮은 바이트의 주소와 같다.

32-bit words	64-bit words	Bytes
0000	0000	0000
		0001
		0002
		0003
0004		0004
		0005
		0006
		0007
0008	0008	0008
		0009
		000A
		000B
000C		000C
		000D
		000E
		000F

Byte Ordering

---

Big Endian

워드의 첫 번째 바이트에 최상위 바이트를 저장한다.

• Sun, PPC Mac, 인터넷

Little Endian

워드의 첫 번째 바이트에 최하위 바이트를 저장한다.

• x86, ARM 프로세서

Byte Ordering Example

4바이트 변수 x = 0x01234567이고 &x = 0x100일 때,

Address	0x100	0x101	0x102	0x103
Big Endian	01	23	45	67
Little Endian	67	45	23	01

Interger C Puzzles

---

int x = foo();
int y = bar();
unsigned ux = x;
unsigned uy = y;

다음 명제의 참/거짓을 판단해 보자.

명제	판단
x < 0 $\Rightarrow$ (x * 2) < 0	거짓
ux >= 0	참
x & 7 == 7 $\Rightarrow$ (x << 30) < 0	참
ux > -1	거짓
x > y $\Rightarrow$ -x < -y	거짓
x * x >= 0	거짓
x > 0 && y > 0 $\Rightarrow$ x + y > 0	거짓
x >= 0 $\Rightarrow$ -x <= 0	참
x <= 0 $\Rightarrow$ -x >= 0	거짓
(x | -x) >> 31 == -1	거짓

References

---

• Carnegie Mellon University. (2015). Lecture 03: Bits, Bytes, and Integers (cont.). [Online].