CSAPP 2.3 ~ 2.4 장 정리

CSAPP 2.3장 정수 연산 (Integer Arithmetic)

어제에 이어서 2.3장~ 2.4장을 TIL겸 정리해봤다. 2.3장에서는 컴퓨터가 정수를 사용하여 덧셈, 곱셈, 나눗셈과 같은 연산을 수행하는 방식을 다룬다. 컴퓨터의 연산은 유한한 비트 수 때문에 실제 정수 연산과 다른 특징을 보이며, 특히 **오버플로우(overflow)**가 발생할 수 있다는 점을 이해하는 것이 중요하다.

1. 덧셈: 하나의 연산, 두 개의 해석

부호 없는 덧셈 (Unsigned Addition)

부호 없는 덧셈의 결과가 w비트로 표현할 수 있는 최대값을 초과하면 오버플로우가 발생한다. 컴퓨터는 이 결과를 단순히 버리지 않고, 모듈러(modular) 연산을 수행한다. 즉, 덧셈 결과는 (x + y) mod 2^w 와 같다. 예를 들어 4비트 환경에서 9(1001) + 12(1100)의 실제 결과는 21이지만, 컴퓨터는 21 mod 16인 5(0101)를 결과로 내놓는다. 오버플로우 여부는 덧셈 결과 s가 피연산자 x나 y보다 작아지는지로 간단히 탐지할 수 있다 (s < x).

