우리 모두 컴퓨터는 0과 1밖에 알아들을 수 없다는걸 들었을 것이다.
근데 왜 하필 0과 1일까? 2진법 대신 우리에게 친숙한 10진법을 사용하면 안되는 걸까?
실제로 1946년에 개발된 에니악은 10진법으로 숫자를 표현했다. 하지만 곧 과학자들은 2진법이 훨씬 효율적이라는걸 깨달았다. 전기적으로 구현하기 쉽기 때문이다.
아래와 같이 0.0V에서 0.2V의 전기가 흐르면 0으로, 0.9V에서 1.1V가 흐르면 1로 받아들이도록 한다.
이렇게 하면 전선에 잡음이 있더라도 안전하게 정보를 오염없이 전달할 수 있다. 같은 방식을 10진법으로 하려면 고려해야할게 훨씬 많을 것이고 정보의 오염도 더 빈번할 것이다. 이와 같은 이유로 컴퓨터는 2진법을 쓰게 되었다.
1. 2의 보수
2진법으로는 숫자를 
처럼 0과 1만을 이용해 2의 거듭제곱의 합으로 표시한다. 예를 들어 5는 2^2 + 2^0 이니 101로 표시한다.
다만 이렇게 1과 0을 계속 적는것은 비효율적이니 보통 16진법을 사용해 적게 된다. 0에서 9와 A에서 F까지의 알파벳을 써서 0에서 15까지의 숫자를 나타낸다. 다음은 같은 수를 16진법, 10진법, 2진법으로 보기 좋게 정리한 표이다.
이진법은 부울 대수와 밀접한 연관이 있다. AND, OR, NOT, XOR 등 우리가 아는 논리연산자들이 부울 대수에 나오는 연산자들이다. 참고로 이 부울 대수와 컴퓨터의 연관성을 밝혀낸 논문이 클로드 섀넌의 석사 논문으로, 이 논문은 세상에서 가장 영향력있는 석사 논문으로 알려져 있다.
C에서도 &, |, ~, ^ 연산자가 존재하고 숫자 타입에도 적용할 수 있다. 숫자를 비트의 벡터로 생각해서 연산을 하는 것이다. 예를 들어
이다.
C에는 시프트 연산자 (<<, >>)도 존재한다. x << y는 비트벡터 x를 y 자리수 만큼 왼쪽으로 이동한다. 예를 들어
이다.
x >> y는 x를 y자리수 만큼 오른쪽으로 논리 시프트한다(오른쪽 시프트에는 논리와 산술 두 종류가 있다). 논리 시프트를 할때는 왼쪽에 들어오는 새 비트는 0이 되고, 산술 시프트를 할때는 최상위 비트(가장 왼쪽의 비트)를 복사한다.
예를 들어 x = 10100010이면 논리 시프트를 할때
이지만 산술 시프트를 할때는 1이 복사되어
이 된다. 왜 이렇게 시프트가 두가지인지 곧 설명하겠다.
또 y가 음수이거나 word size보다 크거나 같다면 undefined behavior가 된다.
2진법으로 어떻게 정수를 표현할까? 0과 양수를 표현하고 싶다면 간단하다. 그냥 아까 말했듯이 각 자리에 해당하는 2의 거듭제곱을 더하기만 하면 된다.
하지만 음수까지 표현하고 싶다면 2의 보수라는 방법을 써야 한다. 2의 보수에서는 최상위 비트를 부호비트로 지정하고 원래의 값을 음수로 정한다. 예를 들어 8비트 숫자라면 부호비트는 -128의 값을 갖는다.
이제 각 자리에 해당하는 2의 거듭제곱을 더하기만 하면 그 수가 나타내는 10진법 정수를 알 수 있다.
예를 들어 1011 이 2의 보수로 되어있다면 -8 + 2 + 1 = -5를 나타낸다.
이런식으로 나타내면 unsigned int는
에서
까지 나타낼 수 있고, (unsigned가 나타낼 수 있는 가장 작은 값을 UMin, 큰 값을 UMax라고 부를 것이다.)
int는
에서
까지 나타낼 수 있다. (비슷하게 signed가 나타낼 수 있는 가장 작은 값을 TMin, 큰 값을 TMax라고 부를 것이다. two's complement(2의 보수)에서 따와서 T를 쓴다.)
w는 앞으로 word size(int의 비트 수)를 나타내기 위해 쓸것이다.
2의 보수를 써서 -1을 8비트 int로 나타내면 11111111 이 된다. 실제로 계산해보면
로 -1이 된다.
다음 표를 보면 16비트 정수는 -32,768부터 32,767까지의 수를 나타낼 수 있다.
일반적으
임을 알 수 있다. 양수가 음수보다 하나 적은 이유는, 부호비트가 1이면 음수인데 반해, 부호비트가 0이면 0 또는 양수라서 그런것이다.
양수가 음수보다 하나 적다 라는 사실은 여러곳에서 비직관적인 결과를 낳는다. abs함수를 다음과 같이 구현한다고 치자.
여기에는 한가지 특별한 점이 있다. abs(TMin)은 뭘까? 아까 
이라고 했는데 TMax=011…1이고 1을 더하면 100…0=TMin이므로 abs(TMin)=TMin이 된다.
이말은 즉슨 코드에 abs가 있으면 오류가 없는지 입력값으로 TMin을 항상 테스트해봐야 한다는 것이다.
C에선 숫자 타입은 형변환이 자동으로 일어나서, 주의해야할 점이 몇가지 더 있다. 만약 unsigned int가 int로 바뀌면 어떻게 될까? 부호 비트(최상위 비트)가 0이면 아무런 변화도 없다.
하지만 부호 비트가 1이라면
를 나타내던 비트가 
를 나타내게 되어 수에서 
를 뺀것과 같은 값이 된다 (w는 int의 비트 수이다).
예를 들어 1011은 unsigned int이라면 8 + 2 + 1 = 11인데, 2의 보수라면 -8 + 2 + 1 = -5이다. 이렇게 2^4를 뺀것과 같은 값이 나온다. int가 unsigned int로 바뀔때는 똑같이 부호비트가 1이라면 
를 더한것과 같은 효과가 있다.
0에서 TMax까지의 수(초록색으로 표시된 부분)는 부호비트가 0이니 형변환이 되도 그대로지만, 그렇지 않은 수(붉은색으로 표시된 부분)는 만큼 차이가 나게 된다. 암묵적인 형변환이 되었는데 숫자가 달라져 버리는 것이다. 참고로 32비트 int에서 는 약 43억이다.
C 형변환의 이상한 점은 아직 끝나지 않았다. 어떤 표현식의 (≥, >, ==, ≤, < 포함) 모든 숫자가 signed라면 형변환이 일어나지 않지만, 여러 unsigned와 signed 숫자가 섞여 있다면 signed 값은 암묵적으로 unsigned로 형변환이 된다.
예시로, -1 와 0U(C에서 unsigned 리터럴은 U를 붙인다)가 있다고 하면 -1는 unsigned로 바뀌어 UMax가 된다 (-1은 2의 보수에서 111…1로 표현된다). 따라서 다음 코드를 실행하면
출력값은 4294967295가 된다 (직접 실행해보자!).
암묵적인 형변환은 예상치 못한 곳에서 버그를 일으킬 수 있다. 예를 들어 다음과 같이 배열을 역순으로 루프하고 싶다고 하자.
만약 i가 unsigned이라면 이 코드는 무한루프에 빠진다. i=0일때 i--는 오버플로우를 일으켜 i=UMax가 되기 때문이다.
하지만 i가 signed라도 같은 일이 일어날 수 있다. 다음의 코드를 보자.
sizeof는 unsigned를 리턴하기 때문에 i - sizeof(char)를 계산하는 과정에서 암묵적인 형변환이 일어나, 결과값도 unsigned가 된다! 또 무한루프가 일어날 수 있는것이다.
이번엔 부호 확장을 알아보자. 주어진 w 비트 2의 보수 숫자를 w+k비트로 확장시키고 싶을때 사용되는 기법이다(int를 long으로 형변환하고 싶을때 등). 부호 확장을 할때 새로운 k 비트들은 모두 부호 비트와 같다.
이렇게 부호 확장을 해서 만든 새 숫자는 기존의 숫자와 값이 같다. 만약 옛 숫자가 1000 이고 두자리 더 늘리고 싶다면 부호 확장을 해서 111000이 된다.
이게 되는 이유는 옛 부호 비트는 -8을 나타냈는데, 111000은 -32 + 16 + 8 = -8을 아직 나타내기 때문이다. 새 부호 비트가 훨씬 커졌지만 새로 추가된 비트들이 숫자를 작게 만든다.
그렇다면 길이제한이 늘어나는 대신 작아진다면 어떻게 해야할까 (int → short처럼)? 그냥 비트를 버리면 된다.
예를 들어 11011 이라는 unsigned 수가 있고 4비트로 만들고 싶다고 하자. 그러면 단순히 5번째 비트를 버려서 1011이 된다. 27에서 11이 된 것이다.
언뜻 보면 모르겠지만 여기에는 규칙이 있다. 비트를 버릴때 16으로 나눈 나머지가 된다는 것이다. 일반적으로 w비트 수를 더 작은 w’비트로 만들때 새로운 수는
로 나눈 나머지가 된다.
unsigned대신 signed를 버릴때도 똑같다. 10011를 4비트로 만들면 0011이 되어, -13에서 3이 된다. 이건 쉽게는 설명할 수 없지만 비슷하게 규칙이 있다고 생각하자 (mod 연산을 안다면 -13 = 3 mod 16이란걸 눈치챌 것이다).
2. 덧셈과 곱셈
두 w 비트 unsigned int를 더한다고 하면 만약 받아올림을 했을때 나오는 비트는 단순히 버려지게 된다. UAdd(u, v)를 이때의 덧셈이라고 정의할때 
가 성립한다 (UAdd(u, v)는 u + v를 2^w로 나눈 나머지이다).
표현할 수 없는 비트는 버린다는걸 수학적으로 나타낸것 뿐이다.
예를 들어 w=4일때 
이라서 합은 1101 + 0101 = 10010을 2^4로 나눈 나머지인 0010이 된다 (그냥 4비트를 초과하는 자리를 버린거다). signed int도 똑같이 작동한다.
덧셈이 항상 올바른 답을 리턴하는건 아니다. 저 규칙에 따르면 1101 + 1010 = 0111이다. -3 + -6 = 7이 된다는 뜻이다. 단순히 -9는 4비트로 표현될 수 없으므로 음수 오버플로우가 난 것이다.
곱셈도 비슷하게 나타낼 수 없는 비트는 버려지고 
가 된다.
예를 들어 0101 * 0101 = 11001 (5 * 5 = 25) 인데 첫번째 비트가 버려져서 1001 (9) 가 된다. 25 = 9 mod 16이니 UMult의 정의와 같다.
signed int도 똑같이 담을 수 없는 비트는 버려진다. 다시 0101 * 0101 = 11001을 보면 결과값은 1001이 되며 이건 2의 보수로 계산했을때 -8 + 1 = -7이 된다. 두 양수를 곱했는데 음수가 나왔다! 오버플로우가 나타난 것이다.
2의 제곱을 곱하는건 시프트 연산자로 간단하게 할 수 있다. u << k =
이며 u >> k = 
이다.
오른쪽 시프트를 구현하려면 일단 
을 u에 더하고 산술 시프트를 한다. 더하지 않으면 floor가 0방향 대신 -∞ 방향으로 반올림되며, 산술 시프트를 하지 않으면 음수를 2의 배수로 나눈게 양수가 될수도 있다.
예를 들어 -7 / 4 를 보자. 반올림되면 -2이나 -1이 될 수 있는데, 0방향으로 반올림되어야 하니 -1 = 1111이 나와야 한다.
-7 / 4는 -7 >> 2와 같으므로 앞에 말한대로 해본다. 
을 더하면 -7 + 3 = -4 = 1100 이고 산술 시프트를 하면 1100 >> 2 = 1111로 올바른 답이 나온다.
하지만 더하지 않고 바로 시프트를 할 경우 -7=1001, 1001 >> 2 = 1110=-2로 틀린 답이 나온다.
3. 메모리
우리는 메모리를 아주 긴 바이트의 배열로 생각할 수 있다.
실제로는 그렇지 않지만 이렇게 생각하면 도움이 된다. 메모리 주소는 이 배열의 인덱스와도 같고, 포인터는 이 인덱스를 저장하는 변수이다.
워드 크기란 이 배열의 크기를 나타낼 수 있는 비트의 수이다. 예를 들어 워드 크기가 32비트인 컴퓨터는 메모리 주소가 2^32 까지 있다 (~4GB). 워드 크기가 64비트면 이론적으로 18페타바이트까지의 메모리 주소를 나타낼 수 있다.
주로 우리는 메모리 주소를 각 바이트 단위로 구분하지만 워드, 또는 더 나아가 임의의 크기의 블록 단위로도 구분할 수 있다. 오른쪽에서 두번째에 메모리를 나타내는 바이트 배열이 있고, 맨 오른쪽에는 각 바이트의 주소가 표시되어 있다. 왼쪽은 이 배열을 32비트 또는 64비트 워드 단위로 구분했을때 어떻게 되는지를 보여준다.
각 워드의 주소는 그 워드가 포함한 바이트 중 주소가 제일 낮은 바이트의 주소이다.
또 이렇게 워드 단위로 구분하게 되면 생각할게 하나 있다. 워드 안의 바이트가 여러개 있을텐데, 그 바이트들의 순서는 어떻게 되는가?
최상위 바이트를 앞쪽 주소에 저장하는걸 빅 엔디안이라 부르고, 최상위 바이트를 뒷쪽 주소에 저장하는걸 리틀 엔디안이라 한다 (참고로 엔디안이라는 용어는 걸리버 여행기에서 따왔다).
말로만 하면 이해가 잘 안되니 예시를 보여주겠다. 0x01234567이라는 값을 생각해보자(C에서 0x가 앞에 붙으면 16진수라는 뜻이다). 이 값이 0x100이라는 메모리 주소에 저장되어 있다고 하자.
이렇게 빅 엔디안을 쓰는 컴퓨터는 최상위 바이트인 01을 앞쪽에, 리틀 엔디안을 쓰면 뒤쪽에 저장하는걸 볼 수 있다.
다만 C의 문자열은 엔디안과 무관하게 읽혀진다. C 문자열의 마지막 문자는 항상 널문자(0 또는 ‘\0’)이기 때문이다.
4. 부동소수점
이진법으로 정수를 표현하는 법을 알아봤으니 이제는 실수를 표현하는 방식에 대해 생각해보자. 가장 간단한 방법은 소수점 아래의 자리도 int처럼 나타내는 것이다.
1011.101는 10진법으로 뭘까? 다음과 같이 소수점 오른쪽의 자릿수는 2의 음수 제곱을 나타낸다. 따라서
이다.
하지만 이렇게 실수를 나타낼 경우 문제점이 있다. 첫번째는 모든 실수를 정확하게 나타낼 수 없다는 것이다. 예를 들어 
라는 무한소수가 된다.
두번째는 우리에게 w 비트가 주어졌을때 이중 몇자리는 소수점 윗부분을, 나머지는 소수점 아랫부분을 나타내는데 써야 한다는 것이다.
따라서 우리가 표현할 수 있는 실수의 범위가 제한된다. 소수점 윗부분에 비트를 많이 쓰게 되면 소수점 아래부분을 표현하지 못하고, 반대도 마찬가지다.
이걸 해결하기 위해 1985년에 발명된게 IEEE 754 표준 부동소수점이다 (1985년 이전에는 실수 표현이 중구난방이였다). 모든 주요 CPU에서 지원되는 하나의 표준이 탄생한 것이다.
부동소수점에선 실수를 다음과 같이 표현한다.
s는 부호 비트이다. 숫자가 양수인지 음수인지를 나타낸다. M은 가수부라고 하며, 1.0 ≤ M < 2.0 이다. E는 지수부라고 하며 2를 몇번 제곱하는지를 나타낸다. 과학적 기수법을 알고 있다면 부동소수점이 아주 비슷하게 보일 것이다. 사실 과학적 기수법의 2진수 버전이 부동소수점이다.
다음은 이 정보를 실제로 저장하는 방법이다. 가장 흔히 쓰는 w=32일때와 w=64일때 두가지 경우를 보여주겠다.
exp는 e를 나타내지만 e는 아니며, frac도 M을 나타내지만 M과 다르다. 이게 무슨 뜻인지는 곧 살펴보겠다.
부동소수점에서 정규화된 값은 exp가 000…0 또는 111…1 이 아닐때를 말한다.
지수부 E = exp - bias이다 (bias = 
, k는 exp의 길이).
이렇게 정의된 이유는 exp는 unsigned로 저장되어있으나 E로 변환되면 2의 보수가 되어서이다. 두 2의 보수가 주어졌을보다 두 unsigned가 주어졌을때기 더 비교하기 쉽다.
1.0 ≤ M < 2.0이니 가수부 M은 
의 형태이다. 이때 우리는 1을 굳이 저장할 필요가 없다. 모든 가수부는 1로 시작하기 때문에 1은 암시적이라서이다. 따라서 우리가 저장하는건 
이다.
예를 들어 float 15213.0을 어떻게 저장할지 보자.
우선 
이다. 그렇다면 frac = 1101101101101이고 E = 13 이니
이다.
아까 정규화된 값은 exp가 000…0 또는 111…1 이 아닐때를 말한다고 했는데, 그럼 exp = 000…0일때는 뭘 나타낼까?
exp = 000…0일때는 비정규화된 값이라 하고, 0에 가까운 숫자들을 나타내도록 한다.
비정규화된 값에서는 E = 1- Bias 이며 가수부는 
형태이다 (따라서
).
이렇게 정의하는 이유는 정규화된 값에서 비정규화된 값으로 넘어갈때 깔끔하게 전환할 수 있어서이기 때문이다.
예를 들어 exp = 000…0, frac = 000…0은 숫자 0을 나타낸다.
exp = 111…1일때는 특수한 값을 나타낸다. frac=000…0이면 무한대를 나타내며 frac ≠ 000…0이면 NaN값을 나타낸다.
다음과 같이 수직선상에 부동소수점이 표현할 수 있는 값들을 나타낼 수 있다. Denorm은 비정규화된 값이다.
이제 부동소수점의 덧셈과 곱셈은 어떻게 작동하는지 보자. 덧셈을 할때는 먼저 정확한 합을 구한 뒤 주어진 비트 안에 맞게 반올림한다.
반올림할때는 소수부분이 0.5보다 작으면 버리고, 0.5보다 크면 올리며, 0.5라면 가장 가까운 짝수로 반올림한다. -1.5는 -2와 가장 가까우니 반올림하면 -2가 된다.
예를 들어 10.11100을 소수부 둘째자리까지 반올림한다고 하자. 둘째자리 이후의 비트가 100이니까 절반부분에 있다는 뜻이다. 그렇다면 가장 가까운 “짝수”로 반올림해야한다. 이진법의 “짝수”는 최하위 비트가 0일때이므로 가장 가까운 짝수는 11.00이 된다. 따라서 소수부 둘째자리까지 반올림하면 11.00이다.
0강에서 부동소수점의 덧셈은 결합법칙이 성립하지 않는다고 보았다. (3.14 + 1e20)-1e20 = 0이지만 3.14+(1e20-1e20)=3.14이기 때문이다.
다만 교환법칙은 성립한다(x+y=y+x). 또한 무한대와 NaN을 제외한 모든 수는 덧셈의 역원이 있으며 (마이너스 부호를 앞에 붙일 수 있다) a ≥ b라면 a + c ≥ b + c가 성립한다 (단조성).
부동소수점의 곱셈을 할때 두 가수부를 곱한게 2보다 크거나 같을경우 새로운 M을 오른쪽 시프트하고 E를 1만큼 증가시킨다.
덧셈과 비슷하게 곱셈도 결합법칙이 성립하지 않는다. 오버플로우가 일어날 수도 있고 반올림할때 오차가 생길 수 있기 때문이다. 예를 들어 (1e20 * 1e20) * 1e-20 = ∞ 이지만 1e20 * (1e20 * 1e-20) = 1e20이다.
같은 이유로 분배법칙또한 성립하지 않는다. 1e20 * (1e20 - 1e20) = 0.0인데 반해 1e20 * 1e20 - 1e20 * 1e20 = NaN이기 때문이다 (∞ - ∞ = NaN).
a ≥ b && c ≥ 0 이면 ac ≥ bc일까? 이 수들이 무한대나 NaN이 아니라면 성립한다. 이걸 곱셈의 단조성이라 한다.
마지막으로 오늘 배운걸 테스트해보자.
오늘 나간 진도는 CSAPP 2.1 ~ 2.4장이고 강의영상 02, 03, 04에 해당한다. 더 자세히 알고 싶다면 책을 읽어보면 도움이 될 것이다.
궁금하거나 이해 잘 안되는거 있으면 댓글로 물어보면 내가 아는선에서 최대한 답변해줄테니 많이 물어봐라.
긴글 읽어줘서 고맙고 다음에는 수업의 첫번째 실습인 데이터랩에 대한 간단한 설명을 하겠다.
