CS : APP Chapter 2-2

2.2 Integer Representations2.2.1 Integral Data Types2.2.2 Unsigned Encodings2.2.3 Two's-Complement Encodings2.2.4 Conversions Between Signed and Unsigned2.2.5 Signed vs. Unsigned in C2.2.6 Expanding the Bit Representation of a Number2.2.7 Truncating Numbers2.2.8 Advice on Signed vs. Unsigned

2.2 Integer Representations

이 섹션에서, 우리는 integers를 인코딩하기 위해 사요될 수 있는 두 개의 다른 방법을 설명한다 - 음이 아닌 숫자만을 나타낼 수 있는 것과, negative, zero, 그리고 positive numbers를 나타낼 수 있는 것.

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

Figure 2.8 32-bit machine에서 C integral data types의 일반 범위. square brackets에 있는 Text는 optional하다.

 

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

Figure 2.9 64-bit machine에서 C integral data types에 대한 일반 범위. square brackets에 있는 Text는 optoinal이다.

 

우리는 그것들이 그것들의 수학적 특성과 machine-level 구현 둘 다에 강하게 연결되어 있다는 것을 볼 것이다. 우리는 또한 encoded integer를 다른 길이를 가진 representation과 맞게하기 위해 expand하고 shirink시키는 효과를 조사한다.

 

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

Figure 2.10 C integral data types에 대해 보장되는 범위. square brackets에 있는 Text는 optional하다. 그 C표준은 그 data types이 적어도 이 범위의 값들을 가질 것을 요구한다.

 

2.2.1 Integral Data Types

C는 다양한 Integral data types를 지원한다 - 유한한 범위의 integers를 나타내는 것들. 이러한 것은 그림 2.8과 2.9에서 보여지고, "일반적인" 32- 그리고 64-bit macihnes에 대해 그것들이 가질 수 있는 값의 범위가 함께 있다. 각 type은 char, short, long, 또는 long long의 키워드와 함께 size를 명시할 수 있고, 그 뿐만 아니라 그 나타내어진 숫자들이 모두 음수가 아닌 것을 가리키는 (unsigned로 선언된) 것을 명시할 수 있다. 또는 negative가 될 수 있는지 (default). 우리가 그림 2.3에서 보았듯이, 다른 sizes에 대해 할당된 bytes의 수는 machine의 word size와 compiler에 따라 다르다. byte allocations을 기반으로, 다른 sizes는 다른 범위의 값들이 나타내어지게 된다. 가리켜진(indicated) 유일한 machine-dependent range는 size 지정자 long에 대한 것이다. 대부분의 64-bit machines은 8-byte representation을 사용하는데, 이것은 32-bit machines에서 사용되는 4-byte representation보다 더 넓은 범위의 값을 준다.

그림 2.8과 2.9에서 주목해야할 한 가지 중요한 특징은, 그 범위들이 대칭적이지 않다는 것이다 - 음수의 값의 범위는 양수의 값의 범위 보다 더욱 확장된다. 우리는 음수가 나타내어지는 방법을 고려할 때 왜 이것이 발생하는지를 알게 될 것이다.

그 C 표준은 각 data type이 나타내어질 수 있어야 하는 최소한의 값의 범위를 정의한다. 그림 2.10에서 보여지듯이, 그것들의 범위는 그림 2.8과 2.9에서 보여지는 일반 구현보다 같거나 더 작다. 특히, 우리는 그것들이 오직 양수와 음수의 대칭 범위를 요구한다는 것을 알게 된다. 우리는 또한 그 data type int가 2-byte numbers로 구현되어질 수 있다는 것을 알게 된다. 비록 이것이 16-bit machines 시절의 옛날 것이지라도. 우리는 또한 long size가 4-byte 숫자로 구현되어질 수 있다는 것을 알게 된다. 그리고 이것은 종종 사실이다. Data type long long은 ISO C99와 함께 도입되었고, 그것은 적어도 8-byte representation을 요구한다.

New to C? Signed and unsigned numbers in C, C++, Java

C와 C++는 signed (the default)와 unsigned numbers를 지원한다. Java는 signed numbers만을 지원한다.

 

2.2.2 Unsigned Encodings

우리가 w개의 bits의 integer data type을 가진다고 가정하자. 우리는 $\overrightarrow{x}$로서 bit vector를 작성하는데, 이겅슨 전체 vector를 표기하기 위해서이다. 또는 그 vector 내의 개별 bits를 표기하기 위해 $[x_{w-1}, x_{w-2}, \dots, 0]$으로서 표기한다. $\overrightarrow{x}$를 binary notation에서 작성된 숫자로 다루어서, 우리는 $\overrightarrow{x}$의 unsigned interpretation를 얻는다. 우리는 이 해석을 한 함수 $B2U_w$ 로서 표현한다 (길이 w에 대해 "binary to unsigned"를 위한):

$$B2U_w(\overrightarrow{x}) \doteq \sum^{w-1}_{i=0} x_i 2^i \;\;\;\; (2.1)$$

이 방정식에서, 그 "$\doteq$" 표기는 좌변이 우변과 같다고 정의된다는 것을 의미한다. 그 함수 $B2U_w$는 길이 w의 0과 1의 strings을 nonnegative integers에 매핑한다. 예를들어, 그림 2.11은 그 mapping을 보여준다. B2U에 따라, bit vectors에서 다음의 경우에 정수들로:

$$B2U_4([0001]) = 0 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 0 + 0 + 0 + 1 = 1 \\ B2U_4([0101]) = 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 0 + 4 + 0 + 1 = 5 \\ B2U_4([1011]) = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 8 + 0 + 2 + 1 = 11 \\ B2U_4([1111]) = 1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 8 + 4 + 2 + 1 = 15 \\ (2.2)$$

그림에서, 우리는 길이가 $2^i$인 오른쪽을 향하는 blue bar로 각 비트 포지션 i를 나타낸다. 한 bit vector와 연결된 numeric value는 그러고나서 대응되는 bit values가 1인 bars의 combined length와 같다.

w bits를 사용하여 나타내어질 수 있는 값의 범위를 고려해보자. 그 가장 작은 값은 bit vector $[00\cdots0]$에 의해 주어지고, integer value 0을 갖는다. 그리고 가장 큰 값은 bit vector $[11\cdots1]$에 의해 주어지고, $UMax_w \doteq \sum^{w-1}_{i=0} 2^i = 2^w-1$의 정수값을 갖게된다. 4-bit case를 예시로 사용하여, 우리는 $UMax_4 = B2U_4([1111]) = 2^4 - 1 = 15$를 갖는다. 따라서, 그 함수 $B2U_w$는 $B2U_w:\{0, 1\}^w \rightarrow \{0, \dots, 2^w-1\}$의 매핑으로서 정의도리 수 있다.

그 unsigned binary representation은 0과 $2^w-1$사이의 모든 숫자가 w-bit value로서의 unique encoding을 갖는 중요한 특성을 가진다. 예를들어, 10진수 11에 대해 오직 한 개의 표현만이 있다. unsigned, 4-bit number인 [1011]. 이 특징은 수학적 용어에서 보여지는데, 함수 $B2U_w$는 bijection이다. - 그것은 단일 값을 길이가 w인 각 bit vector에 대한 unique value로 연관시킨다; 역으로 말해서, 0과 $2^w -1$사이의 각 정수는 길이가 w의 bit vector로서 unique binary representation을 갖는다.

 

2.2.3 Two's-Complement Encodings

많은 어플리케이션들에 대해, 우리는 음수를 또한 나타내고 싶어한다. 대부분의 signed numbers에 대한 공통된 컴퓨터 표기는 two's-complement form으로서 알려져있다. 이것은 그 word의 most significant bit이 negative weight를 갖는다고 해석하여 정의된다. 우리는 이 해석을 함수 $B2T_w$ ("binary to two's-complement" length w)로 표현한다:

