[CSAPP] 2.2 정수의 표시(Ch. 2 정보의 표현과 처리)

2.2 정수의 표시

signed integer와 unsigned integer를 인코딩하는 방법에 대해 살펴볼 것.

또한 인코딩된 정수를 길이가 다른 표현에 맞게 확장 or 축소하는 방법도 볼 것이다.

다음은 정수 인코딩 공부 과정에서 참조 가능한 수학적 용어들에 대한 표이다($\omega$는 데이터 표시에 필요한 비트 수를 의미).

Symbol	Type	Meaning	Page(한글판/영문판)
$B2T_{\omega}$	Function	Binary to two's complement	63/100
$B2U_{\omega}$	Function	Binary to unsigned	61/98
$U2B_{\omega}$	Function	Unsigned to binary	63/100
$U2T_{\omega}$	Function	Unsigned to two's complement	69/107
$T2B_{\omega}$	Function	Two's complement to binary	64/101
$T2U_{\omega}$	Function	Two's complement to unsigned	69/107
$TMin_{\omega}$	Constant	Minimum two's-complement value	64/101
$TMax_{\omega}$	Constant	Maximum two's-complement value	64/101
$UMax{\omega}$	Constant	Maximum unsigned value	62/99
$+^t_{\omega}$	Operation	Two's-complment addition	87/126
$+^u_{\omega}$	Operation	Unsigned addtion	83/121
$*^t_{\omega}$	Operation	Two-s-complment multiplication	94/133
$*^u_{\omega}$	Operation	Unsigned multiplication	93/132
$-^t_{\omega}$	Operation	Two's-complement negation	92/131
$-^u_{\omega}$	Operation	Unsigned negation	86/125

---

2.2.1 정수형 데이터 타입

<32비트 프로그램에서 C 정수형 자료형의 '일반적' 범위>

C data type	Minimum	Maximum
[signed] char	−128	127
unsigned char	0	255
short	-32,768	32,767
unsigned short	0	65,535
int	-2,147,483,648	2,147,483,647
unsigned	0	4,294,967,295
long	-2,147,483,648	2,147,483,647
unsigned long	0	4,294,967,295
int32_t	-2,147,483,648	2,147,483,647
uint32_t	0	4,294,967,295
int64_t	-9,222,372,036,854,775,808	9,223,372,036,854,775,807
uint64_t	0	18,446,744,073,709,551,615

<64비트 프로그램에서 C 정수형 자료형의 '일반적' 범위>

C data type	Minimum	Maximum
[signed] char	−128	127
unsigned char	0	255
short	-32,768	32,767
unsigned short	0	65,535
int	-2,147,483,648	2,147,483,647
unsigned	0	4,294,967,295
long	-9,222,372,036,854,775,808	9,223,372,036,854,775,807
unsigned long	0	18,446,744,073,709,551,615
int32_t	-2,147,483,648	2,147,483,647
uint32_t	0	4,294,967,295
int64_t	-9,222,372,036,854,775,808	9,223,372,036,854,775,807
uint64_t	0	18,446,744,073,709,551,615

C 표준은 각 자료형에서 표현할 수 있는 최소한의 범위만 명시한다.

표준에서는 고정길이 자료형을 제외하면 양수와 음수 범위가 대칭적이다.

다음은 C 정수형 자료형의 보장된 범위이다.

C data type	Minimum	Maximum
[signed] char	−127	127
unsigned char	0	255
short	-32,767	32,767
unsigned short	0	65,535
int	-32,767	32,767
unsigned	0	65,535
long	-2,147,483,647	2,147,483,647
unsigned long	0	4,294,967,295
int32_t	-2,147,483,648	2,147,483,647
uint32_t	0	4,294,967,295
int64_t	-9,222,372,036,854,775,808	9,223,372,036,854,775,807
uint64_t	0	18,446,744,073,709,551,615

---

2.2.2 비부호형의 인코딩

$\omega$비트의 정수형 자료형을 가정.

비트 벡터 전체를 $vec{x}$로 나타내거나, $[x_{\omega - 1}, x_{\omega - 2} , \cdots , x_0]$로 나타낼 수 있다.

비부호형 해석은 $vec{x}$전체를 이진수로 나타낸 숫자로 해석하면 된다.

$x_i$는 $2^i$자릿수를 의미한다.

 

