시스템 프로그래밍 노트 1 - 기본 표현 단위와 정수 표현

1. 기본 표현 단위

모든 정보의 최소 표현 단위는 비트이다.

• bit : 0,1
• byte: 여덟 개의 bit를 묶어서 부른다. 이진수로는 00000000 ~ 11111111, 십진수로는 0 ~ 255, 십육진수로는 00 ~ ff로 표현된다.

1.1. 비트 연산자

• &, |, ~, ^
  • C에서 사용하는 &&, ||, !는 논리 연산자로, 0을 거짓, 나머지를 모두 참으로 대응한다는 점에서 큰 차이가 있다.
• <<, >>. >>의 경우 왼쪽을 0으로 채운다. 반면 논리 연산자에서는 왼쪽을 가장 중요한 비트most siginificant bit로 채운다.

2. 정수

크게 unsigned와 Two’s Complement로 구분할 수 있다.

2.1. unsigned

• 언제나 0보다 크거나 같은 수들을 뜻한다.

• 단순히 이진수 표현을 한다.

$B2U(X) = \sum _{i=0} ^{w-1} x_i \cdot 2^i$

• 0부터 $2^w -1$

2.2. Two’s Complement

• 가장 왼쪽에 있는 비트가 부호 비트로, 0이면 양수, 1이면 음수를 뜻한다.

$B2T(X) = -x_{w-1} \cdot 2^{w-1} + \sum _{i=0} ^{w-2} x_i \cdot 2^i$

• $-2^{w-1}$부터 $2^{w-1} -1$

• -1을 표현하면 111...11이다.

2.3. 변환

• c에서 (int), (signed int) 변환casting을 말하는 것이다.

• Two’s Complement 기준 양수 영역은 그대로

• Two’s Complement 기준 음수 영역은 unsigned의 큰 양수 영역으로 그대로 옮겨진다.

• $ U2T = B2T \circ U2B, $T2U = B2U \circ T2B. 어려울 건 없고 그냥 같은 비트 표현을 공유한다고 생각하면 된다.

• 실제 언어에서는 암시된 변환implicit casting을 허용한다.

int tx, ty;
unsigned ux, uy;
tx = ux; // same as tx = (int) ux;
uy = ty; // same as uy = (unsigned) ty;

• 두 가지 표현이 섞여있으면 암시적으로 int를 unsigned로 변환한다.

2.4. 확장/축소

• 확장의 경우, signed일 때 부호 비트를 앞에다가 붙인다. 확장을 하는 상황은 다음과 같다:

short int x = -15213; // 0xc493
int ix = (int) x;     // 0xffffc493

• 축소는 그 수가 양쪽 영역에 모두 포함되어 있으면 확장의 역변환이다. 그렇지 않다면, 예를 들어 int를 short로 바꾸는 경우에 mod 0x10000한다.

2.5. 덧셈

• $UAdd_w (u,v) = u+v \mod 2^w $
• $TAdd_w$는 $UAdd_w$와 비트 단위에서 동일하다.
  • 즉, $TAdd_w (u,v) = U2T(UAdd_w (T2U(u), T2U(v)))$

2.6. 곱셈

• $ UMult_w (u,v) = uv \mod 2^w $
• $TMult_w$는 $UMult_w$와 비트 단위에서 동일하다. (증명 가능)
  • 즉, $TMult_w (u,v) = U2T_w (UMult_w (T2U (u), T2U(v))) $

2.7. Bitwise Shift

2.7.1. Left Shift

• u << k는 $u \times 2^k$와 동일하다.
• 앞에다가 0을 k개 붙인 후 나머지 비트는 버린다.

2.7.2. Right Shift

• unsigned는 앞에 k개의 0비트를 넣으면서 오른쪽으로 밀어버린다.
  • 반올림 그런거 없고 그냥 버린다. 수학적으로는 $\lfloor x / 2^k \rfloor$.
• signed는 앞에 k개의 부호 비트를 넣으면서 오른쪽으로 밀어버린다.
  • x가 0보다 크거나 같을 때는 똑같이 버린다.
  • x가 음수이면 \lfloor (x+2^k -1) / 2^k \rfloor $의 형태로 계산한다. 이는 어림 하는 방향을 0으로 맞추기 위함이다. $x가 $2^k$의 배수이면 상관이 없지만, 그렇지 않으면 1이 더해져서 올림이 된다. 궁극적으로 $\lceil x / 2^k \rceil$을 비트 레벨에서 구현한 것과 같다.

3. Byte Ordering

• 메모리를 처리하는 단위를 word라고 하고, 32비트 아키텍쳐는 4바이트, 64비트는 8바이트이다.
• 각 주소에는 바이트가 할당된다. 즉, 그 주소들을 묶어서 처리하는 것.
• 각 C 데이터 타입에 따른 크기는 다음과 같다:

• 여러 바이트로 이루어진 단어를 어떻게 메모리에 저장할까? 그 방법에는 두 가지가 있다. 예를 들어 0xdeadbeef를 각 방법에 맞춰 넣는다고 하면

  • Big Endian : LSB가 가장 높은 추소, deadbeef. Sun, PPC Mac, Internet에서 이용한다.
  • Little Endian : LSB가 가장 낮은 주소, efbeadde. x86, Android, iOS, WIndows의 ARM 프로세서에서 이용한다.

  단, 문자열에 대해서는 조심해야 하는게, char의 배열로 취급된다. 그러니까 ‘abcd’를 넣는다면 각 a, b, c, d에 해당하는 아스키코드가 순서대로 저장된다. 마지막 바이트는 널바이트0x00.