컴퓨터공학 300 주제 시리즈의 082번째 글이다. 전체 지도는 여기.

한 줄 요약

2의 보수는 n 비트 패턴의 최상위 비트에 −2^(n−1) 의 무게를 주어 음수를 표현하는 방식이다. 덧셈 회로 하나로 부호 있는 수와 없는 수를 함께 계산할 수 있게 해 주지만, 범위를 넘으면 값이 조용히 반대편으로 넘어간다. 이것이 오버플로다.

왜 필요한가

정수 변수는 무한하지 않다. 32비트 int 는 약 ±21억에서 끝난다. 이 경계를 넘을 때 무슨 일이 생기는지는 언어마다 다르다.

  • C 의 부호 있는 정수 오버플로는 정의되지 않은 동작이다. 컴파일러가 “일어나지 않는다” 고 가정하고 코드를 지울 수 있다.
  • 자바는 조용히 감아 돌린다(wrap).
  • 러스트는 디버그 빌드에서 패닉, 릴리스 빌드에서 감아 돌린다.
  • 파이썬 int 는 임의 정밀도라 넘치지 않는다.

같은 a + b 가 언어에 따라 다른 결과를 낸다. 하드웨어가 어떻게 계산하는지 알아야 이 차이를 설명할 수 있다.

핵심 개념

세 가지 후보

음수를 표현하는 방법은 역사적으로 셋이 있었다. 8비트로 −5 를 적어 보자.

방식 −5 0 의 표현 문제
부호-크기 1000 0101 +0, −0 두 개 덧셈 회로가 부호를 따로 봐야 함
1의 보수 1111 1010 +0, −0 두 개 끝자리 올림(end-around carry) 필요
2의 보수 1111 1011 하나 없음(범위가 비대칭일 뿐)

오늘날 범용 CPU 는 사실상 모두 2의 보수를 쓴다. C++20 과 C23 은 표준 차원에서 부호 있는 정수를 2의 보수로 못박았다.

정의: 최상위 비트의 무게가 음수다

n 비트 패턴 b(n−1) … b0 의 2의 보수 값은 다음과 같다.

값 = −b(n−1)·2^(n−1) + b(n−2)·2^(n−2) + ... + b0·2^0

8비트 1111 1011 = −128 + 64 + 32 + 16 + 8 + 2 + 1 = −5.

범위는 −2^(n−1) 부터 2^(n−1) − 1 까지다. 8비트면 −128 ~ 127. 음수 쪽이 하나 더 많다. 그래서 −(−128) 은 8비트 안에 담기지 않는다.

부호 바꾸기: 뒤집고 1 더하기

 5 = 0000 0101
뒤집기 1111 1010
+1     1111 1011 = −5

이유는 간단하다. x 와 ~x 를 더하면 모든 비트가 1, 곧 −1 이다. 그러므로 ~x = −x − 1, 정리하면 −x = ~x + 1.

덧셈 회로 하나로 충분하다

2의 보수의 진짜 장점은 하드웨어다. n 비트 덧셈기는 결과를 2^n 으로 나눈 나머지만 남긴다. 2의 보수는 “음수 x 를 2^n + x 로 저장” 하는 것과 같으므로, 모듈러 산술 안에서 부호 있는 덧셈과 부호 없는 덧셈이 같은 비트 연산이 된다. 뺄셈은 a + (~b + 1) 로 처리된다. CPU 는 덧셈 결과에 대해 두 개의 플래그를 따로 세운다.

플래그 의미 언제 보는가
캐리(C) 최상위 비트에서 올림이 나갔다 부호 없는 수로 볼 때의 범위 초과
오버플로(V/OF) 부호 있는 결과가 범위를 넘었다 부호 있는 수로 볼 때의 범위 초과

오버플로 판정 규칙은 외우기 쉽다. 부호가 같은 두 수를 더했는데 결과의 부호가 다르면 오버플로다. 부호가 다른 두 수의 합은 절대 넘치지 않는다.

 0110 0100  (100)
+0001 1100  ( 28)
=1000 0000  (−128)   양수+양수=음수 → 오버플로, 캐리 없음

부호 확장과 산술 시프트

8비트 −5 (1111 1011) 를 16비트로 넓힐 때는 최상위 비트를 복사해 채운다(1111 1111 1111 1011). 0 으로 채우면 251 이 된다. 오른쪽 시프트도 마찬가지로, 부호 있는 수에는 부호 비트를 복사하는 산술 시프트를 쓴다. 이때 −7 » 1 은 −3 이 아니라 −4 다. 0 쪽이 아니라 음의 무한대 쪽으로 내림하기 때문이다.

