2의 보수

3. 컴퓨터에서의 2의 보수

컴퓨터의 CPU를 구성하는 가장 중요한 요소는 ALU인데, 정수형 처리는 ALU에서 이루어진다. CPU의 비트 수 제한으로 인해 이진법 계산에서 비트를 벗어나면 버리게 된다.

CPU는 4비트부터 시작했지만, 주로 8비트와 32비트 이상을 많이 사용한다. 2의 보수를 적용할 때, 프로그램에서 부호를 지정하는 변수를 사용함으로써 구현할 수 있다. 예를 들어, 4비트 이진수 0010₂ (= 2)의 2의 보수는 1110₂이다. 실제로, 이 둘을 덧셈하면 다음과 같다.

:$$$$

\begin{array}{lrrrrr}

& & 0 & 0 & 1 & 0 \\

{}+{} & & 1 & 1 & 1 & 0 \\

\hline

& \cancel{1} & 0 & 0 & 0 & 0

\end{array}



결과는 10000₂ = 2⁴ = 16이 되며, 1110₂이 0010₂의 10000₂에 대한 보수임을 확인할 수 있다. 또한 5비트째 이후를 무시하고 아래 4비트만 취하면 결과는 0000₂이 된다. 즉, 0010₂에 그 2의 보수 1110₂를 더하는 것은 0010에서 0010 자신을 빼는 것과 같은 의미를 가진다. 다시 말해, 1110₂는 음수 -2를 나타낸다.

3. 1. C 프로그래밍 언어에서의 2의 보수

4. 2의 보수 이론

2의 보수는 기수 보수의 한 예이다. N-비트 시스템에서 "2의 N승" ()을 나타내며, N-비트 숫자의 ''2의 보수''는 에 대한 해당 숫자의 보수이다.^[4] 예를 들어, 3비트 이진수(이고 )에서 숫자 3 ()의 2의 보수는 5 ()이다. 원래 숫자와 더하면 가 되기 때문이다.

이진 표현에서 최상위 비트는 부호를 나타낸다. 음이 아닌 첫 번째 그룹은 0이고, 음수의 두 번째 그룹은 1이다.

2의 보수는 덧셈, 뺄셈, 곱셈의 기본적인 산술 연산이 부호 없는 이진수와 동일하게 동작한다는 장점이 있다. 또한, 1의 보수와 달리 음의 영을 나타내는 방법이 없어 관련된 어려움을 겪지 않는다.^[4]

N비트 값에서 하위 절반은 0부터 까지, 상위 절반은 부터 −1까지의 정수를 나타낸다. 상위 절반은 을 법으로 하는 덧셈에서 음수와 동일하게 동작한다.^[11]

n자리 이진수 x와 그 보수 x_c는 다음 관계를 만족한다.

:$$$$

x + x_\mathrm{c} = 2^n

\quad(\iff

x_\mathrm{c} = 2^n - x

)\,.



의 배수를 0과 동일시하면, 위의 보수 관계는 을 법으로 하는 합동식으로 바꿀 수 있다.

:$$$$

x + x_\mathrm{c} \equiv 0 \pmod {2^n} \,.



이는 x의 보수 x_c를 x의 역수 -x로 볼 수 있다는 것을 의미한다. 즉, 수 y에서 x를 빼는 연산은 수 y와 보수 x_c의 덧셈으로 바꿀 수 있다.

:$$$$

y - x

\equiv y + 2^n - x

\equiv y + x_\mathrm{c} \pmod {2^n} \,.



마찬가지로 역수 -x의 곱셈은 보수의 곱으로 바꿀 수 있다.

:$$$$

y \cdot (- x)

\equiv y \cdot 2^n + y \cdot (- x)

\equiv y \cdot x_\mathrm{c} \pmod {2^n} \,.

5. 2의 보수 변환

2의 보수 표현은 양수와 음수를 모두 나타낼 수 있으며, 최상위 비트는 부호를 나타낸다. (0: 양수, 1: 음수)^[4]

N-비트 숫자 ''2의 보수''의 정확한 정의는 2^N에 대한 해당 숫자의 보수이다. 2의 보수를 구하는 방법은 다음과 같다:^[4]

