7 정수의 표현 — 부호, 오버플로, 시프트

먼저 알아야 할 것

4장 단순한 기계 모델 · 기계가 다루는 것은 고정된 폭의 비트 묶음이다

5장 워드와 주소 · 워드와 바이트

돌아보기

5장에서 여러 바이트를 이어 붙여 큰 수를 담는다 했고, 엔디안(넣는 순서)까지 보았다. 그런데 지금까지의 수는 전부 0 이상이었다. 음수는 — 비트 어디에 마이너스 기호를 담는가?

답. 담을 곳이 없다 — 비트에는 0과 1뿐, 마이너스 기호가 없다(4장). 그래서 음수 역시 약속으로 만든다. 어떤 비트 패턴을 음수로 “읽기로” 정하는 것이다. 그 약속을 정하는 방법이 하나가 아니었다는 것, 그리고 그 경쟁의 결말이 이 장의 한복판이다.

이 장의 필요성과 맥락

여기서부터 세 장(7·8·9)이 「표현의 사다리」다 — 정수, 실수, 글자를 차례로 비트에 담는다. 정수가 첫 단인 이유는 나머지 둘이 그 위에 서기 때문이다. 부동소수점의 지수도 정수이고, 문자 코드도 결국 정수다. 그리고 2의 보수·오버플로·시프트는 26장 이후의 타입 이야기가 통째로 기대는 바닥이다.

이 장이 끝나면

표현의 사다리 첫 단이다. 부호 없는 정수가 어떻게 순환하는 수(모듈러) 인지, 음수를 비트로 담는 세 가지 방법이 어떻게 겨루다 2의 보수로 정리됐는지 — 그리고 C23이 마침내 무엇을 못박았는지 — 를 본다. 넘치는 수(오버플로)와, 비트를 통째로 밀고 당기는 시프트(shift)까지 챙기면, 정수에 관한 배경지식이 완성된다.

이 장에서 답할 질문

그런데 왜 이름이 “보수”인가? 그리고 1의 보수, 2의 보수라는 이름에서 1과 2는 무엇을 가리키는가?
표현이 2의 보수로 못박혔으니, 이제 부호 있는 오버플로도 “감아 돌기”로 정의된 것인가?
비트를 밀고 채우는 규칙까지 알아야 할 만큼, 시프트가 중요한 연산인가?
8비트짜리 수를 여덟 칸, 혹은 그 이상 밀면 어떻게 되는가? 상식적으로는 전부 밀려나 0이 될 것 같은데.
1을 잔뜩 채웠는데 왜 값이 그대로인가? 우연인가?

7.1 부호 없는 정수 — 시계처럼 도는 수

먼저 마이너스 걱정이 없는 세계부터 정리한다. $𝑛$ 비트를 그냥 2진수로 읽으면 $0$ 부터 $2^{𝑛} - 1$ 까지, $2^{𝑛}$ 개의 수가 담긴다(4장). 이것이 부호 없는(unsigned) 정수다. 8비트면 0–255다.

이 수의 세계에서 꼭 챙길 성질이 하나 있다. 끝이 처음과 이어져 있다는 것이다. 255에서 1을 더하면 256이 아니라 — 256을 담을 아홉 번째 비트가 없으므로 — 0이 된다. 12시에서 한 시간이 지나면 1시가 되는 시계와 같은 구조다. 수학에서는 이런 셈을 모듈러 산술이라 부른다.

그림의 안쪽 눈금이 미리 답해 주는 것이 하나 있다 — 같은 비트를 부호 있는 타입으로 읽으면 원의 반대쪽이 음수가 된다. 다음 절이 그 이야기다.

수학. 모듈러 산술 — 유한한 수의 정확한 수학

$𝑛$ 비트 부호 없는 정수의 덧셈·뺄셈·곱셈은 결과를 $2^{𝑛}$ 으로 나눈 나머지를 취하는 연산과 정확히 같다:

결과 = (𝑎 + 𝑏) mod 2^{𝑛}

8비트에서 $250 + 10 = 260 mod 256 = 4$ 다. 중요한 것은 이것이 “틀린 덧셈”이 아니라 다른 덧셈 — 완전히 정의된, 예측 가능한 수학 — 이라는 점이다. C 표준도 부호 없는 정수의 넘침을 오류가 아니라 이 수학으로 정의한다.

