[시스템소프트웨어] 02. 정보의 표현과 처리

교재: 컴퓨터 시스템 (Computer Systems - A Programmer's Perspective, Randal E. Bryant, David R. O'Hallaron, 제3판, 김형신 옮김, PEARSON, 2016.08.31)

현대의 컴퓨터는 두 개의 값을 갖는 신호로 표현되는 정보를 저장하고 처리한다. 이 낮은 수준의 이진수인 비트는 디지털 혁명의 근원이다. 두 개의 값을 갖는 신호를 저장하고 계산하기 위한 전자회로는 매우 간단하고 안정적이어서 수백만에서 심지어 수천만 회로를 단 한 개의 실리콘 칩에 집적할 수 있을 정도다.

이 장에서 우리는 세 개의 가장 중요한 숫자 표현에 대해 살펴본다. 비부호형 인코딩은 전통적인 이진수 표시를 사용하며, 0 이상의 수를 표시한다. 2의 보수 인코딩은 양수 또는 음수 값을 갖는 부호형 정수를 표시하는 가장 일반적인 방법이다. 부동소수점 인코딩은 2진수 버전의 소수를 표시하기 위한 과학적 표시방법이다. 실제 수의 표시방법을 학습하면서 표시 가능한 값의 범위와 여러 산술연산의 특성을 이해할 수 있다. 이러한 점들에 대해서 이해하게 되면 모든 범위의 숫자들에 있어서도 정확히 동작하고 다양한 컴퓨터, 운영체제, 컴파일러 조합에서도 동일하게 동작하는 프로그램을 작성할 수 있게 된다.

2.1 정보의 저장

메모리에 저장된 각각의 비트들을 접근하는 방식 대신에 대부분의 컴퓨터들은 메모리에서 주소지정이 가능한 최소단위인 8비트 단위의 블록인 바이트를 사용한다. 기계수준의 프로그램은 메모리를 가상메모리라고 하는 거대한 바이트의 배열로 취급한다. 메모리의 각 바이트는 주소라고 하는 고유한 숫자로 식별할 수 있으며, 모든 가능한 주소들의 집합을 가상 주소공간이라고 부른다.

2.1.1 16진수 표시

우리는 비트 패턴을 16진수로 표시하고자 한다. 16진수(간단히 "hex")는 '0'에서 '9'까지의 숫자와 'A'에서 'F'까지의 문자를 사용해서 16개의 가능한 값으로 나타낸다. C언어에서 0x나 0X로 시작하는 숫자 상수들은 16진수로 해석한다. 문자 'A'에서 'F'까지는 대문자나 소문자 모두 사용할 수 있다.

십진수와 16진수 표시 간에 변환을 하기 위해서는 일반적인 경우를 처리하기 위한 곱셈과 나눗셈을 사용해야 한다. 십진수 x를 16진수로 변환하기 위해서 x를 16으로 반복해서 나누고, 몫 q와 나머지 r을 얻는다. 그러면 $x=q \cdot 16+r$ 로 표시된다. 그러고 나면 r을 나타내는 16진수 숫자릴 최소중요숫자(least significant digit)로 사용하고 q에 대해 이 과정을 반복해서 나머지 숫자들을 생성한다. 예를 들어 십진수 314,156은 16진수 0x4cB2c로 표현할 수 있다.

2.1.2 데이터의 크기

모든 컴퓨터는 워드 크기 word size를 규격으로 가지게 되는데, 이것은 포인터의 정규 크기를 표시한다. 하나의 가상주소가 이와 같은 한 개의 워드로 인코딩되기 때문에 이 워드 크기가 결정하는 가장 중요한 시스템 변수가 가상 주소공간의 최대 크기이다. 즉, $w$비트 워드 크기를 갖는 컴퓨터에서 가상주소는 0에서 $2^w - 1$ 범위를 가지며 프로그램은 최대 $2^w$ 바이트에 접근할 수 있게 된다.

C언어에서는 정수와 부동소수점 데이터를 위한 여러 가지 데이터 포맷을 지원한다. 정수 데이터는 0과 음수, 양수를 표시하기 위해서 부호형 signed 정수가 되거나 양수 값만을 나타내는 비부호형 unsigned 정수가 될 수 있다. 

2.1.3 주소지정과 바이트 순서

어떤 객체를 나타내는 바이트들을 정렬하는 데는 두 가이 일반적인 관습이 존재한다. 비트 표시 $[x_{w-1}, x_{w-2}, \dots x_1, x_0]$를 갖는 $w$-비트 정수가 있다고 하자. 여기서 $x_{w-1}$은 가장 중요한 비트 most significant bit이고, $x_0$는 가장 덜 중요한 비트이다. 객체를 메모리에 가장 덜 중요한 바이트부터 저장하는 관습을 리트 앤디안 이라고 부르고, 가장 중요한 바이트부터 저장하는 관습을 빅 엔디안이라고 부른다.