• 1의 보수를 이용하는 방법:

• 2^N으로부터의 뺄셈:

• 최하위 비트(LSB)에서 최상위 비트(MSB) 방향으로 변환:

• 1의 보수를 이용하는 방법:

• 2⁸으로부터의 뺄셈:

n 자릿수의 이진수의 k+1 자릿수 값을 b_k ∈ {0, 1}이라고 하면, 2의 보수 표현은 다음과 같이 나타낼 수 있다.

:$$$$

{b_{n-1} b_{n-2} \cdots b_1 b_0}_{(2)}

\mapsto

• b_{n-1} \cdot 2^{n-1}

5. 1. 1의 보수로부터 변환

• 01001011의 모든 자리의 수를 반전시켜 1의 보수를 구한다: 10110100 (십진수 180)
• 1의 보수에 1을 더한다: 10110100 + 00000001 = 10110101 (십진수 181)

• 계산 결과: -8 + 0 + 2 + 0 = -6

• 5를 2의 보수로 표현하는 방법은 다음과 같다.

5. 2. 2^N으로부터의 뺄셈

5. 3. 최하위 비트(LSB)에서 최상위 비트(MSB) 방향으로의 변환

6. 부호 확장

2의 보수로 표현된 특정 비트 수의 정수를 더 많은 비트로 변환할 때(예: 1바이트 변수에서 2바이트 변수로 복사할 때), 최상위 비트는 추가된 모든 비트에 반복되어야 한다. 일부 프로세서는 이 작업을 단일 명령어로 수행하지만, 다른 프로세서에서는 조건문을 사용하여 관련 비트 또는 바이트를 설정하는 코드를 실행해야 한다.

숫자를 오른쪽으로 시프트할 때 부호 비트를 포함하는 최상위 비트는 유지되어야 한다. 그러나 왼쪽으로 시프트할 때는 비트가 밀려나간다. 이러한 규칙은 왼쪽 시프트가 숫자를 2배로 곱하고 오른쪽 시프트가 숫자를 2로 나누는 일반적인 의미를 유지한다. 그러나 최상위 비트가 0에서 1로(또는 그 반대로) 변경되면, 값이 부호 있는 정수를 나타내는 경우 오버플로가 발생한다.

7. 가장 작은 음수

2의 보수 표현에서 가장 작은 음수는 예외적인 경우이다. 이 수의 2의 보수는 자기 자신이다.^[4] 예를 들어, 8비트 시스템에서 -128의 2의 보수는 -128이다. -128의 음수화에서 예상되는 결과는 +128이지만, 8비트 2의 보수 시스템으로는 +128을 표현할 수 없으므로 실제로는 음수화를 표현할 수 없다. 2의 보수가 같은 숫자라는 것은 최상위 비트로의 자리올림은 있었지만 최상위 비트에서의 자리올림이 없었으므로 오버플로우 조건으로 감지된다.^[4]

0이 자신의 음수와 같고 숫자의 총 개수가 짝수라는 사실 때문에 0이 아닌 숫자가 자신의 음수와 같게 되는 것은 불가피하다.

최소 음수의 존재는 예기치 않은 프로그래밍 버그로 이어질 수 있다. 예를 들어,

• 단항 음수 연산자는 0이 아닌 숫자의 부호를 변경하지 않을 수 있다. 예: −(−128) ↦ −128.
• 절댓값 구현은 음수를 반환할 수 있다.^[6] 예: abs(−128) ↦ −128.
• 마찬가지로, −1을 곱하면 예상대로 작동하지 않을 수 있다. 예: (−128) × (−1) ↦ −128.
• −1로 나누면 (0으로 나누는 것과 같은) 예외가 발생할 수 있다.^[7] −1로 나머지(또는 모듈로)를 계산하는 것조차 이 예외를 발생시킬 수 있다.^[8] 예: (−128) ÷ (−1) ↦ , (−128) % (−1) ↦ .

8. 2의 보수와 2진수(2-adic Numbers)