이 순환에는 이름이 있다 — 오버플로(overflow), 정확히는 “감아 돌기”(wrap-around)다. 정의된 동작이라 해도, 예상하지 못한 자리에서 일어나면 사고가 된다.

실제 사례. 256판의 벽 — 팩맨 킬 스크린

오락실 게임 팩맨에는 유명한 벽이 있다. 255판까지는 멀쩡히 진행되다가 256판째에 화면 오른쪽 절반이 뜻 모를 기호로 뒤덮이며 게임이 불가능해 진다. 판 번호를 8비트로 세던 코드가 255를 넘는 순간 0으로 감아 돌았고, “지금 몇 판인지”를 전제로 과일을 그리던 루틴이 엉뚱한 개수를 그리며 화면을 부순 것이다. 설계자가 “256판까지 갈 사람은 없다”고 여겼던 그릇의 크기가, 최고수들의 도전 앞에서 벽이 된 사례다 — 그릇의 크기는 언제나 누군가에게는 닿는 벽이 된다.

7.2 음수를 담는 세 가지 약속

이제 음수다. 관건은 $𝑛$ 비트 패턴의 절반쯤을 음수로 “읽기로” 약속하는 방식인데, 역사상 세 가지 약속이 실제로 쓰였다. 8비트로 $- 5$ 를 담는 경우로 비교한다.

첫째, 부호-크기(sign-magnitude). 사람의 표기를 그대로 흉내 낸다 — 맨 앞 비트를 마이너스 기호로 쓰고(1이면 음수), 나머지에 크기를 담는다. $- 5$ 는 1_0000101. 직관적이지만 두 가지 대가가 있다. 00000000(+0)과 10000000(−0), 0이 두 개 생긴다. 그리고 덧셈 회로가 골치다 — 부호가 다른 두 수를 더하려면 “크기를 비교해서 큰 쪽에서 작은 쪽을 빼고 부호를 정하는” 별도 절차가 필요하다.

둘째, 1의 보수(ones’ complement). 음수를 만들 때 모든 비트를 뒤집는다. $5$ 가 00000101이니 $- 5$ 는 11111010. 덧셈 회로가 한결 단순해지지만, 여전히 0이 두 개다(00000000과 11111111) — 비교할 때마다 “두 0은 같은 것으로 친다”는 예외를 끌고 다녀야 한다.

셋째, 2의 보수(two’s complement). 비트를 뒤집고 1을 더한다. $- 5$ 는 11111010 + 1 = 11111011. 언뜻 임의로 보이는 이 규칙이 사실은 가장 우아하다 — 0이 하나뿐이고, 무엇보다 부호 없는 덧셈 회로를 그대로 쓰면 부호 있는 덧셈이 저절로 맞는다. 별도 절차도 예외도 없다.

문. 그런데 왜 이름이 “보수”인가? 그리고 1의 보수, 2의 보수라는 이름에서 1과 2는 무엇을 가리키는가?

답. 보수(補數, complement)는 “채워서 어떤 기준을 완성해 주는 수”다. 십진법으로 먼저 감을 잡으면 쉽다 — 세 자리 수 304에 대해, 각 자리를 9까지 채워 주는 695를 9의 보수라 하고(모든 자리에서 $9 - 그 자리$ ), 1000까지 채워 주는 696을 10의 보수라 한다( $10^{3} - 304$ ). 둘의 관계는 “9의 보수 + 1 = 10의 보수”다.

2진법에서 똑같은 일을 하면 이름의 뜻이 풀린다. 각 자리를 1까지 채워 주는 수 — 즉 11111111에서 빼는 것 — 가 1의 보수인데, 2진법 에서 $1 - 비트$ 는 곧 비트 뒤집기라서 “뒤집는다”는 규칙이 나온 것이다. 그리고 $2^{𝑛}$ — 이진법의 “ $1000 \dots 0$ ”, 즉 2의 거듭제곱 — 에서 빼는 것이 2의 보수다. “뒤집고 1을 더한다”는 요령은 십진법의 “9의 보수 + 1 = 10의 보수”와 똑같은 관계다.