함수 $B2U_{\omega}$는 길이 $\omega$의 binary에서 unsigned로 해석하는 것을 의미.

Principle : Definition of unsigned encoding

For vector $vec{x} = [x_{\omega - 1} , x_{\omega - 2} , \cdots, x_0]$:

$$B2U_{\omega} (vec{x}) \doteq \sum_{i = 0}^{\omega - 1} x_i 2^i$$

$\doteq$는 좌변과 우변이 동일하게 정의됨을 의미.

함수 $B2U_{\omega}$는 길이 $\omega$의 0과 1의 스트링을 양의 정수로 매핑한다.

 

$\omega$비트로 표시할 수 있는 가장 큰 양의 정수는 $UMax_{\omega} \doteq \sum_{i = 0}^{\omega - 1} 2^i = 2^{\omega} - 1$이고, 비트 벡터 $[11 ... 1]$이 된다.

이를 통해 비부호형 이진수 표시는 0과 $2^{\omega} - 1$사이의 모든 숫자가 $\omega$비트 값으로 유일한 인코딩을 갖는 특성을 지닌다.

Principle : Uniqueness of unsigned encoding

Function $B2U_{\omega}$ is a bijection(전단시).

'전단시' 특성의 수학적 의미는 어떤 함수 f를 양방향으로 매핑할 수 있는 것을 의미.(일대일 함수?)

어떤 값 $x$를 $y$로 매핑하면 $y = f(x)$이고 역방향에서 모든 $y$에 대해 $f(x) = y$인 유일한 $x$가 존재.

함수 $B2U_{\omega}$는 길이 $\omega$의 각 비트 벡터를 $0$과 $2^{\omega}-1$사이의 유일한 수로 매핑하며 그 역도 도출 가능.

이를 $U2B_{\omega}$(unsigned tobinary)로 표시하고, $0$과 $2^{\omega} - 1$사이 모든 수를 유일한 $\omega$비트 패턴으로 매핑함.

---

2.2.3 2의 보수(two's complement) 인코딩

'2의 보수 형식'은 부호형 숫자를 컴퓨터에서 표시하는 가장 일반적인 방법.

한 워드의 가장 중요한 비트를 부호값으로 해석.

Principle : Definition of two's-complement encoding

For vector $vec{x} = [x_{\omega -1}, x_{\omega - 2} , \cdots , x_0]$:

$$B2T_{\omega}(vec{x}) \doteq - x_{\omega -1} 2^{\omega -1} +\sum_{i=0}^{\omega - 2} x_i 2^i$$

가장 중요한 비트 $x_{\omega -1}은 '부호 비트'라고도 부름. 부호 비트의 자리값(weight)은 $-2^{\omega -1}$이고 비부호형 표현의 자릿값을 음수로 바꾼 것과 같다.

 

표시할 수 있는 가장 작은 수는 비트 벡터 $[10  \cdots 0]$이고, 정수 값으로는 $TMin_{\omega} \doteq -2^{\omega -1}이다.

가장 큰 값은 비트 벡터 $[01 \cdots 1]$이고, 정수 값은 $TMax_{\omega} \doteq \sum_{i=0}^{\omega-2} 2^i = 2^{\omega - 1} - 1$이다.

$B2T_{\omega}$는 길이 $\omega$의 비트 패턴을 $TMin_{\omega}$와 $TMax_{\omega}$사이의 수로 대응시키고 이를 다음과 같이 표현한다.

$B2T_{\omega} : \{0, 1\}^{\omega} \to  \{TMin_{\omega} , \cdots , TMax_{\omega} \}$

unsigned와 마찬가지로 인코딩의 유일성 법칙이 존재.

Principle : Uniqueness of two's-complement encoding

Function $B2T_{\omega}$ is a bijection.

앞에서와 마찬가지로 함수 $T2B_{\omega}$는 $B2T_{\omega}$의 역함수이다.

따라서 $TMin_{\omega} \leq x \leq TMax_{\omega}$의 어떤 수 $x$에 대해 $T2B_{\omega}(x)$는 $x$를 인코딩한 길이 $\omega$의 유일한 비트 벡터이다.

 

다음 표는 워드 크기별 중요 value에 대한 비트 표현과 숫자 값을 보여준다.

	Word size $w$
Value	8	16	32	64
$UMax_{\omega}$	0xFF	0xFFFF	0xFFFFFFFF	0xFFFFFFFFFFFFFFFF
	255	65,353	4,294,967,295	18,446,744,073,709,551,615
$TMin_{\omega}$	0x80	0x8000	0x80000000	0x8000000000000000
	-128	-32,768	-2,147,483,648	-9,223,372,036,854,775,808
$TMax_{\omega}$	0x7F	0x7FFF	0x7FFFFFFF	0x7FFFFFFFFFFFFFFF
	127	32,767	2,147,483,647	9,223,372,036,854,775,807
-1	0xFF	0xFFFF	0xFFFFFFFF	0xFFFFFFFFFFFFFFFF
0	0x00	0x0000	0x00000000	0x0000000000000000

• $|TMin| = |TMax| + 1$ : 0이 비음수에 포함되기 때문에 양수의 개수가 음수보다 1개 적다.
• $UMax = 2TMax + 1$
• -1이 unsigned에서는 비트가 모두 1인 $UMax$와 같은 비트 표시를 갖는다
• 0은 signed, unsigned 상관 없이 모두 비트가 0인 스트링으로 표현된다.

C 라이브러리의 <limits.h>의 매크로 INT_MAX, INT_MIN, UINT_MAX는 $TMax_{\omega}$, $TMin_{\omega}$, $UMax_{\omega}$에 대응된다.

---

2.2.4 비부호형과 부호형 간의 변환

C에서 캐스팅은 같은 비트에 대해 다른 자료형으로 해석하게 하는 기능이라 할 수 있다.

$T2U_{\omega}(x) \doteq B2U_{\omega}(T2B_{\omega}(x))$로 정의되고, 정의역은 $TMin_{\omega} \leq x \leq TMax_{\omega}$이다.

$U2T_{\omega}(x) \doteq B2T_{\omega}(U2B_{\omega}(x))$로 정의되고, 정의역은 $0 \leq x \leq UMax_{\omega}$이다.

Principle : Conversion from two's complement to unsigned

For $x$ such that $TMin_{\omega} \leq x \leq TMax_{\omega}$ :

$$T2U_{\omega}(x) = \begin{cases} x+2^{\omega}, & x <0 \\ x, & x \geq 0 \end{cases}$$

 

ex) $T2U_{16} (-12,345) = -12,345 + 2^{16} = 53,191$

    $T2U_{\omega} (-1) = -1 + 2^{\omega}$

 