빌 고스퍼는 1972년 MIT 인공지능 연구소(MIT AI Lab)에서 발표된 고전적인 ''HAKMEM''에서 2의 보수 표현이 2진수와 관련이 있음을 언급했다.^[16] 2진수는 무한한 비트 문자열을 숫자로 간주하는 방법을 제공한다.

고스퍼는 2의 거듭제곱을 연속적으로 합산하여 기계의 내부 표현이 2의 보수인지 판별할 수 있다고 지적하며, 이를 대수적으로 계산한 결과가 "대수는 2의 보수를 사용하는 기계(우주)에서 실행된다"는 것을 시사한다고 언급했다.^[16]

고스퍼의 결론은 수학적 유머에 가깝다. "...110 = ...111 − 1", 즉 "2''X'' = ''X'' − 1"이며, 따라서 ''X'' = ...111 = −1이다. 이는 무한한 1의 문자열을 숫자로 간주하는 것을 전제로 하며, 모든 정수에 대한 2의 보수 표기법의 일부로, 전형적인 2진수로, 또는 실수의 발산급수 1 + 2 + 4 + 8 + ···에 대해 정의된 일반화된 합 중 하나로 의미가 있다.^[17] 무한한 비트 문자열로 동작하도록 이상화된 디지털 산술 회로는 2의 보수 표현과 호환되는 2진수 덧셈과 곱셈을 생성한다.^[18] 2진수 메트릭에서 이진 산술 및 비트 연산의 연속성은 암호화에서도 어느 정도 사용된다.^[19]

9. 산술 연산

2의 보수 표현을 사용하면 덧셈, 뺄셈, 곱셈 등의 산술 연산을 간단하게 처리할 수 있다.

• '''덧셈''': 2의 보수 덧셈은 피연산자의 부호에 관계없이 수행할 수 있으며, 결과의 부호는 자동으로 결정된다.^[1]
• '''뺄셈''': 뺄셈은 빼는 수의 2의 보수를 더하는 방식으로 수행된다. 2의 보수에서는 가장 높은 자리에서 자리 올림이 발생할 때 이를 무시하므로 1의 보수보다 계산이 간단하다.
• '''곱셈''': 두 개의 N-비트 숫자의 곱은 모든 가능한 값을 포함하려면 2N 비트가 필요하다.^[13] 2의 보수를 사용하는 두 피연산자의 정밀도가 곱셈 전에 두 배로 늘어난다면, 직접 곱셈(그 정밀도를 넘어서는 비트는 버림)은 올바른 결과를 제공한다.^[14]
• '''비교''': 2의 보수 표현에서 두 수의 비교는 뺄셈을 통해 수행할 수 있다. 상태 레지스터의 제로 플래그는 두 값이 같은지 여부를 나타낸다. 부호와 오버플로 플래그의 배타적 논리합이 1이면 뺄셈 결과가 0보다 작고, 그렇지 않으면 0 이상이다.

10. 2의 보수 표현의 성질 (일본어 문서 내용)

4비트 이진수 0010₂ (= 2)의 2의 보수는 1110₂이다. 이 둘을 덧셈하면 다음과 같다.

:$$$$

\begin{array}{lrrrrr}

& & 0 & 0 & 1 & 0 \\

{}+{} & & 1 & 1 & 1 & 0 \\

\hline

& \cancel{1} & 0 & 0 & 0 & 0

\end{array}



결과는 10000₂ = 2⁴ = 16이 되며, 1110₂이 0010₂의 10000₂에 대한 보수임을 확인할 수 있다. 5비트째 이후를 무시하고 아래 4비트만 취하면 결과는 0000₂이 된다. 즉, 0010₂에 그 2의 보수 1110₂를 더하는 것은 0010에서 0010 자신을 빼는 것과 같은 의미를 가지며, 1110₂는 음수 -2를 나타낸다.

2의 보수를 이용하면 이진법으로 표현된 수(이진수)를 음의 정수에 대응시킬 수 있다. n자리 이진수 x와 그 보수 x_c는 다음 관계를 만족한다.

:$$$$

x + x_\mathrm{c} = 2^n

\quad(\iff

x_\mathrm{c} = 2^n - x

)\,.