$$B2T_w(\overrightarrow{x}) \doteq -x_{w-1} 2^{w-1} + \sum^{w-2}_{i=0} x_i 2^i \;\;\;\; (2.3)$$

그 most significant bit $x_{w-1}$은 또한 sign bit라고 불려진다. 그것의 "weight"는 $-2^{w-1}$이고, 이것은 unsigned representation에서 그것의 weight의 negation이다. 그 sign bit가 1로 설정될 때, 그 표현되는 값은 음수이고, 0으로 설정될 때, 그 값은 음수가 아니다. 예를들어, 그림 2.12는 그 B2T에 의한 매핑을 보여준다. 다음의 경우들에 대해 bit vectors에서 integers까지:

$$B2T_4([0001]) = -0 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 0 + 0 + 0 + 1 = 1 \\ B2T_4([0101]) = -0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 0 + 4 0 + 1 = 5 \\ B2T_4([1011]) = -1 \cdot 2^3 + 0 \cdot 2^2 + 1\cdot 2^1 + 1 \cdot 2^0 = -8 + 0 + 2 + 1 = -5 \\ B2T_4([1111]) = -1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = -8 +4 +2 +1 = -1\\ (2.4)$$

그림에서, 우리는 그 sign bit가 왼쪽으로 향하는 회색 bar로서 negative weightㄹ르 가진다는 것을 가리킨다. 한 bit vector와 관련된 numeric value는 그러고나서 가능한 leftward-pointing gray bar와 오른쪽을 향하는 blur bar의 조합에 의해 주어진다.

우리는 그림 2.11과 2.12 (뿐만 아니라 식 2.2와 2.4)에 대해 bit patterns들이 동일하지만, 그 most significant bit이 1일 때 값이 다르다는 것을 알게 된다. 왜냐하면 한 겨우에 그것은 +8 weight를 가지고, 다른 경우에 -8 weight를 가지기 때문이다.

w-bit two's complement number로서 나타내어질 수 있는 값들의 범위를 고려해보자. 가장 작은 나타낼 수 있는 값은 bit vector $[10 \cdots 0]$으로 주어진다 (negative weight로 bit를 설정하지만 나머지는 모두 clear한다), 그리고 $TMin_w \doteq -2^{w-1}$의 integer value를 갖는다. 그 가장 큰값은 bit vector $[01\cdots1]$에 의해 주어진다 (negative weight bit를 clear하지만, 모든 다른 것을 set한다), 그리고 $TMax_w \doteq \sum^{w-2}_{i=0}2^i = 2^{w-1} -1$의 integer value를 갖는다. 4-bit case를 예를들어, 우리는 $TMin_4 = B2T4([1000]) = -2^3 = -8$를 갖게되고, $TMax_4 = B2T_4([0111]) = 2^2 + 2^1 + 2^0 = 4 + 2 + 1 = 7$을 갖는다.

우리는 $B2T_w$가 길이가 w인 bit patterns을 $TMin_w$와 $TMax_w$사이의 숫자들로의 매핑이라는 것을 알 수 있다. 그리고 이것은 $B2T_w : \{0,1\}^w \rightarrow \{-2^{w-1} , \dots , 2^{w-1} -1 \}$로 쓰여질 수 있다. 우리가 unsigned representation과 함께 보았듯이, 표현 가능한 범위 내의 모든 숫자는 w-bit two's complement number로서 unique encoding을 가진다. 수학적 용어로, 우리는 그 함수 $B2T_w$가 bijection하다고 말한다 - 이것은 길이가 w인 각 bit vector를 unique value로 associate한다는 것이다; 역으로, $-2^{w-1}$과 $2^{w-1} -1$ 사이의 각 정수는 길이 w의 bit vector의 unique binary representation을 갖는다.

 

Practice Problem 2.17

Hexadeciaml	Binary	$B2U_4(\overrightarrow{x})$	$B2T_4(\overrightarrow{x})$
0xE	[1110]	$2^3 + 2^2 + 2^1 = 14$	$-2^3 + 2^2 + 2^1 = -2$
0x0	[0000]	$0$	$0$
0x5	[0101]	$2^2 + 2^0 = 5$	$2^2 + 2^0 = 5$
0x8	[1000]	$2^3 = 8$	$-2^3 = -8$
0xD	[1101]	$2^3 + 2^2 + 2^0$ = 13	$-2^3 + 2^2 + 2^0$ = -3
0xF	[1111]	$2^3 + 2^2 + 2^1 + 2^0$ = 15	$-2^3 + 2^2 + 2^1 + 2^0 = -1$

 

그림 2.13은 다른 word sizes에 대해 몇 가지 중요한 숫자에 대한 bit patterns과 numeric values를 보여준다. 그 처음 세 개는 $UMax_w$, $TMin_w$, 그리고 $TMax_w$의 값들의 관점에서 표현 가능한 정수의 범위를 준다. 우리는 뒤의 논의에서 종종 이러한 세 개의 특별한 값들을 언급할 것이다. 우리는 w가 context로 부터 추론될 수 있거나 논의에 중심이 되지 않을 때, 그 밑의 w를 빼고 $UMax$, $TMin$, $TMax$의 값들을 언급할 것이다.

몇 가지 요점들은 이러한 숫자들에 대해 강조할 만한 가치가 있다. 첫 째로, 그림 2.8과 2.9에서 관찰되듯이, 그 two's-complement range는 비대칭이다 : $|TMin| = |TMax| + 1$, 즉, TMin에 대응되는 양수가 없다. 우리가 보게 되듯이, 이것은 two's-complement arithmetic의 어떤 특이한 특성을 이끌게 되고, 미묘한 프로그램 버그의 원인이 될 수 있다.

Value	8	16	32	64
$UMax_w$	0xFF 255	0xFFFF 65,535	0xFFFFFFFF 4,294,967,295	0xFFFFFFFFFFFFFFFF 18,446,744,073,709,551,615
$TMin_w$	0x80 -128	0x8000 -32,768	0x80000000 -2,147,483,648	0x8000000000000000 -9,223,372,036,854,775,808
$TMax_w$	0x7F 127	0x7FFFF 32,767	0x7FFFFFFF 2,147,483,647	0x7FFFFFFFFFFFFFFF 9,223,372,036,854,775,807
-1	0xFF	0xFFFF	0xFFFFFFFF	0xFFFFFFFFFFFFFFFF
0	0x00	0x0000	0x00000000	0x000000000000000

Figure2.13

이 비대칭은 bit patterns의 절반 (sign bit가 1로 설정되는 것들)이 음수를 나타내는 반면, 나머지 절반 (sign bit가 0으로 설정되는 것들)이 음이 아닌 수를 나타내기 때문에 발생한다. 0은 nonnegative이기 때문에, 그것이 음수보다 양수를 덜 나타낼 수 있다는 것을 의미한다. 둘 째로, 그 최대 unsigned value는 two's-complement maximum의 두배 이상의 값이다: $UMax = 2TMax + 1$. two's-complement notation에서 음수를 나타내는 모든 비트 패턴들은 unsigned representation에서 양수가 된다. 그림 2.13은 또한 상수 -1과 0을 보여준다. -1은 $UMax$와 같은 bit 표기를 갖는다는 것을 보아라. 모두 1로 되어있는 string. Numeric value 0은 모든 표기에서 모두 0으로 되어있는 string으로서 나타내어진다.