2의 보수 덧셈 (Two's-Complement Addition)

2의 보수 덧셈의 가장 중요한 특징은 비트 수준에서는 부호 없는 덧셈과 완전히 동일하게 동작한다는 점이다. 이는 CPU가 부호 있는 수와 없는 수를 구분하지 않고 단 하나의 덧셈기 하드웨어를 사용할 수 있게 하므로 매우 효율적이다.

다만 오버플로우를 해석하는 방식은 다르다.

양수 오버플로우: 두 양수를 더했는데 결과가 음수가 되는 경우이다.
음수 오버플로우: 두 음수를 더했는데 결과가 양수가 되는 경우이다.
피연산자 x, y의 부호가 같은데 결과 s의 부호가 다른 경우로 탐지할 수 있다.

2. 곱셈: 하위 비트는 동일하다

정수 곱셈 역시 결과가 워드 크기를 초과할 수 있으며, 이 경우 상위 비트는 버려지고 하위 w비트만 결과로 저장된다. 덧셈과 마찬가지로, 부호 없는 곱셈과 2의 보수 곱셈은 비트 수준에서 동일한 결과(하위 w비트)를 가진다. 이는 곱셈 하드웨어의 설계를 단순화하는 데 기여한다.

3. 상수에 의한 곱셈과 나눗셈: 컴파일러의 최적화

현대 프로세서에서 곱셈과 나눗셈은 덧셈이나 비트 연산보다 훨씬 느리다. 따라서 컴파일러는 상수를 곱하거나 나누는 연산을 속도가 빠른 이동(shift) 연산과 덧셈/뺄셈의 조합으로 변환하는 최적화를 수행한다.

상수에 의한 곱셈

상수와의 곱셈을 2의 거듭제곱의 합 또는 차로 분해하여 이동과 덧셈/뺄셈 연산으로 바꾼다.

예를 들어 x * 14는 x * (16 - 2) 또는 x * (8 + 4 + 2)로 계산할 수 있다.
x * (8 + 4 + 2)는 (x << 3) + (x << 2) + (x << 1)로 변환되어 훨씬 빠르게 실행된다.

2의 거듭제곱으로 나누기

2의 거듭제곱으로 나누는 연산은 오른쪽 이동(right shift) 연산으로 최적화된다. 이때 부호에 따라 이동 방식이 다르다.

부호 없는 수: 빈자리를 0으로 채우는 논리적 오른쪽 이동을 사용한다.
2의 보수 수: 부호 비트를 보존하기 위해 빈자리를 최상위 비트로 채우는 산술적 오른쪽 이동을 사용한다. 특히 음수를 나눌 때는 올바른 버림(round-down)을 위해 나누기 전에 **편향(biasing)**을 더해주는 추가적인 처리가 필요하다.

CSAPP 2.4장 부동소수점 (Floating Point)

2.4장에서는 실수를 컴퓨터에서 표현하는 표준 방식인 **IEEE 부동소수점(Floating-Point)**에 대해 다룬다. 정수 표현과 달리, 부동소수점은 매우 큰 수나 0에 매우 가까운 수를 표현할 수 있지만, 정밀도에 한계가 있어 근사치를 사용한다.

1. 분수 이진수 (Fractional Binary Numbers)

부동소수점을 이해하려면 먼저 2진 소수 표현법을 알아야 한다. 10진 소수점과 마찬가지로 **2진 소수점(binary point)**을 사용하여 소수를 표현한다.

2진 소수점 오른쪽의 각 자리는 2⁻¹(1/2), 2⁻²(1/4), 2⁻³(1/8) ... 와 같이 음의 거듭제곱 가중치를 가진다.
예를 들어, 101.11₂은 4 + 0 + 1 + 1/2 + 1/4 이므로 10진수로 5.75 이다.
하지만 1/3이나 1/5과 같은 수는 2진 소수로 정확하게 표현할 수 없어 근사치로만 나타낼 수 있다. 이로 인해 작은 오차가 발생할 수 있다.

2. IEEE 부동소수점 표현 (IEEE Floating-Point Representation)

IEEE 754 표준은 실수를 V = (-1)ˢ × M × 2ᴱ 형태로 표현한다. 이 값을 비트 수준에서 저장하기 위해 세 부분으로 나눈다.

부호 (Sign, s): 1비트를 사용하여 양수(0)와 음수(1)를 결정한다.
지수 (Exponent, E): k비트의 지수 필드는 2의 거듭제곱 값을 결정하여 수의 범위를 나타낸다. **편향(bias)**된 형태로 저장되어 음수 지수를 효율적으로 표현한다. 실제 지수값은 E = e - Bias로 계산된다.
가수 (Mantissa 또는 Fraction, M): n비트의 분수 필드는 수의 정밀도를 나타낸다.

이 세 필드의 값에 따라 숫자는 다음 세 가지 경우로 나뉜다.

정규화된 값 (Normalized): 가장 일반적인 경우로, 지수 필드가 모두 0이거나 모두 1이 아닐 때이다. 이때 가수 M은 1 + f (f는 분수 필드 값)로 계산된다. 맨 앞의 1을 생략하고 저장하는 "암시적 선행 1(implicit leading 1)" 기법을 통해 1비트의 추가적인 정밀도를 얻는다.
비정규화된 값 (Denormalized): 지수 필드가 모두 0일 때 사용되며, 0에 매우 가까운 수를 표현하기 위해 사용된다. 정규화 방식으로는 표현할 수 없는 0 근처의 값들을 표현함으로써, 값이 갑자기 0이 되어버리는 **점진적 언더플로우(gradual underflow)**를 가능하게 한다. 이 경우 가수 M은 f와 같다.
특수 값 (Special Values): 지수 필드가 모두 1일 때 사용된다.
- 분수 필드가 0이면 **무한대(infinity)**를 나타낸다.
- 분수 필드가 0이 아니면 **NaN(Not a Number)**을 나타낸다. (예: √-1 또는 0/0 연산의 결과)

3. 반올림 (Rounding)

부동소수점은 실수를 근사적으로 표현하므로, 표현 가능한 가장 가까운 값으로 반올림하는 과정이 필요하다. IEEE 표준은 네 가지 반올림 모드를 정의하며, 기본 모드는 **짝수 반올림(Round-to-even 또는 Round-to-nearest-even)**이다.

왜 짝수 반올림을 사용하는가?

1.5나 2.5와 같이 정확히 두 표현 가능한 값의 중간에 있는 값을 반올림할 때, 항상 올리거나 내리면 특정 방향으로 통계적 편향이 발생할 수 있다. 짝수 반올림은 이러한 값을 반올림할 때 결과의 최하위 비트를 짝수(0)로 만드는 방향으로 반올림한다. 예를 들어 1.5는 2로, 2.5도 2로 반올림된다. 이 방식은 장기적으로 양수와 음수 방향의 반올림 오차를 상쇄시켜 통계적 편향을 최소화하는 장점이 있다.

4. 부동소수점 연산의 특징

부동소수점 연산은 일반적인 실수 연산과 다른 수학적 속성을 가진다. 가장 중요한 특징은 결합법칙이 성립하지 않는다는 점이다.

예를 들어, (3.14 + 1e20) - 1e20은 0.0이 될 수 있다. 3.14가 1e20에 비해 너무 작아 덧셈 과정에서 정밀도 한계로 인해 무시되기 때문이다.
하지만 3.14 + (1e20 - 1e20)은 3.14가 된다.
이러한 특성 때문에 컴파일러는 부동소수점 연산의 순서를 함부로 바꾸는 최적화를 수행하지 않으며, 프로그래머는 연산 순서에 주의해야 한다.