2.1.6 부울 Boolean 대수

비트 벡터를 사용하는 유용한 응용으로 유한집합의 표시를 들 수 있다. $i \in A$이면 언제나 $a_i=1$인 비트 벡터 $[a_{w-1}, \dots, a_1, a_0]$를 갖는 부분집합 $A \subseteq \{0, 1, \dots, w-1\}$을 인코딩할 수 있다. 예를 들면, 비트 벡터 $a=[01101001]$은 집합 $A=\{0, 3, 5, 6\}$을 인코딩한다.

2.1.8 C에서의 논리 연산

C에서는 논리 연산의 OR, AND, NOT에 해당하는 논리연산자 ||, &&, !을 제공한다. 이들은 흔히 비트수준 연산과 혼동될 수 있지만, 이들의 동작은 전혀 다르다. 논리 연산은 0이 아닌 인자들을 '참'으로 취급하고, 0은 '거짓'으로 처리한다. 결과가 참인지 거짓인지에 따라 1 또는 0을 리턴한다.

2.1.9 C에서의 쉬프트 연산

C는 비트 패턴을 좌우로 이동시키는 쉬프트 연산 집합을 제공한다. 비트 표시 $[x_{w-1}, x_{w-2}, \dots x_1, x_0]$를 갖는 오퍼랜드 x에 대해 C 식 x<<k는 비트 표시 $[x_{w-k-1}, x_{w-k-2}, \dots, x_0, 0, \dots 0]$을 생성한다. 즉, x는 좌측으로 k비트 이동하고, 중요한 좌측의 k비트가 밀려서 삭제되며 우측에는 k개의 0으로 채워진다. C언어에서는 이와 대응하는 우측 쉬프트 연산 x>>k가 있으며, 이것은 약간의 미묘한 동작을 가지고 있다. 일반적으로 컴퓨터는 두 종류의 우측 쉬프트를 제공한다.

1. 논리 우측 쉬프트: 좌측 끝을 k개의 0들로 채워서 $[0, \dots, 0,  x_{w-1}, x_{w-2}, \dots x_k]$를 만든다.
2. 산술 우측 쉬프트: 좌측 끝을 가장 중요한 비트를 k개 반복해서 채워서 $[x_{w-1}, \dots, x_{w-1}, x_{w-1}, x_{w-2}, \dots x_k]$를 만든다. 이 관습은 약간은 특이한 것 같지만, 이것은 부호형 정수 데이터의 연산에서 유용하게 작용한다.

C표준은 부호현 숫자의 경우에 어떤 타입의 우측 쉬프트가 사용되어야 하는지 명확히 정의하고 있지 않다. 산술 또는 논리 쉬프트 둘 다 사용 가능하다. 실제로는 대부분의 컴파일러/컴퓨터 조합들은 부호형 데이터에 대해서 산순 우측 쉬프트를 사용하고 있으며, 많은 프로그래머들도 이렇게 사용하는 것을 가정하고 있다. 비부호형 데이터에에 대해서 우측 쉬프트는 논리 쉬프트여야 한다.

2.2 정수의 표시

이 절에서는 정수를 인코드하기 위해 사용할 수 있는 두 가지 방법$-$양수만 표시할 수 있는 방법과 음수, 0, 양수 모드를 표시할 수 있는 방법$-$에 대해 설명한다.

2.2.2 비부호형의 인코딩

w비트의 정수형 데이터 타입이 있다고 하자. 전체 벡터를 나타내기 위해서 비트 벡터를 $\vec{x}$로 표시하거나 벡터의 각 비트를 표시하기 위해 $[x_{w-1}, x_{w-2}, \dots x_1, x_0]$를 사용할 수 있다. $\vec{x}$를 이진수 표시로 작성된 숫자로 생각하면 $\vec{x}$의 비부호형 해석을 할 수 있다. 이러한 해석과정을 함수 $B2U_w$(길이 $w$의 "binary에서 unsigned로"를 의미)로 나타낸다:

\begin{align*}
    &  B2U_w(\vec{x}) \overset{\cdot}{=} \Sigma^{w-1}_{i=0} x_i 2^i
    \tag{2.1}
\end{align*}

이 식에서 $ \overset{\cdot}{=} $ 부호는 좌변이 우변과 동일하게 적의된다는 것을 의미한다.

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

부호형 숫자를 컴퓨터에서 표시하는 가장 일반적인 방법은 2의 보수 형식이라고 알려져 있다. 이와 같은 해석ㄷ을 함수 $B2T_w$("이진수에서 길이 $w$의 2의 보수")와 같이 나타낸다:

