CSAPP(2) - Representing and Manipulating Information

업데이트: September 14, 2023

1. Information Storage

대부분의 컴퓨터는 메모리 각 비트에 접근하는 대신 8bit(1bytes) 블럭을 사용한다.

1.1. Hexadecimal Notation

이진수 표기법은 장황하고 십진수 표기법은 변환이 지루하다.
그래서 16진수 표기법을 자주 쓴다. 진수 변환할 줄 알아야 한다.

1.2. Data Sizes

워드 크기란 포인터 데이터의 크기를 말한다.
가상 주소의 최대 크기는 워드 크기에 의해 결정된다.
- $w$ bit 워드 크기의 가상 주소 범위는 0부터 $2^w-1$ 까지다.
- 32비트는 주소 공간이 최대 4GB($2^{32}$bytes)이다.
- 64비트 워드 크기는 최대 16 exabyte 이다.
대부분의 64비트 머신은 하위 호환성을 위해 32bit 프로그램을 구동할 수 있다.
- 32/64 비트 프로그램은 어디서 구동되느냐가 아닌 어떻게 프로그램이 컴파일되었는가 로 구분한다.

1.3. Addressing and Byte Ordering

데이터를 메모리에 저장할 때

리틀 엔디언 : 최하위 바이트가 먼저
- 대부분 인텔 CPU 머신
빅 엔디언 : 최상위 바이트가 먼저
최근의 칩들은 bi-endian이다. 리틀, 빅 둘 다 가능하다.
- 실제로 바이트 순서는 특정 OS가 고정해서 쓴다.
- ex) ARM은 bi-endian인데, Andiroid와 IOS는 리틀 엔디언 모드에서만 동작한다.

일반적으로 응용 프로그래머들은 바이트 순서를 고려할필요는 없으나 다음과 같은 경우 찾아볼 수 있다.

이진 데이터를 바이트 순서가 다른 머신 간에 네트워크 통신할때 문제가 발생한다. 네트워크 표준에 맞게 변환해서 전송한다.
머신 레벨의 프로그램에서 disassemble 해보면 특정 정수값을 리틀 엔디언으로 저장하는 어셈블리 명령을 볼 수 있다.
응용 프로그램에서 객체의 바이트 표현을 출력할 때

1.4. Representing Strings

C에서 문자열은 ASCII코드로 표현되는 바이트 배열이다. 결과적으로 텍스트 데이터는 바이너리 데이터보다 플랫폼 독립적이다.

1.5 Representing Code

특정 소스 코드를 기계 코드로 컴파일하면 바이트 표현이 된다.

머신마다 다르게 명령하고 코드를 인코딩한다.
- 같은 머신이라도 os별로 다르다. 머신/os간 호환되지 않는다.
기계 관점에서 플그램은 일련의 바이트일 뿐. 원래 소스에 대한 정보가 없다.(디버깅을 위해 일부 존재함)

1.6 Introduction to Boolean Algebra

불 대수 연산 소개들..

2. Integer Representations

2.3. Two’s Complement Encodings

C와 다르게 자바 표준의 정수형 데이터 타입의 범위와 표현은 꽤 구체적이다.

일반적인 C의 64bit 2의 보수 표현이다. 근데 이제 unsigned가 없는.
단일 바이트 데이터 타입은 char가 아닌 byte
- java에서 char는 2바이트
실행되는 os나 머신에 관계없이 동일하게 동장하도록 의도되었다.

3. Integer Arithmetic

두 양의 정수를 더하는 것이 음의 결과가 될 수도 있으며, x < y 는 x-y < 0 과 다른 결과가 될 수 있다. 이는 컴퓨터 산술의 제한된 환경 때문이다.

아래와 같은 방식으로 정수의 산술 연산이 수행된다. 자세한 내용은 책 참고

3.1. Unsigned Addition

덧셈의 결과가 워드 크기보다 커지면($2^w-1$ 초과) 오버플로가 발생한다.

3.2. Two’s Complement Addition

2의 보수의 범위는 $-2^{w-1} \le x \le 2^{w-1}-1$ 로, 양의 오버플로와 음의 오버플로 둘 다 발생할 수 있다. 자세한 내용은 책 참고

3.3. Two’s Complement Negation

3.4. Unsigned Multiplication

3.5. Two’s Complement Multiplication

3.6. Multiplying by Constants

왼쪽 쉬프트 연산을 활용한다.

3.7. Dividing by Powers of 2

오른쪽 쉬프트 연산을 활용한다.

3.8. Final Thoughts on Integer Arithmetic

4. Floating Point

부동소수점은 $V = x * 2^y$ 형태로 표현된다.
1985년 IEEE754 표준이 제정되어 이기종간 이식성을 크게 증가시켰다.