C 표준은 signed integers가 two's complement form에서 나타내어지기를 요구하지 않지만, 거의 모든 머신들은 그렇게 한다. 모든 가능한 machines에 걸쳐 이식성을 최대화 하는 것을 걱정하는 프로그래머들은 그림 2.10에서 가리키는 범위를 넘어 나타낼 수 있는 값의 어떤 특정한 범위를 가정해서는 안된다. 뿐만 아니라, 그들은 signed numbers의 어떤 특정한 표현을 가정해서는 안된다. 반면에, 많은 프로그램들은 signed numbers의 two's-complement representation을 가정하여 쓰여지고, 그림 2.8과 2.9에서 보여지는 "일반적인" 범위들을 가정한다. 그리고 이러한 프로그램들은 넓은 범위의 머신들과 컴파일러에 걸쳐 portable하다. C library에 있는 <limits.h> 파일은 그 컴파일러가 동작하는 특정한 머신에서의 다른 integer data types에 대한 범위를 한정하는 상수의 집합을 정의한다. 예를들어, 그것은 signed와 unsigned integers의 범위를 설명하는 INT_MAX, INT_MIN, UINT_MAX를 정의한다. data type int가 w bits를 가지는 two's-complement machine에 대해, 이러한 상수들은 $TMax_w, TMin_w, UMax_w$의 값들에 대응된다.

 

Aside signed numbers의 대안 표기

signed numbers에 대한 두 가지 다른 표준 표기가 있다:

Ones' Complement : 이것은 most significant bit이 $-2^{w-1}$이 아니라, $-(2^{w-1} -1)$의 weight를 가진다는 것을 제외하고 two's complement와 같다:

$$B2O_w(\overrightarrow{x}) \doteq -x_{w-1}(2^{w-1} -1) + \sum^{w-2}_{i=0} x_i 2^i$$

Sign-Magnitude: 그 most significant bit은 나머지 비트들이 음수 또는 양수 가중치로 주어질지를 결정하는 sign bit이다:

$$B2S_w(\overrightarrow{x}) \doteq (-1)^{x_{w-1}} \cdot (\sum^{w-2}_{i=0} x_i 2^i)$$

이러한 두 표기는 숫자 0에 대한 두 개의 다른 인코딩이 있다는 호기심을 유발하는 특징을 가진다. 두 표기에서 $[00 \cdots 0]$은 $+0$으로 해석된다. 그 값 $-0$은 sign-magnitude form $[10 \cdots 0]$으로 나타내어지고, ones'-complement에서 $[11 \cdots 1]$로 나타내어질 수 있다. 비록 ones'-complement 표기를 기반으로 하는 머신들이 과거에 만들어졌을 지라도, 거의 모든 현대 머신들은 two's complement를 사용한다. 우리는 sign-magnitude encoding이 floating-point numbers와 함께 사용된다는 것을 보게 될 것이다. apostrophes의 다른 위치를 주목해라: Two's complement 와 Ones' complement. 그 용어 "two's complement"는 음이 아닌 x에 대해, 우리가 -x의 w-bit representation $2^w - x$ (single two)로 연산한다는 사실로 부터 발생한다. 그 용어 "ones' complement는 우리가 -x를 이 표기에서 $[111 \cdots 1] - x$ (여러개의 1들)로 연산할 수 있다는 특성에서 온다.

예를들어, 다음의 코드를 고려해라:

xxxxxxxxxx
short x = 12345;
short mx = -x;
​
show_bytes((byte_pointer) &x, sizeof(short));
show_bytes((byte_pointer) &mx, sizeof(short));

big-endian machine에서 작동될 때, 이 코드는 30 39와 cf c7을 출력한다. 이것은 x가 hexadecimal representation 0x3039를 가지는 반면, mx가 hexadecimal representation 0xCFC7를 가진다는 것을 가리킨다. 이것을 binary로 확장하여, 우리는 x에 대해 [0011000000111001]를 mx에 대해 [1100111111000111]의 bit patterns을 얻는다. 그림 2.14가 보여주듯이, 방정식 2.3은 이러한 두 비트 패턴들에 대해 values 12,345에와 -12,345를 만들어낸다.

Weight	12,345 Bit	12,345 Value	-12,345 Bit	-12,345 Value	53,191 Bit	53,191 Value
1	1	1	1	1	1	1
2	0	0	1	2	1	2
4	0	0	1	4	1	4
8	1	8	0	0	0	0
16	1	16	0	0	0	0
32	1	32	0	0	0	0
64	0	0	1	64	1	64
128	0	0	1	128	1	128
256	0	0	1	256	1	256
512	0	0	1	512	1	512
1,024	0	0	1	1,024	1	1,024
2,048	0	0	1	2,048	1	2,048
4,096	1	4,096	0		0	0
8,192	1	8,192	0		0	0
16,384	0	0	1	16,384	1	16,384
+-32,768	0	0	1	-32,768	1	32,768
Total		12,345		-12,345		53,191

Figure 2.14 12,345와 -12,345의 Two's-complement 표현, 과 53,191의 unsigned representation. 뒤에 두 개는 동일한 bit representations을 갖는다는 것에 주목해라.

 

Practice Problem 2.18

Chapter 3에서, 우리는 disassembler에의해 생성된 목록을 볼 것이다. 그것은 executable program file을 다시 좀 더 읽을 수 있는 ASCII form으로 바꿔주는 프로그램이다. 이러한 파일들은 많은 hexadecimal numbers를 포함하고, 일반적으로 two's complement form에서 값을 나타낸다. 이러한 숫자들을 인지할 수 있고, 그것들의 중요성을 이해하는 것 (예를들어, 그것들이 음수이거나 양수인지를)은 중요한 스킬이다.

다음의 목록에서 (오른쪽에서) A-J로 라벨이 붙은 라인들에 대해, 그 instruction names (sub, mov, and add)의 오른쪽에 보여지는 hexadecimal value를 그것들의 decimal과 대응되는 것으로 바꾸어라:

xxxxxxxxxx
8048337: 81 ec b8 01 00 00      sub $0x1b8,%esp                 A.
​
0x1b8 -> 0001 1011 1000 -> 256 + 128 + 32 + 16 + 8 -> 440
​
​
804833d: 8b 55 08               mov 0x8(%ebp),%edx
8048340: 83 c2 14               add $0x14,%edx                  B.
​
0x14 -> 0001 0100 -> 16 + 4 = 20
​
8048343: 8b 85 58 fe ff ff      mov 0xfffffe58(%ebp),%eax       C.
​
0xfffffe58 -> 1111 1111 1111 1111 1111 1110 0101 1000
           -> 1111 1111 1111 1111 1111 1110 0101 0111
           -> 0000 0000 0000 0000 0000 0001 1010 1000
           -> 256 + 128 + 32 + 8 = 424
           -> -424
​
8048349: 03 02                  add (%edx),%eax
804834b: 89 85 74 fe ff ff      mov %eax,0xfffffe74(%ebp)       D.
​
0xfffffe74 -> 1111 1111 1111 1111 1111 1110 0111 0100
           -> 1111 1111 1111 1111 1111 1110 0111 0011
           -> 0000 0000 0000 0000 0000 0001 1000 1100
           -> 256 + 128 + 8 + 4 = 396
           -> -396
​
​
8048351: 8b 55 08               mov 0x8(%ebp),%edx
8048354: 83 c2 44               add $0x44,%edx                  E.
​
0x44 -> 0100 0100 -> 64 + 4 = 68
​
8048357: 8b 85 c8 fe ff ff      mov 0xfffffec8(%ebp),%eax       F.
​
0xfffffec8 -> 1111 1111 1111 1111 1111 1110 1100 1000
           -> 1111 1111 1111 1111 1111 1110 1100 0111
           -> 0000 0000 0000 0000 0000 0001 0011 1000
           -> 256 + 32 + 16 + 8 = 312
           -> -312