\begin{align*}
    &  B2T_w(\vec{x}) \overset{\cdot}{=} -x_{w-1} 2^{w-1} \Sigma^{w-1}_{i=0} x_i 2^i
    \tag{2.3}
\end{align*}

가장 중요한 비트인 $x_{w-1}$은 부호 비트라고도 불린다. 이 비트의 "자리값(weight)"은 $-2^{w-1}$이고, 이 값은 자리값을 비부호형 표현한 것을 음수화한 것이다.

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

값은 동일하게 유지한 채 다른 길이의 위드로 정수를 변환하는 것은 일반적인 연산의 하나이다. 비부호형 수를 보다 길이가 긴 데이터 타입으로 변환하기 위해서 단순히 앞에 0들을 추가할 수 있다; 이 연산은 영의 확장 zero extension이라고 알려져 있다. 비부호형 수를 영의 확장으로 확대하는 방법은 다음과 같다. 길이 $w$의 비트 벡터 $\vec{u}= [u_{w-1}, u_{w-2}, \dots, u_1, u_0] $와 길이가 $w'$인 벡터 $\vec{u'}= [0, \dots, 0, u_{w-1}, u_{w-2}, \dots, u_1, u_0] $에 대해서 $B2U_w(\vec{u})=B2U_{w'}(\vec{u'})$ 가 성립한다. 또한 길이 $w$의 비트 벡터 $\vec{x}= [x_{w-1}, x_{w-2}, \dots, x_1, x_0] $ 와 $\vec{x'}= [ x_{w-1} , \dots, x_{w-1} , x_{w-1}, x_{w-2}, \dots, x_0] $ 인 두 개의 벡터를 정의하자. 그러면 $B2T_w(\vec{x})=B2T_{w'}(\vec{x'})$ 관계가 성립한다.

2.2.7 숫자의 절삭

비트의 개수를 줄이는 경우를 살펴보자. $w$ 비트의 수 $\vec{x}= [x_{w-1}, x_{w-2}, \dots, x_0] $ 를$k$ 비트 수로 절삭할 때 상위 $w-k$ 비트를 제거해서 비트 벡터 $\vec{x'}= [x_{k-1}, x_{k-2}, \dots, x_0] $ 를 얻는다. 수를 절삭하면 값이 바뀔 수 있다. 이것은 일종의 오버플로우와 같다.

2.3 정수의 산술연산

2.3.1 비부호형 덧셈

두 개의 비음수 $x,y, 0 \leq x,y \leq 2^w$가 있다고 하자. 이들 각각은 $w$비트 비부호형 수로 표시될 수 있다. 그러나 이들의 합을 계산하면 가능한 범위는 $0 \leq x+y \leq 2^{w-1}-2$ 를 갖는다. 이 합을 표시하기 위해서는 $w+1$개의 비트가 필요하게 된다. 일반적으로, 프로그래밍 언어들은 "덧셈"과 "곱셈" 같은 연산은 정수에 대응하는 일반적인 연산들과 다르다. 비부호형 산술연산은 나머지 연산 modular의 한 가지 형태로 볼 수 있으며, x+y의 비트수준 표현에서 자리값이 $2^{w-1}$ 보다 큰 비트들을 단순히 삭제하여 합을 $2^w$의 나머지를 구해서 계산한다. 이 값을 $+^u_w$ 로 표시한다.

2.3.4 비부호형 곱셈

범위 $0 \leq x,y \leq 2^w-1$을 갖는 정수 $x,y$는 $w$ 비트 비부호형 수로 나타낼 수 있지만, 이들의 곱 $x \cdot y$는 0과 $(2^w-1)^2= 2^{2w} - 2^{w+1} +1$사이의 범위를 가질 수 있다. 이것을 표시하려면 $2w$ 비트까지 필요할 수 있다. 대신, C에서 비부호형 곱셈은 $2w$ 비트 정수 곱의 하위 $w$ 비트로 주어지는 $w$ 비트 값을 만드는 것으로 정의된다. 이 값을  $*^u_w$로 표시한다. 즉, $0 \leq x,y \leq UMax_w$인 $x,y$에 대해서 $x *^u_w y=(x \cdot y)\mod 2^w$ 이다.

2.3.6 상수를 사용한 곱셈

역사적으로 여러 컴퓨터에서 정수 곱셈은 매우 느려서 10개 이상의 클럭 사이클이 필요하다. 그러나 덧셈, 뺄셈, 비트수준 연산, 쉬프트 연산 등은 1사이클만 필요로 한다. $x$가 비트 패턴 $[x_{w-1}, x_{w-2}, \dots, x_0]$를 갖는 비부호형 정수라고 하자. 그러면 $k \leq 0$인 모든 $k$에 대해 $x2^k$의 $w+k$ 비트 수준 표현은 $[x_{w-1}, x_{w-2}, \dots, x_0, 0, \dots, 0]$ 이며, 무측에 $k$개의 0을 추가한 것이다.

2.3.7 2의 제곱으로 나눗셈하기

대부분의 컴퓨터에서 정수 나눗셈은 정수 곱셈보다 훨씬 느리다. 약 30사이클 이상 소요된다. 2의 제곱으로 나누는 것은 오른쪽 쉬프트를 사용한다. 비트 벡터 $[x_{w-1}, x_{w-2}, \dots, x_0]$를 $k$만큼 우측 논리 쉬프트하면 다음과 같은 비트 벡터를 얻게 된다. $[0, \dots, 0, x_{w-1}, x_{w-2}, \dots, x_k]$

2.4 부동소수점

부동소수점 표현은 $V=x \times 2^y$ 형태의 소수를 인코딩한다. 이 방식은 매우 큰 수와 관련된 계산을 할 때 $(|V| \gg 0)$, 또는 0에 매우 가까운 수를 계산할 때 $(|V| \ll 0)$ 우용하며, 실수 산술연산의 근사값으로 보다 일반적으로 유용하게 사용된다.

2.4.1 비율 이진수 (Fractional Binary Numbers)

비율 이진수는 아래 수식과 같이 정의될 수 있다.

\begin{align*}
    &  b= b_m b_{m-1} \dots b_1 b_0 b_{-1} b_{-2} \dots b_{-n+1} b_{-n} = \Sigma^m_{i=-n}{2^i \times b_i}
    \tag{2.19}
\end{align*}

부호 '.'은 이제는 이진 소수점이 되고, 좌측의 비트들은 비음수의 2의 제곱을 자리값으로 가지며, 우측은 2의 음의 제곱을 자리값으로 갖는다. 식 2.19로부터 이진 소수점을 좌측으로 한 자리 이동하면 수를 2로 나누는 효과를 낸다는 것을 알 수 있다. 마찬가지로 이진 소수점을 한 자리 우측으로 이동하면 수를 2로 곱한 효과를 얻는다. 비율 이진수 표기는 $x \times 2^y$로 나타낼 수 있는 수만 표시할 수 있다. 다른 값들은 오직 근사화할 수 밖에 없다. 대신에 이진 표시를 길게 늘려서 정확도를 높이도록 근사해야 한다.

2.4.2 IEEE 부동소수점 표시

위치에 기반을 둔 표기법은 값이 큰 수를 표시할 때는 효율적이지 못하다. 그 대신, 우리는 수를 $x \times 2^y$ 형태로 나타내서 $x$와 $y$ 값으로 표시하고자 한다. IEEE 부동소수점 표준은 수를 $V=(-1)^s \times M \times 2^E$ 형태로 나타낸다:

• 부호 $s$는 숫자가 음수인지 (s=1) 앙수인지 (s=0) 를 결정한다. 여기서 0을 나타내기 위한 부호 비트는 특별하게 다룬다.
• 유효숫자 $M$은 비율 이진수로 1과 $2- \epsilon$ 사이 또는 0과 $1- \epsilon$ 사이의 값을 갖는다.
• 지수 $E$는 2의 제곱으로 자리값을 제공한다 (음수 제곱도 가능).

그림 2.32 표준 부동소수점 형식

Case1: 정규화 값 Normalized Values

이것은 가장 일반적인 경우다. 이것은 exp의 비트 패턴이 모두 0(숫자 값 0)은 아니며, 모두 1이 아니어야 한다.

Case2: 비정규화 값 Denormalized Values

지수 필드가 모두 0일 때 나타낸 수는 비정규화 형태를 갖는다. 이 경우, 지수 값은 $E=1-Bias$이고, 유효숫자는 $M=f$, 즉 암시적 선두 1이 없는 비율 필드 값이다.

Case3: 특수 값 Special Values

마지막 범주는 지수 필드가 모두 1인 경우이다. 비율 필드가 모두 0이면, 결과값은 무한대를 나타낸다.

그림 2.33 단일-정밀도 부동소수점 값들의 구분

2.4.4 근사법 Rounding

부동소수점 산술연산은 표시방법이 제한된 범위와 정밀도를 갖기 때문에 실제 연산의 근사값을 사용할 수 밖에 없다. 그래서 어떤 값 $x$에 대해 원하는 부동소수점 형식으로 표시할 수 있는 "가장 유사한" 값 $x'$를 체계적으로 계산하는 방법을 필요로 한다. 이것은 근사 rounding 연산을 의미한다.