영어 표기도 여기서 정리해 둔다. 통용 표기는 one’s complement와 two’s complement다(“1s’”나 “2s’” 같은 표기는 없다). 다만 전산학자 커누스(Knuth)는 재치 있는 구별을 주장했다 — 1의 보수는 “모든 자리의 1들에 대한 보수”이므로 복수 소유격 ones’ complement가 옳고, 2의 보수는 “ $2^{𝑛}$ 이라는 하나의 수에 대한 보수”이므로 단수 소유격 two’s complement가 옳다는 것이다. 문법 트집 같지만 두 보수의 수학적 정의 차이(자리별 기준 vs 전체 기준)를 정확히 담은 구별이고 — 실제로 C 표준 문서 자신이 이 구별을 채택했다. 표준의 표현 조항은 세 방식을 “sign and magnitude”, “two’s complement”, “ones’ complement”라고 적는다. 커누스의 트집이 법전에 이긴 셈이다. 교과서 용어로는 2의 보수를 기수 보수(radix complement), 1의 보수를 감소 기수 보수(diminished radix complement)라고도 부른다.

수학. 2의 보수가 우아한 이유 — 모듈러 산술의 재활용

2의 보수의 정체는 위의 모듈러 산술이다.

- 𝑥

를

2^{𝑛} - 𝑥

라는 패턴으로 담는 약속이므로, 8비트에서

- 5

는

256 - 5 = 251

, 즉 11111011이다. 그러면

7 + (- 5)

는 회로 입장에서

7 + 251 = 258 mod 256 = 2

— 답이 저절로 맞는다. 음수란 “모듈러 시계에서 반대 방향으로 세는 것”일 뿐이라서, 회로는 부호를 아예 몰라도 된다. 유일한 비대칭은 범위다 — 8비트에서

- 128

부터

+ 127

까지로, 음수가 하나 더 많다(

- 128

의 짝

+ 128

이 없다).

7.3 세 약속의 경쟁, 그리고 C23의 결단

세 방식 모두 실제 기계에 쓰였다 — 부호-크기와 1의 보수는 초기 대형기들(UNIVAC, CDC 계열 등)에 실존했다. C가 표준화되던 1989년에도 그런 기계들이 현역이었기 때문에, C 표준은 어느 편도 들지 않았다. 세 가지 표현을 모두 허용한 것이다. 이 중립은 공짜가 아니었다 — 표현이 다르면 같은 연산의 결과 비트가 달라지므로, 표준은 부호 있는 정수의 많은 동작을 “기계마다 다르다”로 남겨 둘 수밖에 없었다. 부호 있는 오버플로가 정의되지 않은 동작(52장)이 된 사연의 절반이 여기에 있다.

그사이 현실은 한쪽으로 수렴했다. 2의 보수의 회로 단순성이 압도적이라 수십 년간 새로 만들어진 CPU는 사실상 전부 2의 보수였고, 나머지 두 방식은 박물관으로 갔다. 그리고 C23이 마침내 결단했다 — 부호 있는 정수의 표현은 2의 보수다. 반세기의 관행이 표준의 약속으로 승격된 것이다(4장의 “바이트=8비트” 논의와 똑같은 무늬다).

문. 표현이 2의 보수로 못박혔으니, 이제 부호 있는 오버플로도 “감아 돌기”로 정의된 것인가?

답. 아니다 — 여기가 미묘하고 중요한 지점이다. C23이 못박은 것은 표현 (음수가 어떤 비트 패턴인가)이지, 오버플로의 의미가 아니다. 부호 있는 정수의 오버플로는 C23에서도 여전히 정의되지 않은 동작으로 남았다. 이유는 표현이 아니라 최적화다 — “부호 있는 수는 넘치지 않는다”는 전제가 컴파일러(13장)의 루프 분석과 재배열에 요긴해서, 표준은 그 전제를 유지하는 쪽을 택했다. 요약하면: 부호 없는 넘침 = 정의된 감아 돌기, 부호 있는 넘침 = 여전히 계약 밖. 실무 규칙은 27장에서 다룬다.

흔한 오해. “오버플로가 나면 컴퓨터가 오류를 알려 준다”

