CS:APP Ch02. Representing and Manipulating Information - 2

2.2 Integer Representations

정수를 인코딩하는 두가지 다른  방법이 있다.

하나는 부호가 없는 수, 다른 하나는 음수, 0, 양수를 표현하는 것이다.

정수 데이터를 인코딩하고 연산하는 방법

위의 표는 어떻게 컴퓨터가 정수를 인코딩하고 연산하는 지에 대한 수학적 용어이다.

 

2.2.1 Integral Data Types

C는 다양한 정수형 데이터 타입을 지원하며 유한한 범위의 정수를 표현한다.

다른 사이즈에 맞게 할당되는 바이트 수는 프로그램이 32비트나 64비트로 컴파일 되는지에 따라 다르게 한다.

고정 사이즈 데이터 타입을 제외하고는, 양수와 음수에 대한 대칭 범위를 요구한다.

 

2.2.2 Unsigned Encoding

w 비트의 정수형 데이터 타입이 있다. 이진법으로 표현할 때 각 비트의 부호가 없다는 것을 포함한다. 각 비트는 0또는 1의 값을 가진다.

각 비트는 2^i의 수학적 값을 가진다. 이러한 해석을 B2U 함수라고 부른다.

 

부호 없는 이진 표현법은 0부터 2^w - 1 사이의 모든 숫자가 유일한 인코딩을 가지고 있는 중요한 특성이 있다.

B2U 함수의 반대되는 함수는 U2B이다.

 

2.2.3 Two-Complement Encodings

부호 있는 수의 표현 방법은 2의 보수(Two-Complement) 형태로 표현된다.

이러한 함수를 B2T라고 부른다.

최상위 비트는 부호 비트라고 부르며 이것은 -2^(w - 1)의 값을 갖는다.

부호 비트가 1이면 음수이고, 0이면 음수가 아니다.

B2T의 반대되는 함수는 T2B이다.

 

2.2.4 Conversions between Signed and Unsigned - 다시

C는 숫자 데이터 타입 간의 캐스팅을 허용해준다.

음수 값을 부호 없는 수로 변환하면 0이라는 결과를 만든다.

 

2.2.5 Signed versus Unsigned in C

C는 정수형 데이터 타입에 대해 부호 있는/없는 산술을 동시에 지원한다.

C는 부호 없고와 부호 있는 것의 변환을 허용한다.

 

2.2.6 Expanding the Bit Representation of a Number

2.2.7 Truncating Numbers

2.2.8 Advice on Signed versus Unsigned

 

2.3 Integer Arithmetic

많은 시작하는 프로그래머들이 두 양수의 합이 음수 결과를 낳으면 놀란다.

또한, x < y가 x - y < 0와 다르다는 것에도 놀란다.

 

컴퓨터 산술의 뉘앙스를 이해하는 것은 프로그래머들이 더 신뢰 있는 코드를 작성하게 해준다.

 

2.3.1 Unsigned Addition

두 음수가 아닌 정수 x, y가 있다. 각 값은 w 비트로 표현된다. 0<= x, y <= 2^w

두 정수의 합의 범위는 0<= x + y <= 2^(w + 1) - 2 이며 w + 1 비트를 요구할 수 도 있다.

합이 w + 1 비트이지만 다른 값을 더하면 w + 2 비트가 될 수도 있다.

워드 크기 인플레이션(word size inflation)은산술 결과를 완벽하게 표현하기 위한 워드 크기의 범위에 위치시킬 수 없다는 뜻이다.

 

정수 결과가 자료형의 워드 사이즈에 맞게 안된다면 산술 연산의 결과가 오버플로우(overflow) 됐다고 말한다.

 

2.3.2 Two Complement's Addition

2의 보수 합에서, 결과가 너무 크거나 너무 작을 때 어떻게 해야할 지 결정해야 한다.

-2^(w - 1) <= x, y <= 2^(w - 1) - 1이고 그들의 합의 범위는 -2^w <= x + y <= 2^w - 2이다.

 

정수와 2의 보수 합의 관계

x + y 가 Case 4를 초과하면 양의 오버플로우(positive overflow)이고, Case 1보다 작으면 음의 오버플로우(negative overflow)이다.

양의 오버플로우이면 합에서 2^w를 빼주고, 음의 오버플로우이면 2^w를 더해주는 것이다.

 

두 수의 w-비트 2의 보수 합은 정확히 같은 비트 수준의 표현 방법을 가지고 있다.

대부분의 컴퓨터는 부호가 있는 그리고 없는 합 연산에 대해 같은 기계 명령어를 사용한다

 

2.3.3 Two's-Complement Negation

 

2.3.4 Unsigned Multiplication

0 <= x, y <= 2^w - 1 범위인 x * y는 0부터 (2^w - 1)^2의 범위를 갖는다.

이는 2w의 비트가 필요할 수 있다.

C에서 부호 없는 곱셉은 2w 비트의 낮은 순서의 w 비트를 사용한 w 비트로 정의된다.

 

2.3.5 Two's-Complement Multiplication

 

2.3.6 Multiplying by Constants

많은 기계에서 정수 곱셈 명령어는 꽤 느렸으며, 10이상의 클럭 사이클을 요구했다.

반대로, 덧셈, 뺄셈, 비트 수준의 연산, 시프트와 같은 연산은 1 클럭 사이클만을 요구한다.

 

컴파일에 의해 사용된 중요한 최적화는 상수에 의한 곱셉을 시프트와 덧셈 연산 조합으로 바꾸는 것이다.

예를 들어, 11을 4비트로 표현하면 1011이다. 2만큼 왼쪽으로 시프트하면 101100으로 44가 된다.

왼쪽으로 값을 시프트하는 것은 2의 거듭 제곱으로 부호 없는 곱셈을 하는 것과 같다.

 

2.3.7 Dividing by Powers of 2 - 다시

정수 나눗셈은 정수 곱셈보다도 더 느리다. 30이상의 클럭 사이클을 요구한다.

정수 나눗셈은 오른쪽 시프트 연산을 사용한다. 정수 나눗셈은 항상 0으로 반올림한다.

 

x >= 0, y > 0 일 때, 정수 나눗셈은 ⌊x / y⌋ 이고, x < 0, y > 0 일 때, 정수 나눗셈은 ⌈x / y⌉ 이다.

 

2.3.8 Final Thoughts on Integer Arithmetic

컴퓨터가 수행하는 정수 산술은 실제로 모듈식 산술의 형태이다.

유한한 워드 크기는 가능한 값의 유한한 범위를 제한하고 결과가 오버플로우될 수도 있다.

 

2의 보수 표현은 음수와 양수 값을 동시에 표현하는 데 괜찮은 방법이다.

C 언어에서 어떤 관습들은 뜻밖의 결과를 보여주는데, 이해하고 인지하기 힘든 버그의 원인이 될 수 있다.