거듭제곱 2ⁿ의 배수를 0과 동일시하면, 위의 보수 관계는 2ⁿ을 법으로 하는 합동식으로 바꿀 수 있다.

:$$$$

x + x_\mathrm{c} \equiv 0 \pmod {2^n} \,.



이는 x의 보수 x_c를 x의 역수 -x로 볼 수 있다는 것을 의미한다. 즉, 수 y에서 x를 빼는 연산은 수 y와 보수 x_c의 덧셈으로 바꿀 수 있다.

:$$$$

y - x

\equiv y + 2^n - x

\equiv y + x_\mathrm{c} \pmod {2^n} \,.



마찬가지로 역수 -x의 곱셈은 보수의 곱으로 바꿀 수 있다.

:$$$$

y \cdot (- x)

\equiv y \cdot 2^n + y \cdot (- x)

\equiv y \cdot x_\mathrm{c} \pmod {2^n} \,.



음수의 계산을 위해 0부터 2^''n''-1 - 1까지의 음이 아닌 정수를 일반적인 위치 기수법에서의 이진 표시로 대응시킨다.

: $$$$

\begin{align}

0 &\mapsto 0_2, \\

1 &\mapsto 1_2, \\

2 &\mapsto {10}_2, \\

& \;\; \vdots \\

2^{n-1}-2 &\mapsto

{011\cdots10}_2, \\

2^{n-1}-1 &\mapsto

\underbrace{011\cdots11}_{n \text{桁}}{}_{2}

\end{align}



이러한 수의 보수로서 음의 정수에 대한 2의 보수 표현을 얻을 수 있다.

: $$$$

\begin{alignat}{2}

2^{n-1} &\equiv -2^{n-1}

&&\mapsto {100 \cdots 00}_2, \\

2^{n-1} + 1 &\equiv 1 - 2^{n-1}

&&\mapsto {100 \cdots 01}_2, \\

& \;\; \vdots && \;\; \vdots \\

2^{n} - 2 &\equiv -2

&&\mapsto {111 \cdots 10}_2, \\

2^{n} - 1 &\equiv -1

&&\mapsto {111 \cdots 11}_2

\,.

\end{alignat}



n 자릿수의 이진수에서 k+1 자릿수 값을 b_k라고 하면, 2의 보수 표현은 다음과 같이 나타낼 수 있다.

: $$$$

{b_{n-1} b_{n-2} \cdots b_1 b_0}_{(2)}

\mapsto

• b_{n-1} \cdot 2^{n-1}

2의 보수 표현은 부호 비트가 0이면 부호 없는 정수 표현(일반적인 이진법)과 일치하며, n비트로 표현 가능한 수의 범위는 −2ⁿ⁻¹부터 2ⁿ⁻¹ − 1까지로, 음수 범위가 양수 범위보다 1만큼 커 비대칭적이다. 짝수/홀수 여부는 최하위 비트(LSB)로 판별하며, 양수/음수 판정은 최상위 비트만으로 가능하다.

2의 보수 표현에서 -1은 항상 모든 자릿값이 1인 이진수 111...11₂에 대응된다. 비트열 x와 그 비트를 반전시킨 비트열 ^fx는 다음을 만족한다.

: $$$$

x + {}^\mathrm{f}x \equiv -1 \pmod{2^n} \,.



x의 2의 보수는 ^cx = ^fx + 1로 나타낼 수 있으며, 비트 반전은 1의 보수를 얻는 연산이다.

: $$$$

{}^\mathrm{f}x

\equiv -1 - x

\equiv \left(2^n - 1\right) - x

\pmod{2^n} \,.



n비트 이진수 x의 하위 m-1 비트까지의 값이 0이었을 경우, 2의 보수를 구할 때 하위 M = min(m, n) 비트까지 원래 수와 2의 보수의 값이 일치하고, 나머지 상위 n-M 비트는 비트 반전의 상위 n-M 비트와 일치한다.

2⁴에 대한 2의 보수 표현에서 보수와 원래 수의 하위 비트 일치 예시는 다음과 같다.

10. 1. 부호 없는 정수와의 일치

10. 2. 최솟값과 최댓값의 비대칭성

10. 3. 짝수/홀수 판정