그럴듯한 기대다 — 잘못된 일이 생기면 알려 주는 것이 도리이니까. 그러나 CPU의 덧셈 회로는 넘침의 순간 내부 신호(플래그)를 올릴 뿐, 프로그램을 세우거나 알리지 않는 것이 기본이다. C도 마찬가지다 — 부호 없는 수는 조용히 감아 돌고, 부호 있는 수는 계약 밖(무슨 일이든 일어날 수 있음)이다. 팩맨의 화면이 요란하게 부서진 것은 오버플로 “경보”가 아니라 감아 돈 값이 낳은 후속 사고였다. 넘침의 감시는 기계가 아니라 프로그래머의 일이다 — 이것이 뒤에서 proven 같은 검증 도구가 산술을 검사하는 이유이기도 하다(43장, 88장).

7.4 시프트 — 비트를 통째로 밀기

정수의 비트를 다루는 기본 연산이 하나 더 있다 — 시프트(shift), 비트 열을 통째로 왼쪽이나 오른쪽으로 미는 것이다. 밀고 나면 두 가지 질문이 남는다. 밀려난 비트는 어디로 가고, 빈자리는 무엇으로 채우는가.

왼쪽 시프트는 답이 하나다. 위로 밀려난 비트는 버려지고, 아래 빈자리는 0으로 채운다. 00010110을 왼쪽으로 한 칸 밀면 00101100 — 십진법에서 끝에 0을 붙이면 10배가 되듯, 2진법의 왼쪽 한 칸은 2배다.

오른쪽 시프트는 답이 둘이다. 빈자리(맨 위)를 무엇으로 채우는가에 따라 갈린다.

논리 시프트(logical): 0으로 채운다. 부호 없는 수에 맞는 방식이고, 오른쪽 한 칸은 2로 나눈 몫이 된다.
산술 시프트(arithmetic): 부호 비트를 복사해 채운다. 2의 보수 음수는 맨 위 비트들이 1로 차 있으므로(위의 $- 5$ = 11111011), 1을 채워야 “2로 나누기”라는 뜻이 유지된다. 0을 채워 버리면 음수가 갑자기 거대한 양수처럼 읽힌다.

그래서 CPU들은 오른쪽 시프트 명령을 두 벌(논리/산술) 갖고 있고, C에서는 부호 없는 수의 오른쪽 시프트는 논리로, 부호 있는 음수의 오른쪽 시프트는 — 오랫동안 “기계마다 다르다”였다가 사실상 모든 구현이 산술을 쓰는 관행으로 수렴했다. 2의 보수 확정과 나란히, 관행을 약속으로 승격하는 방향의 정리다.

문. 비트를 밀고 채우는 규칙까지 알아야 할 만큼, 시프트가 중요한 연산인가?

답. 중요하다 — 두 가지 이유에서다.

첫째, 가장 싼 연산이기 때문이다. 시프트는 회로 입장에서 배선을 옆으로 옮기는 수준의 일이라, 거의 모든 CPU에서 한 박자짜리 최속 연산에 속한다. 방금 본 대로 왼쪽 $𝑘$ 칸은 $2^{𝑘}$ 배, 오른쪽 $𝑘$ 칸은 $2^{𝑘}$ 으로 나눈 몫이므로 — 2의 거듭제곱 곱셈·나눗셈을 시프트로 바꾸는 것은 고전적인 속도 요령이었다. 다만 오늘의 C에서는 그 요령을 사람이 부릴 필요가 없다. 소스에는 뜻 그대로 x * 2, x / 8이라 쓰면 되고, 컴파일러(13장의 편집자)가 알아서 시프트로 바꿔 준다. 가독성을 내주고 얻을 것이 없는 자리다.

둘째, 비트의 세계를 다루는 기본 동작이기 때문이다. 여러 값을 한 정수의 비트 자리들에 나눠 담고 꺼내는 일 — 9장에서 볼 UTF-8 바이트 조립, 6장의 태그 포인터, 색상값(RGB)의 분해, 하드웨어 레지스터의 플래그 읽기 — 이 전부가 “원하는 자리로 밀고, 필요한 비트만 남기는” 시프트+마스크의 조합이다. 수의 곱셈으로서의 시프트는 컴파일러에게 넘어갔지만, 자리 배치 도구로서의 시프트는 시스템 프로그래머의 일상 언어로 남아 있다. C 문법에서의 실제 사용은 28장에서 다룬다.

문. 8비트짜리 수를 여덟 칸, 혹은 그 이상 밀면 어떻게 되는가? 상식적으로는 전부 밀려나 0이 될 것 같은데.

