Lecture 02: Bits, Bytes, and Integers

Everything is bits

---

디지털 세상은 이진 값을 기반으로 한다.
연속적인 값(아날로그)보다 비트 단위의 값(디지털)을 저장하는 것이 훨씬 용이하기 때문이다.

Example Data Representations

C Data Type	Typical 32-bit	Typical 64-bit	x86-64
char	1	1	1
short	2	2	2
int	4	4	4
long	4	8	8
float	4	4	4
double	8	8	8
long double	-	-	10/16
pointer	4	8	8

시간이 지남에 따라 워드(word)의 크기가 점차 확장되어 왔기 때문에, 자료형의 크기는 기계마다 다를 수 있다.

Boolean Algebra

---

비트 연산은 19세기에 등장한 불 대수(Boolean algebra)를 기반으로 한다.

A	B	A & B	A | B	~A	A ^ B
0	0	0	0	1	0
0	1	0	1	1	1
1	0	0	1	0	1
1	1	1	1	0	0

Example: Representing & Manipulating Sets

$w$개의 비트를 이용하여 크기가 $w$인 집합의 부분 집합을 표현할 수 있다.

\[a_j = 1 \ \ if \ \ j \in A\]

Bit vector	Subset
01101001	{ 0, 3, 5, 6 }
01010101	{ 0, 2, 4, 6 }

또한, 비트 연산은 집합 연산에 각각 대응한다.

	Operation	Bit vector	Subset
&	교집합 (Intersection)	01000001	{ 0, 6 }
|	합집합 (Union)	01111101	{ 0, 2, 3, 4, 5, 6 }
^	대칭차집합 (Symmetric difference)	00111100	{ 2, 3, 4, 5 }
~	여집합 (Complement)	10101010	{ 1, 3, 5, 7 }

Contrast: Logic Operations in C

&&, ||, !과 같은 논리 연산에서

• 0은 False로 간주
• 0이 아닌 것은 모두 True
• 항상 0 또는 1을 반환
• 연산 진행 도중 남은 연산에 관계 없이 결괏값이 결정되는 경우, 연산 조기 종료(Early termination)

16진수 논리 연산 예시:

• !0x41 → 0x00
• !0x00 → 0x01
• !!0x41 → 0x01
• 0x69 && 0x55 → 0x01
• 0x69 || 0x55 → 0x01
• p && *p (Null 포인터에 접근하는 것을 방지)

Shift Operations

---

Left Shift: x << y

비트 벡터 x를 왼쪽으로 y만큼 시프트한 뒤, 빈 자리(새로운 하위 비트)를 0으로 채운다.

x	x << 3
01100010	00010000
10100010	00010000

Right Shift: x >> y

비트 벡터 x를 오른쪽으로 y만큼 시프트한 뒤, 빈 자리(새로운 상위 비트)를

• 논리 시프트 (Logical shift): 0으로 채운다.
• 산술 시프트 (Arithmetic shift): x의 최상위 비트와 동일한 값으로 채운다.

x	x >> 2 (Log.)	x >> 2 (Arith.)
01100010	00011000	00011000
10100010	00101000	11101000

Undefined Behavior

• y가 음수인 경우
• y의 값이 비트 벡터 x의 크기보다 큰 경우

Encoding Integers

---

Sign Bit

2의 보수(Two’s complement) 표현에서 최상위 비트는 부호를 의미한다.
최상위 비트가 1이면 음수이며, 0이면 음수가 아니다.

Type	Binary	Decimal
Unsigned	10110	$16 + 4 + 2 = 22$
Signed (Two’s complement)	10110	$-16 + 4 + 2 = -10$

Numeric Ranges

크기가 $w$인 비트 벡터에 대해 unsigned의 최댓값, 최솟값을 각각 $U_{max}$, $U_{min}$,
signed의 최댓값, 최솟값을 각각 $T_{max}$, $T_{min}$이라 하자.

	Binary	Decimal
$U_{min}$	000…0	$0$
$U_{max}$	111…1	$2^w - 1$
$T_{min}$	100…0	$-2^{w-1}$
$T_{max}$	011…1	$2^{w-1} - 1$

• $\lvert T_{max} \rvert = \lvert T_{min} \rvert - 1$
• $U_{max} = 2T_{max} + 1$

Unsigned & Signed Numeric Values

이진수 $X$를 unsigned 또는 signed로 간주하여 십진수로 나타낸 값을 각각 $B2U(X)$, $B2T(X)$라 하자.

$X$	$B2U(X)$	$B2T(X)$
000	0	0
001	1	1
010	2	2
011	3	3
100	4	-4
101	5	-3
110	6	-2
111	7	-1

• 비트 패턴이 동일하더라도 unsigned와 signed 중 어떤 것으로 간주되냐에 따라 값이 달라질 수 있다.
• 최상위 비트가 0인 경우 두 값이 동일하며, 1인 경우 두 값의 차는 $2^w$이다.
• $B2U(X)$와 $B2T(X)$는 일대일 대응이다.

Signed vs Unsigned in C

---

Constants

기본적으로 상수는 signed로 간주되며, 0U, 4294967259U와 같이 접미사 U를 통해 unsigned로 선언할 수 있다.

Casting Surprises

하나의 표현식에 unsigned와 signed가 섞여 있는 경우, signed는 암시적으로 unsigned로 변환된다.
$w = 32$인 경우를 예로 들면,

\[\begin{align*} T_{min} &= -2,147,483,648 \\[5pt] T_{max} &= \ \ \; 2,147,483,647 \end{align*}\]

LHS	RHS	Relation	Evaluation
0	0U	==	unsigned
-1	0	<	signed
-1	0U	>	unsigned
2147483647	-2147483647-1	>	signed
2147483647U	-2147483647-1	<	unsigned
-1	-2	>	signed
(unsigned)-1	-2	>	unsigned
2147483647	2147483648U	<	unsigned
2147483647	(int)2147483648U	>	signed

이번에는 다음 반복문을 보자.

for (int i = n - 1; i - sizeof(char) >= 0; i--)
    f(a[i]);

얼핏 보면 i가 감소하면서 루프를 돌다가 0이 되는 순간 루프를 종료할 것처럼 보인다. 하지만 실제로는 sizeof 연산자가 unsigned를 반환하기 때문에 암시적 형 변환이 일어나 조건 i - sizeof(char) >= 0은 항상 참이 되고, i가 계속 감소하다가 결국 음수가 되면서 유효한 인덱스 범위를 벗어나 메모리 에러를 초래하거나 무한 루프에 빠질 것이다.

Sign Extension & Truncation

---

Expanding

어떠한 정수를 보다 큰 크기의 자료형으로 변환할 때, 빈 자리(새로운 상위 비트)를 기존의 최상위 비트와 동일한 값으로 채운다.

Word size	Binary
4 → 8	00000110
4 → 8	11111110

Truncating

반대로 보다 작은 자료형으로 변환할 때, 상위 비트가 그대로 잘린다. 이때 값이 변하는 메커니즘은 나머지 연산과 동일하다.

Type	Word size	Binary	Decimal
Unsigned	8 → 4	10001011	$139 \ \mathrm{mod} \ 2^4 = 11$
Signed	8 → 4	10000011	$-125 \ \mathrm{mod} \ 2^4 = 131 \mathrm{U \ mod} \ 2^4 = 3$

References

---

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