2,147,483,647 ?
그 시절 메이플스토리를 해본 사람이라면 2,147,483,647 이라는 숫자에서 무언가 향수를 느낄지도 모른다.
백만 단위도 크게 느껴졌던 나에게, 학교에서 배운 방법으로 4자리씩 끊어가며 본 결과 저 숫자가 21억이라는 어마어마한 숫자라는 걸 알았을 때 무언가 압도되는 느낌을 받았었다. 그래서 저 숫자가 기억이 난다.
시간이 지나고 잊고 살다가, int 자료형을 배우게 되면 저 숫자가 2^31 - 1이라는걸 알게 된다.
대부분의 32bit 운영체제에서 int, long type의 자료형은 4byte, 그러니까 32개의 bit를 저장 할 수 있다. 그런데 2^32는 계산해보면
2,147,483,648이 아니다. 왜 그럴까?
그 이유를 컴퓨터가 Integer를 encoding하는 방법을 통해 알아보도록 하자.
(후술할 내용은 CS:APP 3rd edition을 참고하였습니다.)
1. Integer?
int num = 3;Integer는 수학 용어로 정수를 의미한다.
그리고 CS에서의 Integer는 유한한 범위의 정수를 표현하는 integral data type을 의미한다.
위 표에 32비트 운영체제에서 integral data type의 range가 적혀 있다.
눈 여겨 볼 점은 음수의 범위가 양수의 범위보다 1만큼 크다는 것이다.
아마 0 때문이라고 직관적으로 추측은 되지만, 왜 그런지 정확히 설명해보라고 하면 할 말이 없다.
2. Unsigned encodings
위 표를 보면 알 수 있듯이 자료형은 음수 범위를 커버하는지에 따라 signed와 unsigned로 나뉜다. 그리고 signed인지 unsigned인지에 따라 정수가 encoding되는 방식이 다르다.
unsigned의 경우 우리가 일반적으로 decimal(10진수)을 binary(2진수)로 변환하는 방법을 따른다. 이를 Unsigned encoding이라고 한다.
(B2U: Binary to Unsigned mapping)
이는 우리의 일반적인 상식과 일맥상통한다. 근데 이제 -1을 어떻게 표현하지??
3. Two's complement encodings
Two's complement form:
Interpreting the most significant bit of the word to have negative weight.
Most Significant bit, 즉 첫번째 비트는 음수로 본다는 뜻이다. 예를 들어 보자.
(B2T: Binary to Two's complement)
예시를 통해 보면 이해가 쉽다.
이제 왜 음수 범위가 양수 범위보다 1만큼 큰지 이해가 되는가?
음수의 최댓값은 [100...000]이고 양수의 최댓값은 [011...111]이다. 이는 1만큼 차이가 난다.
조금 더 생각해보면 unsigned를 non-negative로 정의하면서 0과 양수가 하나의 집합으로 묶이게 되었다. 그래서 0 + 양수의 집합과 음수의 집합은 크기가 같다.
non-positive를 unsigned로 정의한다면 양상은 반대가 될 것이다.
왜 two's complement라고 불릴까?
예를 들어 -5를 표현할 때 [1011] = -8 + 0 + 2 + 1로 계산이 된다.
즉 -2^3에 더하는 방식이기 때문에 two's complement라고 부른다.
4. 그 외의 Encoding 방법들
반면 one's complement는 0이 [11...11]로 표현되고,
-x = [11...11] - x로 구해지기 때문에 one's complement라고 불린다.