언어별 오버플로 처리

언어 부호 있는 정수 오버플로 근거
C 정의되지 않은 동작 (부호 없는 정수는 2^n 모듈러) ISO C 표준
Java 2의 보수로 감아 돌림, 예외 없음. Math.addExact 는 예외 JLS 4.2.2
Rust 디버그 빌드 패닉, 릴리스 빌드 감아 돌림. checked_add 등 제공 The Rust Book 3.2
Python 임의 정밀도, 오버플로 없음 언어 사양

직접 해 보기

8비트 2의 보수를 파이썬으로 흉내 낸다. python3 로 실행해 확인했다.

BITS = 8
MASK = (1 << BITS) - 1

def enc(x):            # 정수 -> 8비트 패턴
    return x & MASK

def dec(p):            # 8비트 패턴 -> 부호 있는 정수
    return p - (1 << BITS) if p & (1 << (BITS - 1)) else p

for x in (5, -5, -1, -128, 127):
    print(f"{x:5d} -> {enc(x):08b}")

def add8(a, b):
    raw = enc(a) + enc(b)
    carry = raw >> BITS
    r = dec(raw & MASK)
    overflow = (a >= 0) == (b >= 0) and (r >= 0) != (a >= 0)
    return r, carry, overflow

for a, b in [(100, 27), (100, 28), (-100, -29), (-1, 1), (50, -70)]:
    print(a, b, add8(a, b))

import struct
print(struct.unpack("<i", struct.pack("<I", 0xFFFFFFFF))[0])
print(struct.unpack("<i", struct.pack("<I", 2**31))[0])
print(2**63 + 1)
print(-7 >> 1, -7 // 2)

출력:

    5 -> 00000101
   -5 -> 11111011
   -1 -> 11111111
 -128 -> 10000000
  127 -> 01111111
100 27 (127, 0, False)
100 28 (-128, 0, True)
-100 -29 (127, 1, True)
-1 1 (0, 1, False)
50 -70 (-20, 0, False)
-1
-2147483648
9223372036854775809
-4 -4

(-1, 1) 은 캐리가 나갔지만 부호 있는 결과 0 은 정확하다. 캐리와 오버플로가 서로 다른 신호라는 것을 보여 준다. struct 예제는 같은 32비트 패턴 0xFFFFFFFF 가 부호 있는 정수로는 −1 이라는 점을 확인한다.

현업에서는

  • 이진 탐색 중간값: mid = (lo + hi) / 2 는 lo, hi 가 크면 32비트에서 넘친다. lo + (hi - lo) / 2 로 쓰는 이유다.
  • ID·카운터 고갈: DB 의 32비트 integer 기본 키는 약 21억에서 끝난다. PostgreSQL 문서도 integer 범위를 −2147483648 ~ +2147483647 로 적는다. 트래픽이 큰 테이블은 처음부터 bigint 로 잡는다.
  • 언어 경계: 자바 long 을 JSON 으로 내보내 자바스크립트가 받으면 2^53 을 넘는 값이 깨진다(부동소수점 문제, 다음 글). 64비트 ID 를 문자열로 내보내는 API 가 많은 이유다.
  • 보안: 버퍼 크기 계산의 정수 오버플로는 작은 메모리를 할당한 뒤 큰 데이터를 쓰게 만드는 고전적인 취약점 경로다. 크기 계산에는 검사 연산(__builtin_add_overflow, checked_mul)을 쓴다.

확인 문제

  1. 8비트 2의 보수에서 1000 0001 은 얼마인가.
  2. 16비트 부호 있는 정수의 범위를 적어라.
  3. 8비트에서 (−100) + (−29) 의 결과 패턴과 해석된 값을 구하고, 오버플로인지 판정하라.
  4. C 에서 int 오버플로를 검사하려고 if (a + b < a) 라고 쓰면 왜 위험한가.

풀이

  1. −128 + 1 = −127.
  2. −32,768 ~ 32,767.
  3. 합 −129 는 범위 밖이다. 하위 8비트는 0111 1111 = 127. 음수+음수=양수이므로 오버플로다.
  4. 부호 있는 오버플로가 정의되지 않은 동작이라 컴파일러가 그 조건을 항상 거짓으로 보고 검사를 제거할 수 있다. 연산 전에 범위를 비교하거나 내장 검사 함수를 쓴다.

더 읽을거리 (References)