Principle : Unsigned to two's-complement conversion

For $u$ such that $0 \leq u UMax_{\omega}$:

$$U2T_{\omega}(u) = \begin{cases} u, & u \leq TMax_{\omega} \\ u - 2^{\omega}, & u > TMax_{\omega}\end{cases}$$

---

2.2.5 C에서 부호형과 비부호형의 비교

명시적 캐스팅 : 괄호를 통해 캐스팅

묵시적 캐스팅 : 한 가지 타입의 수식이 다른 타입의 변수에 할당될 때 발생

또한 C에서 부호형과 비부호형이 섞인 수식을 처리할 때 피연산자 한 개가 부호형이고 다른 것이 비부호형인 경우 묵시적으로 부호형 인자를 비부호형으로 변환하고(즉, 숫자들이 비음수라고 가정하고) 계산을 수행.

다음은 C 변환 규칙 효과에 대한 표이다. 직관적이지 않은 evaluation결과에 '*'표시하였다.

Expression			Type	Evaluation
0	==	0U	Unsigned	1
-1	<	0	Signed	1
-1	<	0U	Unsigned	0 *
2147483647	>	-2147483647-1	Signed	1
2147483647U	>	-2147483647-1	Unsigned	0 *
2147483647	>	(int) 2147483648U	Signed	1 *
-1	>	-2	Signed	1
(unsigned) -1	>	-2	Unsigned	1

cf) C에서 $TMin_{32}$을 쓸 때 -2,147,483,648 대신 -2,147,483,647-1로 쓰는 것은 2의 보수 표현의 비대칭성과 C의 변환 규칙 때문.

---

2.2.6 수의 비트 표시를 확장하기

어떤 정수를 동일한 값의 더 긴 길이의 워드로 확장하려고 한다.

 

비부호형 수를 더 긴 자료형으로 변환하려면 단순히 앞에 0을 추가하면 된다.

이는 '영의 확장(zero extension)'이라고 부른다.

Principle : Expansion of an unsigned number by zero extension