답. 바로 그 “상식”이 기계마다 달랐다는 것이 함정이다. 시프트 칸수는 CPU 안에서 몇 비트짜리 회로가 처리하는데, 폭 이상의 칸수가 들어왔을 때의 대응이 갈렸다 — 어떤 CPU 계열(인텔 x86)은 칸수의 아래 몇 비트만 보고 나머지를 무시해서 32비트 수를 32칸 밀면 그대로이고, 다른 계열(옛 ARM 등)은 정말로 다 밀어서 0이 된다. 같은 코드가 기계마다 다른 답을 내는 것이다. C 표준의 대응은 이제 익숙한 패턴이다 — 어느 편도 들 수 없으니, 폭 이상의 시프트는 정의되지 않은 동작으로 계약 밖에 두었다. “기계들이 서로 다르게 대응하는 곳은 표준이 약속을 포기한다” — 이 무늬는 52장에서 정식으로 다시 만난다.

7.5 부호 확장(sign extension) — 좁은 그릇에서 넓은 그릇으로

시프트의 “무엇으로 채우는가”라는 질문은 한 군데서 더 나타난다. 8비트 그릇에 든 수를 16비트 그릇으로 옮겨 담을 때다. 늘어난 위쪽 여덟 칸을 무엇으로 채울 것인가.

부호 없는 수는 답이 자명하다 — 0으로 채운다(zero extension). 8비트의 11111011(=251)은 16비트의 00000000 11111011(=251)이 된다. 값이 그대로다.

부호 있는 수에서는 같은 방법이 사고를 낸다. 8비트의 11111011은 2의 보수로 $- 5$ 인데, 위를 0으로 채우면 16비트의 00000000 11111011 — 맨 앞 비트가 0이니 양수 251로 읽힌다. $- 5$ 가 그릇을 옮기다가 251이 된 것이다. 올바른 답은 산술 시프트와 같은 요령이다 — 부호 비트를 복사해 채운다. 11111111 11111011, 여전히 $- 5$ 다. 이것이 부호 확장(sign extension)이다.

문. 1을 잔뜩 채웠는데 왜 값이 그대로인가? 우연인가?

답. 우연이 아니라 모듈러 수학의 필연이다. 2의 보수에서 8비트의 $- 5$ 는 $2^{8} - 5 = 251$ 이라는 패턴이었고, 16비트의 $- 5$ 는 $2^{16} - 5 = 65531$ 이라는 패턴이다. 그런데 $65531 = 251 + 255 \cdot 256$ — 이진법으로 적으면 정확히 “원래 패턴 위에 1을 여덟 개 얹은 것”이다. 부호 비트 복사란 “ $2^{8}$ 에 대한 보수를 $2^{16}$ 에 대한 보수로 갈아 끼우는” 산술을 비트 복사 한 번으로 해치우는 요령이다. 2의 보수의 우아함이 여기서도 일한다 — 부호-크기나 1의 보수였다면 이런 공짜 확장은 없다.

거꾸로 넓은 그릇에서 좁은 그릇으로 줄여 담으면 위쪽 비트들이 그냥 잘려 나간다 — 값이 그릇에 안 들어가면 소리 없이 망가진다는 점에서 오버플로의 사촌이다. C는 계산 전에 작은 정수를 자동으로 넓히는 규칙 (정수 승격)을 갖고 있고, 넓히기·줄이기가 언제 일어나며 무엇이 위험한지 는 C의 정수 타입과 함께 27·28장에서 정식으로 다룬다 — 이 장의 그림 (0 채움 / 부호 복사 / 잘림)이 그때의 밑천이다.

정수의 배경지식이 완성됐다. 부호 없는 수는 시계처럼 도는 모듈러의 세계이고, 음수는 세 가지 약속의 경쟁 끝에 2의 보수로 정리되어 C23이 못박았으며, 넘침은 조용하고, 시프트와 그릇 옮기기(확장)는 채움의 방식 까지 알아야 뜻이 선다. C의 정수 타입들과 실무 규칙은 27·28장에서 이 배경 위에 세운다.

다음 장은 사다리의 다음 단이다 — 정수 너머, 소수점 있는 수를 담는 두 가지 방법과 IEEE 754라는 계약을 만난다.

← 이전목차로다음 →