4.1. Fractical Binary Numbers

$b_{m}b_{m-1}b_{1}b_{0}.b_{-1}…b_{-n}$

4.2. IEEE Floating Point Representation

위에서 본 위치 표기법은 매우 큰 수를 표기하기에 효율적이지 못하다.

IEEE 부동소수점 표준은 $V = (-1)^s * M * 2^E$ 로 표현한다.

s는 부호를 결정
유효숫자 $M$은 분수 이진수로 1과 2-e 사이거나 0과 1-e 사이다.
$E$는 지수이다
float는 32비트 표현 : 부호 1비트, 지수 8비트, 유효숫자 23비트
double은 64비트 표현 : 부호 1비트, 지수 11비트, 유효숫자 52비트

이러한 비트 표현은 지수에 따라 3개의 케이스로 나뉜다.

정규화된 값
- 가장 일반적인 케이스.
- 지수 비트가 전부 0이거나 1이 아닌 경우.
- 지수 필드는 부호있는 정수로 표현된다.
  - 32비트에서는 -126부터 +127까지, 64비트에서는 -1022부터 +1023까지이다.
- 유효숫자 필드는 이진 표현으로
  - $1.각비트$의 의미를 가진다.
비정규화된 값
- 지수 필드가 모두 0인 경우
- 유효숫자 필드는 $0.각비트$
- 두 가지 목적으로 쓰인다.
  - 숫자값 0의 표현 (정규화 값은 항상 1보다 크기 떄문)
  - 0.0에 매우 가까운 수를 표현(점진적 언더플로)
특별한 값
- 지수 필드가 모두 1인 경우
- 유효숫자 필드가 모두 0이면 무한대를 표현.
  - 무한대는 오버플로를 표현할 수 있다. 매우 큰 수의 곱이나 0으로의 나누기를 표현할 수 있다.
- 유효숫자 필드가 0이 아니면 $NaN$
  - 실수나 무한대로 표현될 수 없는 경우. ex)루트-1, $\infty - \infty$
  - 초기화되지 않은 데이터를 표현할 때도 유용

4.3. Example Numbers

4.4. Rounding

부동소수점 산술은 실수 산술에 근사할 수 밖에 없다. 때문에 가장 가까운 값을 표현하는 일반적인 방법을 찾아야 한다. 반올림 연산을 해야 한다.

IEEE 부동소수점 표기법은 4개의 반올림 모드를 정의한다. 디폴트는 가장 가까운 매치이고, 나머지 세개는 상한과 하한을 계산하는 데 쓰인다.

Round-to-even : 가장 가까운 매치. 딱 가운데인 경우 짝수로 반올림.
- 딱 절반인 경우에 항상 올림하거나 내림하면 전체 집합의 평균이 높거나 낮기 때문에 변향을 막기 위해 짝수로 정했다고.
Round-toward-zero : 양수는 내림, 음수는 올림
Round-down : 양수과 음수를 내림
Round-up : 양수와 음수를 올림

4.5. Floating-Point Operations

실수 x+y 는 Round(x+y)

오버플로 시 inf
교환법칙 가능, 결합법칙 불가능. (반올림 떄문!)
역과의 덧셈 시 0이다.
- 예외 : $NaN + x = NaN$, $+\infty - \infty = NaN$
곱셉 또한 결합법칙 불가능. 곱셈 분배법칙 또한 불가능!

4.6. Floating Point in C

float과 double 두 타입을 제공한다. IEEE 부동소수점을 지원하는 머신에서는 single, double 정밀도 부동소수점에 대웅한다. 또한 round-to-even 반올림 모드를 사용한다.

다만 C표준은 머신이 IEEE표준을 사용하기를 요구하지 않아서 반올림 모드를 변경하거나 NaN같은 특별한 값을 얻을 표준이 없다. 라이브러리를 통해 제공받아야 한다.

5. Summary

대부분의 머신은 부호있는 수를 2의 보수 표현법으로 인코딩한다.
대부분의 C구현은 singed와 unsinged를 캐스팅할때 비트 패턴으로 바꾸지 않는다. 이 때문에 많은 버그가 생긴다.
부동 소수점은 0.0에 너무 가까울 때 0이 되는 언더플로가 발생할 수 있다.
정수 산술은 오버플로로 인해 x*x가 음수가 될 수도 있다.
정수 산술은 교환법칙, 결합법칙, 분배법칙을 만족한다. 따라서 여러 최적화가 가능
- 실수는 결합,분배법칙을 만족하지 않으므로 관련 최적화 불가
Floating-point arithmetic must be used very carefully, because it has only limited range and precision, and because it does not obey common mathematical properties such as associativity.

출처

https://csapp.cs.cmu.edu/
책 “Computer Systems : A Programmer’s Perspective”

남궁찬