Define bit vectors $ \vec{u} = [ u_{\omega-1} , u_{\omega - 2}, \cdots , u_0]$of width $\omega$ and $\vec{u} = [ 0, \cdots , 0, u_{\omega -1}, u_{\omega-2}, \cdots, u_0]$ of width $\omega'$, where $\omega' > \omega$. Then $B2U_{\omega} (\vec{u}) = B2U_{\omega'} (\vec{u}')$.

 

2의 보수를 더 긴 자료형으로 변환하려면 '부호 확장(sign extension)'이 필요.

이는 가장 중요한 비트를 복사해서 앞부분에 추가하는 것이다.

Principle : Expansion of a two's-complement number by sign extension

Define bit vectors $\vec{x} = [x_{\omega-1}, x_{\omega-2}, \cdots , x_0]$ of width $\omega$ and $\vec{x}' = [x_{\omega -1}, \cdots, x_{\omega-1} , x_{\omega-1} , x_{\omega-2}, \cdots, x_0]$ of width $\omega'$, where $\omega' > \omega$. Then $B2T_{\omega} (\vec{x}) = B2T_{\omega'}(\vec{x}')$.

 

cf) C에서 데이터 길이를 늘이고 비부호형과 부호형 간의 변환의 작업 순서에 따라 결과물이 달라질 수 있음.

short sx = -12345;			/* -12345 */
unsigned uy = sx;

printf("uy	= %u:\t", uy);
show_bytes((byte_pointer) &uy, sizeof(unsigned));

위 코드를 빅 엔디안 머신에서 실행하면 다음과 같이 출력.

uy = 4294954951: ff ff cf c7

이는 short을 unsigned로 변환하는 작업이 길이를 늘인 다음, 자료형을 변환하기  때문이다.

(unsigned)sx 는 (unsigned)(int)sx이지 (unsigned)(unsigned short)sx가 아니다.

단순히 관습이 아니라 C 표준에 요구되는 내용이다.

---

2.2.7 숫자의 절삭

int x = 53191;
short sx = (short) x;	/* -12345 */
int y = sx;				/* -12345 */

 $\omega$비트의 수 $\vec{x} = [ x_{\omega-1}, x_{\omega-2} , \cdots, x_0]$를 $k$비트 수로 절삭하면 상위 $\omega -k$비트를 제거해서 비트 벡터 $\vec{x} = [x_{k-1} , x_{k-2}, \cdots, x_0]$를 얻게 된다. 이렇게 수를 절삭하면 값이 바뀔 수 있는데, 일종의 오버플로우로 볼 수 있다.

Principle: Truncation of an unsigned number

Let $\vec{x}$ be the bit vector $[x_{\omega-1}, x_{\omega-2}, \cdots, x_0]$, and let $\vec{x}'$ be the result of truncating it to $k$ bits: $\vec{x}' = [x_{k-1}, x_{k-2}, \cdots, x_0]$. Let $x= B2U_{\omega}(\vec{x})$ and $x'  = B2U_k(\vec{x}')$. Then $x' = x\,mod\,2^k$.

 

2의 보수의 절삭에서도 맨 앞 비트만 부호 비트로 생각하는 것을 제외하면 비슷하다.

Principle: Truncation of a two's-complement number

Let $\vec{x}$ be the bit vector $[x_{\omega-1}, x_{\omega-2}, \cdots, x_0]$, and let $\vec{x}'$ be the result of truncating it to $k$ bits: $\vec{x}' = [ x_{k-1}, x_{k-2}, \cdots, x_0]$. Let $x = B2T_{\omega} (\vec{x})$ and $ x' = B2T_k(\vec{x}')$. Then $x' = U2T_k(x\, mod\, 2^k)$.

---

2.2.8 Signed와 Unsigned에 관한 조언

묵시적 타입 변환으로 인한 버그는 알아채기 힘드므로 사용에 주의해야 한다.

다른 언어는 unsigned형을 지원하지 않는 경우도 많다.

비부호형 값이 유용한 경우로는 우선 워드 길이 데이터를 숫자로 해석하기 보다 단순한 비트의 집합으로 해석하는 경우에 유용하다.(bool 플래그의 집합과 같은 경우)

두번째로는 주소의 경우. (주소는 원래 unsigned이므로)

또 modular연산, 다중정밀도 산술연산 같이 숫자들이 워드의 배열로 표시되는 경우에 수학 패키지로 구현할 때 유용.