​
804835d: 89 02                  mov %eax,(%edx)
804835f: 8b 45 10               mov 0x10(%ebp),%eax             G.
​
0x10 -> 0001 0000 = 16
​
8048362: 03 45 0c               add 0xc(%ebp),%eax              H.
​
0xc -> 1100 = 12
​
8048365: 89 85 ec fe ff ff      mov %eax,0xfffffeec(%ebp)       I.
​
0xfffffeec -> 1111 1111 1111 1111 1111 1110 1110 1100
           -> 1111 1111 1111 1111 1111 1110 1110 1011
           -> 0000 0000 0000 0000 0000 0001 0001 0100
           -> 256 + 16 + 4 = 276
           -> -276
​
804836b: 8b 45 08               mov 0x8(%ebp),%eax
804836e: 83 c0 20               add $0x20,%eax                  J.
​
0x20 -> 0010 0000 = 32
​
8048371: 8b 00                  mov (%eax),%eax

 

2.2.4 Conversions Between Signed and Unsigned

C는 다른 numeric data types 사이의 캐스팅을 허용한다. 예를들어, 변수 x가 int로 선언되어 있고, u가 unsigned로 선언되어 있다고 가정하자. 그 식 (unsigned) x는 x의 갑승ㄹ unsigned value로 바꾸고, (int) u는 u의 값을 signed integer로 바꾼다. signed value를 unsigned로 캐스팅하는 것 그리고 역으로 하는 것의 효과는 무엇이 되어야 하는가? 수학의 관점에서, 어떤 사람은 몇 가지 다른 컨벤션들을 상상할 수 있다. 명백히, 우리는 두 형태에서 나타내어질 수 있는 어떤 값을 보존하고 싶다. 반면에, negative value를 unsigned로 바꾸는 것은 zero를 만들지도 모른다. two's complement로 나타내어지기에 너무 큰 unsigned value를 바꾸는 것은 TMax를 만들지도 모른다. 그러나 C의 대부분 구현에 대해, 이 질문에 대한 답은 numeric 한 것이 아닌 bit-level 관점의 기반이 된다.

예를들어, 다음의 코드를 고려해라:

xxxxxxxxxx
short int v = -12345;
unsigned short uv = (unsigned short) v;
printf("v = %d, uv = %u\n", v, uv);

two's-complement machine에서 작동 될 때, 이것은 다음의 output을 생성한다:

xxxxxxxxxx
v = -12345, uv = 53191

우리가 여기에서 보는 것은 casting의 효과가 그 bit values를 동일하게 유지하는 것이지만, 이러한 비트들이 표현되는 것을 바꾸는 것이다. 우리는 그림 2.14에서 -12,345의 two's-complement representation이 53,191의 16-bit unsigned representation과 동일하다는 것을 보았다. short int를 unsigned short로 바꾸는 것은 그 numeric value를 바꾸었지만, bit representation는 그렇지 않다.

유사하게, 다음의 코드를 고려해라:

xxxxxxxxxx
unsigned u = 4294967295u;   /* UMax_32 */
int     tu = (int) u;
printf("u = %u, tu = %d\n", u, tu);

two's-complement machine에서 작동될 때, 이것은 다음의 output을 생성한다:

xxxxxxxxxx
u = 4294967295, tu = -1

...

이것은 대부분의 C 구현들이 같은 word size를 가진 signed and unsigned numbers사이의 변환을 처리하는 방법에 대한 일반적인 규칙이다 - numeric values가 변할지도 모르지만, bit patterns은 그렇지 않다. 이 원칙을 좀 더 수학적인 형태로 이해해보자. $B2U_w$와 $B2T_w$는 bijections이기 때문에, 그것들은 잘 정의된 inverses이다. $U2B_w$를 $B2U^{-1}_w$라고 하고, $T2B_w$를 $B2T^{-1}_w$라고 정의하자. 이러한 함숟르은 numeric value로부터 unsigned or two's-complement bit patterns을 준다. 즉, 범위 $0 \leq x \leq 2^w$에 있는 정수 x가 주어진다면, 그 함수 $U2B_w(x)$는 $x$의 유일한 $w$-bit unsigned representation을 준다. 유사하게, $x$가 범위 $-2^{w-1} \leq x < 2^{w-1}$의 범위에 있을 떄, 그 함수는 $T2B_w(x)$는 $x$의 unique $w$-bit two's complement representation을 준다. ...

이제 그 함수 $U2T_w$를 $U2T_w(x) \doteq B2T_w(U2B_w(x))$라고 정의하자. 이 함수는 $0$과 $2^w -1$ 사이의 숫자를 취하고, $-2^{w-1}$과 $2^{w-1} -1$의 사이의 숫자를 만들어 낸다. 거기에서 그 두 개의 숫자들은 동일한 bit representations을 가지지만, 그 인자가 unsigned라는 점을 제외한다. 반면 그 결과는 two's-complement representation이다. 유사하게, $-2^{w-1}$과 $2^{w-1} -1$사이의 $x$에 대해, 그 함수 $T2U_w$는 , $T2U_w(x) \doteq B2U_w(T2B_w(x))$로 정의된, $x$의 two's-complement representation과 같은 unsigned representation을 가진 숫자를 만들어낸다.

...

 

Practice Problem 2.19

문제 2.17를 풀 때 너가 채웠던 테이블을 사용하여, 함수 $T2U_4$를 설명하는 다음의 테이블을 채워라:

x	$T2U_4(x)$
-8	8
-3	13
-2	14
-1	15
0	0
5	5

signed number x와 그것의 unsigned counterpart $T2U_w(x)$사이의 관계를 더 잘 이해하기 위해, 우리는 그것들이 numerical relationship을 끌어내기 위해 동일한 bit representations을 가진 다는 사실을 사용할 수 있다. Equations 2.1과 2.3를 비교하여, 우리는 bit pattern $\overrightarrow{x}$에 대해, 만약 우리가 $B2U_w(\overrightarrow{x}) - B2T_w(\overrightarrow{x})$의 차이를 계산한다면, 0에서 $w - 2$까지의 bits들에 대한 weighted sums은 서로를 상쇄시킬 것이고, 다음의 값을 만든다 : $B2U_w(\overrightarrow{x}) - B2T_w(\overrightarrow{x}) = x_{w-1}(2^{w-1}- -2^{w-1}) = x_{w-1} 2^w$. 이것은 $B2U_w(\overrightarrow{x}) = x_{w-1}2^w + B2T_w(\overrightarrow{x})$의 관계를 준다. 만약 우리가 $\overrightarrow{x} = T2B_w(x)$라고 한다면, 그러면 우리는 다음을 가진다.

$$B2U_w(T2B_w(x)) = T2U_w(x) = x_{w-1}2^w + x\;\;\;\; (2.5)$$

이 관계는 unsigned와 two's complement 대수 사이의 관계를 증명하는데 유용하다. x의 two's-complement 표현에서, $x_{w-1}$ 비트는 x가 음수인지 아닌지를 결정하고, 다음을 준다

$$T2U_w(x) = \Bigg\{ \begin{split} & x + 2^w, \;\; x < 0 \\ & x, \;\; x \geq 0 \end{split} \\ (2.6)$$

예제로, 그림 2.15는 B2U와 B2T 함수가 w = 4에 대해 bit patterns에 대해 값을 어떻게 할당 하는지를 비교한다. two's-complement case에 대해, most significant bit는 sign bit의 역할을 하고, 우리는 회색의 왼쪽을 향하는 bar로서 그린다. unsigned case에 대해, 이 bit는 positive weight를 가지고, 우리는 검정색의 오른쪽을 향하는 bar로 보여준다. two's complement에서 unsigned로 갈 때, most significant bit는 그것의 가중치를 -8에서 +8로 바꾼다. 결과적으로, two's-complement representation에서 음수인 값은 unsigned representation으로 $2^4 = 16$만큼 증가한다. 따라서 -5는 +11이 되고, -1은 +15가 된다.

그림 2.16는 $T2U$의 일반 행동을 설명한다. 그것이 보여주듯이, signed number를 그것의 unsigned counterpart로 매핑할 때, 음수는 큰 양수로 변환되고, 반면에 음이 아닌 수들은 변하지 않는다.

 

Practice Problem 2.20

방정식 2.6이 문제 2.19를 풀 때 너가 만든 테이블의 entires에서 어떻게 적용되는지 설명해라.

x	$T2U_4(x)$	$T2U_w(x)$
-8	8	$-8 + 2^4 = 8$
-3	13	$-3 + 2^4 = 13$
-2	14	$-2 + 2^4 = 14$
-1	15	$-1 + 2^4 = 15$
0	0	$0$
5	5	$5$

 

다른 방향으로 가서, 우리는 unsigned number $u$와 그것의 signed counterpart $U2T_w(u)$ 사이의 관계를 도출하고 싶다. 둘 다 $\overrightarrow{u} = U2B_w(u)$의 bit representations을 가지고. 우리는 다음을 가진다

$$B2T_w(U2B_w(u)) = U2T_w(u) = -u_{w-1}2^w + u \;\; (2.7)$$

$u$의 unsigned representation에서, $u_{w-1}$ 비트는 $u$가 $2^{w-1}$보다 더 크거나 같은지를 결정하고, 다음을 주게 된다

$$U2T_w(u) = \Bigg\{ \begin{split} & u, & \;& u< 2^{w-1} \\ & u - 2^w, &\; & u \geq 2^{w-1} \end{split} \\ (2.8)$$

이 행동은 그림 2.17에서 그려진다. small ($< 2^{w-1}$) 숫자들에 대해, unsigned에서 signed로의 변환은 numeric value를 보존한다. Large ($\geq 2^{w-1}$) 숫자들은 음수로 변환된다.

요약해서, 우리는 unsigned와 two's-complement representations 사이의 양 방향으로의 변환의 결과를 고려했었다. $0 \leq x < 2^{w-1}$의 범위에 있는 x 값들에 대해, 우리는 $T2U_w(x) = x$를 가지고 $U2T_w(x) = x$를 가진다. 즉, 이 범위에 있는 숫자들은 동일한 unsigned and two's-complement 표현을 갖는다. 이 범위 밖에 있는 값들에 대해, 그 변환은 $2^w$를 더하거나 뺀다. 예를들어, 우리는 $T2U_w(-1) = -1 + 2^w = UMax_w$를 가진다. 0에 가장 가까운 음수는 가장 큰 unsigned number로 매핑된다. 다른 쪽 끝에서, $T2U_w(TMin_w) = -2^{w-1} + 2^w = 2^{w-1} = TMax_w + 1$이라는 것을 알 수 있다. 가장 negative (음수중에서 가장 작은) 숫자는 positive, two's-complement 숫자의 범위 밖에 있는 unsigned number로 매핑된다. 그림 2.14의 예제를 사용하여, 우리는 $T2U_16(-12,345) = 65,536 + -12,345 = 53,191$라는 것을 알 수 있다.

 

2.2.5 Signed vs. Unsigned in C

그림 2.8과 2.8에서 가리켜지듯이, C는 모든 그것의 integer data types에 대해 signed와 unsigned arithmetic 둘 다 지원한다. 비록 그 C 표준이 signed numbers의 특정한 representation을 명시하지 않을지라도, 거의 모든 머신들은 two's complement를 사용한다. 일반적으로 대부분의 숫자들은 default로 signed이다. 예를들어, 12345, 0x1A2B같은 상수를 선언할 때, 그 값은 signed로 고려된다. 접미사로 'U' 또는 'u'를 붙이는 것은 unsigned constant를 만든다. 예를들어 12345U 또는 0x1A2Bu.

C는 unsigned와 signed 사이의 변환을 허용한다. 그 규칙은 밑의 bit representation이 바뀌지 않는 것이다. 따라서, two's-complement machine에서, 그 결과는 unsigned에서 signed로 바꿀 때 $U2T_w$함수를 적용하는 것이고 signed에서 unsigned로 바꿀 때 $T2U_w$를 적용하는 것이다. 거기에서 $w$는 그 data type에 대한 bits의 개수이다.

Conversions은 explicit casting에 의해 발생할 수 있다. 다음의 코드에서 처럼:

xxxxxxxxxx
1   int tx, ty;
2   unsigned ux, uy;
3
4   tx = (int) ux;
5   uy = (unsigned) ty;

대안적으로 그것들은, 한 type의 expression이 다른 것의 변수로 할당될 때 implicitly하게 발생할 수 있다, 다음의 코드에서 처럼:

xxxxxxxxxx
1   int tx, ty;
2   unsigned ux, uy;
3
4   tx = ux;    /* Cast to signed */
5   uy = ty;    /* Cast to unsigned */

printf로 numeric values를 출력할 때, 그 지시어 %d, %u, 그리고 %x가 한 수를 각각 signed decimal, unsigned decimal, 그리고 hexadecimal format으로 출력하기 위해 사용된다. printf가 어떠한 type information을 이용하지 않는다는 것에 주목해라. 그래서, type int의 값을 directive %u로 출력하고, unsigned type의 값을 directive %d로 출력하는 것이 가능하다. 예를들어 다음의 코드를 고려해라:

xxxxxxxxxx
1   int x = -1;
2   unsigned u = 2147483648;    /* 2 to the 31st */
3
4   printf("x = %u = %d\n", x, x);
5   printf("u = %u = %d\n", u, u);

32-bit machine에서 작동할 때, 그것은 다음을 출력한다:

xxxxxxxxxx
x = 4294967295 = -1
u = 2147483648 = -2147483648

두 경우에, printf는 그 단어를 처음에 그것이 unsigned number를 나타내는 것처럼 출력하고, 두 번째를 signed number를 나타내는 것처럼 나타낸다. 우리는 conversion routines을 볼 수 있다: $T2U_{32}(-1) = UMax_{32} = 2^{32} - 1$ 그리고 $U2T_{32}(2^{31}) = 2^{31} - 2^{32} = -2^{31} = TMin_{32}$

어떤 이상한 행동이 signed and unsigned quantities의 조합을 포함하는 expressions의 C의 처리에 의해 발생한다. 한 operand가 signed이고 다른 것이 unsigned인 상황에서 한 연산이 수행될 때, C는 implicitly하게 그 signed argument를 unsigned로 캐스팅하고, 그 숫자가 음수가 아닌 것처럼 가정하고 연산을 수행한다. 우리가 보게 되듯이, 이 컨벤션은 standard arithmetic operations에 대해 작은 차이를 만들지만, <와 > 같은 relational operations에 대해 직관적이지 않은 결과들을 이끈다. 그림 2.18은 몇 가지 sample relational expressions을 보여주고, 그것들의 최종 evaluations을 보여준다. 이것은 two's-complement representation을 사용하는 32-bit machine를 가정한다. -1 < 0U의 비교를 고려해라. 두 번째 operand가 unsigned이기 때문에, 그 첫 번째 것은 implicitly하게 unsigned로 캐스팅 되고, 그러므로 그 expression은 4294967295U < 0U의 비교와 같다. 그리고 이것은 물론 false이다. 그 다른 케이스들은 비슷한 분석들에 의해 이해된다.

Expressions	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

Figure 2.18 C promotion rules의 결과. 비직관적인 케이스들은 *로 마킹되어 있다. 비교의 operand중 하나가 unsigned일 때, 다른 operand는 implicitly하게 unsigned로 캐스팅 된다. 우리가 $TMin_{32}$를 `-2147483647-1`로 쓴 이유에 대해 Web Aside Data:TMin를 보아라.

 

Practice Problem 2.21

식들이 two's-complement 연산을 사용하는 32-bit machine에서 구해진다고 가정하여, 그림 2.18의 스타일대로 casting의 결과와 relataional operations의 결과를 설명하는 다음의 테이블을 채워라.

Expression	Type	Evaluation	이유
-2147483647-1 == 2147483648U	unsigned	1	-2147483647-1은 two's complement representation에서 -2147483648로 1000 0000의 bit representation을 갖는데, 하지만 우측 operand가 unsigned로 이게 다시 unsigned로 implicitly하게 캐스팅 되는데, 이 때, 이 값은 unsigned에서는 $2^{31} = 2147483648$로 같은 값이 된다.
-2147483647-1 < 2147483647	signed	1	단순 signed 비교.
-2147483647-1U < 2147483647	unsigned	0	-2147483647-1U가 있어서 -2147483647은 unsigned로 implicitly하게 캐스팅 된다. 이 때 bit representation이 1000 0000이므로, $2^{31} = 2147483648$이 되고, 그것에 -1를 빼면, 2147483647이 된다. 따라서 <의 우측에 있는 것도 unsigned로 바뀔 것인데 캐스팅은 상관없고, 값이 같으므로 Evaluation하면 0이 나온다.
-2147483647-1 < -2147483647	signed	1	단순 signed 비교
-2147483647-1U < -2147483647	unsigned	1	위에서 설명했듯이 -2147483647-1U는 unsigned로 캐스팅되어 연산되므로 2147483647의 값이 되고, <의 우측에 있는 것도 unsigned로 바뀌어 2147483648의 값이 된다. 따라서 그것보다 작으므로 1이 나온다.

Web Aside Data:TMIN Writing TMin in C

그림 2.18과 문제 2.21에서, 우리는 조심스럽게 $TMin_{32}$를 -2147483647-1로 썼다. 그것을 단순히 -214743648 또는 0x8000 0000으로 쓰지 않았을까? C header file limits.h를 보면, 우리는 그것들이 우리가 $TMin_{32}$와 $TMax_{32}$를 썼을 때와 같은 방법으로 그것들 사용하는 것을 보게 된다:

xxxxxxxxxx
/* Minimum and maximum values a 'signed int' can hold. */
#define INT_MAX     2147483647
#define INT_MIN     (-INT_MAX - 1)

불행하게도, two's-complement representation과 C의 conversion rules 사이의 비대칭성 사이의 흥미로운 상호작용은 우리가 $TMin_{32}$를 이렇게 보통의 방법이 아니게 작성하도록 강요한다. 비록 이 문제를 이해하는 것이 C언어 표준의 애매한 구석 중의 하나를 파고드는 것을 요구할지라도, integer data types과 표기의 미묘함을 이해하는 데 도움이 될 것이다.

 

2.2.6 Expanding the Bit Representation of a Number

한 가지 공통된 연산은 같은 numeric value를 유지하면서 다른 word sizes를 가진 integers 사이에서의 변환이다. 물론, 이것은 destination data type이 desired value를 표현하기에 너무 작을 때 가능하지 않을지도 모른다. 그러나, 더 작은 data type에서 더 큰 type으로 바꾸는 것은 항상 가능해야 한다. unsigned number에서 더 큰 data type으로 바꾸기 위해서, 우리는 간단하게 그 representation에 leading zeros를 더할 수 있다; 이 연산은 zero extension이라고 알려져 있다. two's-complement number를 더 큰 data type으로 바꾸기 위해서, 그 규칙은 sign extension을 수행하는 것인데, 이것은 그 representation에 most significant bit의 복사본들을 추가하는 것이다. 따라서, 만약 우리의 original value가 bit representation $[x_{w-1}, x_{w-2}, \dots, x_0]$이라면, 그 확장된 representation은 $[x_{w-1}, \dots, x_{w-1}, x_{w-1}, x_{w-2},\dots, 0]$이다. (우리는 sign extension의 역할을 강조하기 위해 sign bit $x_{w-1}$를 파란색으로 보여준다.)

한 예제로서, 다음의 코드를 고려해라:

xxxxxxxxxx
1   short sx = -12345;          /* -12345 */
2   unsigned short usx = sx;    /* 53191 */
3   int     x = sx;             /* -12345 */
4   unsigned ux = usx;          /* 53191 */
5
6   printf("sx = %d:\t", sx);
7   show_bytes((byte_pointer) &sx, sizeof(short));
8   printf("usx = %u:\t", usx);
9   show_bytes((byte_pointer) &usx, sizeof(unsigned short));
10  printf("x   = %d:\t", x);
11  show_bytes((byte_pointer) &x, sizeof(int));
12  printf("ux  = %u:\t", ux);
13  show_bytes((byte_pointer) &ux, sizeof(unsigned));

two's-complement representation을 사용하는 32-bit big-endian 머신에서 작동될 때, 이 코드를 다음의 output을 출력한다

xxxxxxxxxx
sx  = -12345:   cf c7
usx = 53191:    cf c7
x   = -12345:   ff ff cf c7
ux  = 53191:    00 00 cf c7

...

우리는 그 sign extension이 작동하는 것을 정당화 할 수 있는가? 우리가 증명하고 싶은 것은

$$B2T_{w+k}([x_{w-1}, \dots, x_{w-1}, x_{w-1}, x_{w-2}, \dots, x_0]) = B2T_w([x_{w-1}, x_{w-2}, \dots , x_0])$$

여기에서 좌변의 식에서 우리는 bit $x_{w-1}$의 k개의 추가 복사본을 만들었다. 그 증명은 k에 대한 유도를 따른다. 즉, 만약 우리가 1 bit씩 연장시키는 그 sign이 numeric value를 보존한다면, 그러면 이 특성은 임의의 비트 개수로 sign을 확장시킬 때도 유효할 것이다. 따라서, 그 작업은 다음을 증명하는 것으로 된다

$$B2T_{w+1}([x_{w-1}, x_{w-1}, x_{w-2}, \dots, x_0]) = B2T_w([x_{w-1}, x_{w-2}, \dots , x_0])$$

Equation 2.3으로 좌변식을 확장시키는것은 다음을 준다:

$$\begin{split} B2T_{w+1}([x_{w-1}, x_{w-1}, x_{w-2}, \dots, x_0]) & = -x_{w-1}2^w + \sum^{w-1}_{i=0} x_i 2^i \\ & = -x_{w-1}2^w + x_{w-1}2^{w-1} + \sum^{w-2}_{i=0} x_i 2^i \\ & = -x_[w-1](2^w - 2^{w-1}) + \sum^{w-2}_{i=0} x_i 2^i \\ & = -x_{w-1}2^{w-1} + \sum^{w-2}_{i=0} x_i 2^i\\ & = B2T_w([x_{w-1}, x_{w-2}, \dots, x_0]) \end{split}$$

우리가 이용하는 주된 property는 $2^w - 2^{w-1} = 2^{w-1}$이다. 따라서, weight $-2^w$의 bit를 추가하고 weight $2^{w-1}$를 가진 것으로 $-2^{w-1}$를 가진 비트로 변하는 것의 combined effect는 원래의 numeric value를 보존하는 것이다.

 

Pratice Problem 2.22

Equatnion 2.3을 적용하여 다음의 bit vectors의 각각이 -5의 two's-complement representation라는 것을 보여주어라:

A. [1011]

B. [11011]

C. [111011]

$$\begin{split} & [1011] = -2^3 + 2^1 + 2^0 = -8 + 2 + 1 = -5 \\ & [11011] = -2^4 + 2^3 + 2^1 + 2^0 = -16 + 8 + 2 + 1 = -5 \\ & [111011] = -2^5 + 2^4 + 2^3 + 2^1 + 2^0 = -32 + 16 + 8 + 2 + 1 = -5 \end{split}$$

두 번째와 세 번째 bit vectors가 sign extension으로 첫 번째로부터 도출된다는 것을 관찰해라. 첫 번째에서 sign비트를 빼면 중요한 것은 +2와 +1이다. B와 C로 내려가면서 그 +2 +1를 제외하고 추가되는 것들은 결국에 똑같은 A에서의 -8를 만들고 있다. 즉, $-2^w + 2^{w-1} + \cdots$가 되고 있는데 이것은 사실 $-(2^w - 2^{w-1} - 2^{w-2} - \cdots )$가 되는 것이고 이것은 다시 위에서 설명한 특성에 의해 $-(2^{w-1} - 2^{w-2} - \cdots)$가 되고 그리고 다시 $-(2^{w-2} - 2^{w-3} - \cdots)$로 쭉가게 된다. 따라서 초기의 sign bit였던 -8를 만들게 된다.

 

만들 가치가 한 가지 요점은 한 data size에서 다른 것으로 그리고 unsigned와 signed 사이의 변환의 상대적인 순서는 한 프로그램의 행동에 영향을 미칠 수 있다. 다음의 코드를 고려해라:

xxxxxxxxxx
1   short sx = -12345;      /* -12345 */
2   unsigned uy = sx;       /* Mystery! */
3
4   printf("uy  = %u\t", uy);
5   show_bytes((byte_pointer) &uy, sizeof(unsigned));

big-endian machine에서 작동할 때, 이 코드는 다음의 output이 출력되도록 한다:

xxxxxxxxxx
uy = 4294954951:    ff ff cf c7

이것은 short에서 unsigned로 변환할 때, 우리는 처음에 그 size를 변하게하고, 그러고나서 signed에서 unsigned로 바꾼다는 것을 보여준다. 즉, (unsigned) sx는 (unsigned)(int)sx와 동일하다는 것이고, 4,294,954,951의 값이 구해지고, 53,191의 값으로 구해지는 (unsigned) (unsigned short)sx가 아니라는 것이다. 정말로, 이 컨벤션은 C standards에 의해 요구되는 것이다.

 

Practice Problem 2.23

다음의 C 함수들을 고려해라:

xxxxxxxxxx
int fun1(unsigned word) {
    return (int) ((word << 24) >> 24);
}
​
int fun2(unsigned word) {
    return ((int) word << 24) >> 24;
}

이러한 것들이 two's-complement 연산을 사용하는 32-bit word size의 머신에서 실행된다고 가정하자. 또한 signed values의 right shifts가 arithmetically 수행된다고 가정하고, unsigned values의 right shifts가 logically 수행된다고 가정하자.

A. 몇 가지 예제의 arguments에 대해 이러한 함수들의 결과를 보여주는 다음의 표를 채워라. hexadecimal representation으로 작업하는게 더 편하다는 것을 ㅇ라게 될 것이다. hex digits 8부터 F가 그것들 자신의 significant bits가 1고과 같다는 것을 기억해라.

w	fun1(w)	fun2(w)
0x0000 0076	(word << 24) -> 0x7600 0000 (0x 7600 0000 >> 24) -> 0x0000 0076 (int)(0x0000 0076) -> 동일	(int)word -> 동일 0x0000 0076 << 24 -> 0x7600 0000 0x7600 0000 >> 24 -> 0x0000 0076
0x8765 4321	(word << 24) -> 0x2100 0000 (0x2100 000 >> 24) -> 0x0000 0021 (int)하면 동일임	(int)word -> 동일 0x8765 4321 << 24 -> 0x2100 0000 0x2100 0000 >> 24 -> 0x0000 0021
0x0000 00C9	(word << 24) -> 0xC900 0000 (0xC900 0000 >> 24) -> 0x0000 00C9 (unsigned)여서 (int)하면 동일임	(int)word -> 동일 0x0000 00C9 << 24 -> 0xC900 0000 0xC900 0000 >> 24 -> 0xFFFF FFC9 (int의 arithmetic right shift여서)
0xEDCB A987	(word << 24) -> 0x8700 0000 0x8700 0000 >> 24 -> 0x0000 0087 (unsigned)여서 (int)하면 동일	(int) word -> 동일 0xEDCB A987 << 24 -> 0x8700 0000 0x8700 0000 >> 24 -> 0xFFFF FF87 (int의 arithmetic right shift여서)

B. 이러한 함수들 각각이 수행하는 유용한 연산을 words로 설명해라. 음,,, 내 생각엔 fun1의 경우 32bit unsigned integer값의 low bit 8의 값만을 가져오기 위해서 사용할 것 같고, fun2의 경우 fun2의 경우 low bit 8의 값을 가져오는데 parameter의 most significant bit가 1이 set되어 있으면 음수로 그 값을 가져오게 하는것 같다. 정확히 뭐에 유용한지는 모르겠다.

Answer : Function fun1는 인자의 low-order 8bits의 값을 가져오고, 이것은 0에서 255사이의 값을 준다. Function fun2는 argument의 low-order 8bits 값을 가져오지만, 그것은 또한 sign extension을 한다. 그 결과는 -128과 127사이의 값이다.

 

2.2.7 Truncating Numbers

한 값을 추가 비트들로 확장하기 보다, 우리가 한 숫자를 나타내는 비트들의 개수를 줄인다고 가정해보자. 예를들어 이것은 코드에서 다음처럼 발생한다:

xxxxxxxxxx
1   int     x = 53191;
2   short   sx = (short) x;     /* -12345 */
3   int     y = sx;             /* -12345 */

일반적인 32-bit machine에서, 우리가 x를 short가 되도록 캐스팅할 때, 우리는 32-bit int를 16-bit short int로 줄인다. 우리가 이전에 보았듯이 ,이 16-bit pattern는 -12,345의 two's-complement representation이다. 우리가 이것을 int로 다시 캐스팅할 때, sign extension이 그 상위 16bits들을 1로 설정할 것이고, -12,345의 32-bit two's complement representation을 만든다.

w-bit number $\overrightarrow{x} = [x_{w-1}, x_{w-2}, \dots, x_0]$을 k-bit number로 줄일 때, 우리는 상위 $w - k$ bits를 떨어뜨리고, bit vector $\overrightarrow{x}' = [x_{k-1}, x_{k-2}, \dots, x_0]$를 준다. 한 숫자를 truncate하는 것은 그것의 값을 바꿀 수 있다 - 즉 overflow의 형태이다. 우리는 이제 무슨 numeric value가 만들어질지 조사한다. unsigned number x에 대해, 그것을 k개의 bits로 truncate하는 것의 결과는 $x \;mod\; 2^k$를 연산하는 것 과 같다. 이것은 Equation 2.1에 대해 나머지 연산을 적용함으로써 보여질 수 있다:

$$\begin{split} B2U_w([x_{w-1}, x_{w-2}, \dots, x_0]) \; mod \; 2^k & = \bigg[ \sum^{w-1}_{i=0} x_i 2^i \bigg] \; mod \; 2^k \\ & = \bigg[ \sum^{k-1}_{i=0} x_i 2^i \bigg] \; mod \; 2^k \\ & = \sum^{k-1}_{i=0} x_i 2^i \\ & = B2U_k ([x_{k-1}, x_{k-2}, \dots, x_0]) \end{split}$$

이 유도에서, 우리는 어떤 $i \geq k$에 대해 $2^i \; mod \; 2^k = 0$라는 특성과 $\sum^{k-1}_{i=0} x_i2^i \leq \sum^{k-1}_{i=0} 2^i = 2^k - 1 < 2^k$의 특성을 이용한다.

two's-complement number x에 대해, 유사한 argument는 $B2T_w([x_{w-1}, x_{w-2}, \dots, x_0]) \; mod \; 2^k = B2U_k([x_{k-1}, x_{k-2}, \dots, x_0])$를 보여준다. 즉, $x \; mod \; 2^k$는 $[x_{k-1}, x_{k-2}, \dots, x_0]$의 bit-level representation을 가지는 unsigned number로 나타내어질 수 있다. 그러나, 일반적으로, 우리는 그 truncated number를 signed인것 처럼 다룬다. 이것은 numeric vluae $U2T_k(x\; mod \; 2^k)$를 가질 것이다.

요약하여, unsigned numbers를 truncation하는 것의 결과는

$$B2U_k([x_{k-1}, x_{k-2}, \dots, x_0]) = B2U_w([x_{w-1}, x_{w-2}, \dots, x_0]) \; mod \; 2^k, \;\;\;\;\; (2.9)$$

이고, tw's-complement numbers에 대한 결과는

$$B2T_k([x_{k-1}, x_{k-2}, \dots, x_0]) = U2T_k(B2U_w([x_{w-1}, x_{w-2}, \dots, x_0]) \; mod \; 2^k) \;\;\;\;\; (2.10)$$

 

Practice Problem 2.24

우리가 4-bit value (hex digits 0부터 F까지 나타내어지는)를 3-bit value (hex digits 0부터 7까지 나타내어지는)로 truncate한다고 가정하자. 몇 가지 경우들에 대한 이 truncation의 결과를 보여주는 아래의 표를 채워라. 그러한 bit patterns의 unsigned와 two's complement 해석의 관점에서

Hex Original	Hex Truncated	Unsigned Original	Unsigned Truncated	Two's-C Original	Two's-C Truncated
0 [0000]	0	0	0 [000]	0 [0000]	0 [000]
2 [0010]	2	2	2 [010]	2 [0010]	2 [010]
9 [1001]	1	9	1 [001]	-7 [1001]	1 [001]
B [1011]	3	11	3 [011]	-5 [1011]	3 [011]
F [1111]	7	15	7 [111]	-1 [1111]	-1 [111]

Answer : Equation 2.9에서 말했듯이, unsigned values에 대한 이 trunaction의 결과는 간단히 8로 나머지 연산하여 나머지 값을 차즌ㄴ 것이다. signed values에 대한 trunation의 결과는 좀 더 복잡하다. Equation 2.10에 따라서, 우리는 처음에 그 인자의 8로 나눈 나머지 값을 연산한다. 이것은 인자 0에서 7까지에 대해서는 0에서 7까지의 값을 주고, -8에서 -1에 대해서도 그런다. 그러고나서 $U2T_3$를 이러한 나머지에 적용하는데, 0~3의과 -4 ~ -1의 sequences의 두 반복을 주게 된다.

 

2.2.8 Advice on Signed vs. Unsigned

우리가 보았듯이, signed에서 unsigned로의 implicit casting은 어떤 비직관적인 행동을 이끌게 된다. 비직관적인 특징들은 종종 프로그램 버그를 만들게 되고, implicit casting의 늬앙스를 포함하는 것들은 특별히 보기에 어려울 수 있다. 그 캐스팅은 코드에서 어떠한 명백하 가리키는게 없이 발생할 수 있기 때문에, 프로그래머들은 종종 그것의 결과를 간과한다.

다음의 두 practice problems은 implicit casting과 unsigned data type에 의해 발생할 수 있는 몇 가지 미묘한 에러들을 보여준다.

 

Practice Problem 2.25

array a의 원소들을 합하려고 하는 다음의 코드를 고려해라. 거기에서 원소들의 개수는 parameter length에 의해 주어진다:

x
1   /* WARNING: This is buggy code */
2   float sum_elements(float a[], unsigned length) {
3       int i ;
4       float result = 0;
5       
6       for (i = 0; i <= length - 1; i++)
7           result += a[i];
8       return result;
9   }

argument length가 0과 같을 때 동작할 때, 이 코드는 0.0을 반환해야 한다. 대신에 그것은 메모리 에러를 만난다. 왜 이것이 발생하는지를 설명해라. 이 코드가 어떻게 수정될 수 있는지를 보여주어라.

length가 0인데 거기에 -1빼게 된다면, unsigned 상태에서 뺄셈을 진행하게 되는데 unsigned 0값에 -1를 하면 underflow가 발생하므로 uint32의 max값이 되어버린다. 따라서 파라미터 unsigned length를 int length로 바꾸면 된다.

 

Practice Problem 2.26

한 string이 다른 것보다 더 긴지를 결정하는 함수를 작성하는 과제를 받았다. 너는 다음의 선언을 가지는 strlen의 string library function을 이용해야 한다:

xxxxxxxxxx
/* Prototype for library function strlen */
size_t strlen(const char* s);

여기에 그 함수에 대한 너의 첫 번째 시도가 있다:

xxxxxxxxxx
/* Determine whether string s is longer than string t */
/* WARNING: This function is buggy */
int strlonger(char *s, char *t) {
    return strlen(s) - strlen(t) > 0;
}

너가 어떤 샘플 데이터에 대해 이것을 테스트 할 때, 꽤 잘 작동하지 않는 것처럼 보인다. 너는 더 조사하고, data type size_t가 stdio.h에서 unsigned int로 (typedef를 통해) 정의되어 있다고 결정했다.

A. 어떤 케이스들에서 이 함수는 부정확한 결과를 낼 것인가?

t의 문자 길이가 s의 문자 길이보다 더 클 때이다. 왜냐하면 unsigned끼리에서의 연산에서 음수가 나올 수 없기 때문이다.

B. 이 부정확한 결과가 어떻게 오는지 설명해라.

위에서 설명함

C. 그것이 믿을만하게 작동하도록 코드를 고칠 방법을 보여주어라.

x
int strlonger(char* s, char * t) {
    return strlen(s) > strlen(t);
}

 

우리는 unsigned arithmetic의 미묘한 기능들, 그리고 특히 signed에서 unsigned로의 변환이 에러나 취약성으로 이끌 수 있는 여러 방법들을 보았다. 그러한 버그를 피하는 한 가지 방법은 결코 unsigned numbers를 사용하지 않는 것이다. 사실, C를 제외한 어떤 언어들은 unsigned integers를 지원하지 않는다. 명백히, 이러한 다른 언어 설계자들은 그것들을 가치있다기 보다는 문제로서 보았었다. 예를들어, Java는 오직 signed integers만을 지원하고, 그것들은 two's-complement arithmetic으로 구현되어야 하는 것을 요구한다. normal right shift operator >>는 arithmetic shift를 수행하도록 보장된다. 그 특별한 operator >>>는 logical right shift를 수행하기 위해 정의된다.

Unsigned values는 numeric interpretation이 없는 bits의 집합으로서 words를 생각하기 원할 때 유용하다. 예를들어, 한 word를 다양한 Boolean conditions를 묘사하는 flags로 packing할 때 이것이 발생한다. Addresses는 본질 상 unsigned이다. 그래서 시스템 프로그래머들은 unsigned types이 도움이 된다는 것을 안다. Unsigned values는 또한 modular arithmetic과 multiprecision arithmetic를 위한 수학 packages를 구현할 떄 또한 유용하다. 거기에서 숫자들은 words의 arrays로 나타내어진다.