부호화된 숫자 표현

부호화된 숫자 표현(Signed number representations)은 컴퓨팅에서 사용되는 이진법에서 음수를 인코딩하기 위해 필요한 표현이다.

수학에서 음수는 모든 수 앞에 마이너스 기호("-")를 붙여서 표현한다. 그러나 컴퓨터 하드웨어에서 숫자는 어떠한 추가 기호 없이 비트 수열로만 표시된다. 이진법에서 부호가 들어간 숫자를 나타내도록 확장하는 가장 잘 알려진 4가지 방법은 부호 및 크기, 1의 보수, 2의 보수, 오프셋 이진법이다. 대체 방법 가운데 일부는 밑 -2를 사용하여 음수의 이진법과 같은 명시적인 부호 대신 암묵적인 기호를 사용한다. 해당 방법은 양수, 음수, 분수 또는 그러한 주제에 대한 다른 세부 사항에도 불구하고 다른 기초에 대해 고안될 수 있다.

그러한 어떤 표현도 보편적으로 우월하다는 결정적인 기준은 없다. 정수의 경우 유니시스 클리어패스 도라도 시리즈(Unisys ClearPath Dorado series)의 메인프레임은 2의 보수를 사용하지만 대부분의 최신 컴퓨팅 장치에 사용되는 표현은 2의 보수이다.

역사

디지털 컴퓨팅의 초창기에는 하드웨어 기술과 연산 기술(숫자 체계)에 관한 많은 경쟁적인 아이디어들이 있었다. 가장 큰 논쟁 가운데 하나는 음수의 형식이었는데 당대의 최고 전문가들 가운데 일부는 매우 강하고 다른 의견을 갖고 있었다. 한 캠프는 오늘날 지배적인 시스템인 2의 보수를 지지했다. 또 다른 캠프는 한 단어의 모든 비트를 뒤집어서 양의 값이 음의 등가물로 만들어지는 이들의 보수를 지지했다. 3번째 그룹은 단순히 단어의 부호(고차) 비트를 전환함으로써 값이 양의 값에서 음의 값으로 바뀌는 "부호 및 크기"를 지원했다.

각각의 시스템에 대한 찬반 논쟁이 있었다. 부호 및 크기는 작은 숫자 값이 1비트를 적게 사용하므로 메모리 덤프의 더 쉬운 추적(1960년대의 일반적인 프로세스)을 가능하게 한다. 내부적으로는 이 시스템이 1의 보수 계산을 수행했기 때문에 숫자가 레지스터에서 연산 유닛으로 전송될 때에 1의 보수로 변환되어야 했고 결과가 레지스터로 다시 전송될 때에 다시 부호 크기로 변환되어야 했다. 전자 제품은 다른 시스템보다 더 많은 게이트가 필요했다. 즉 이산 트랜지스터의 비용과 포장이 매우 중요한 관심사였다. IBM은 표지판 크기를 초기 지지한 사람들 가운데 하나였는데 704, 709, 709x 시리즈 컴퓨터는 아마도 그것을 사용하는 가장 잘 알려진 시스템일 것이다.

연산자를 주고받을 때에 값을 변환할 필요가 없었기 때문에 다소 단순한 하드웨어 설계가 가능했었다. 그러나 부호 크기(-0)와 함께 바람직하지 않은 특성을 공유하기도 했다. 음수 0은 양수 0과 정확히 비슷하게 동작한다. 어떤 계산에서든 피연산자로 사용될 때에 결과는 피연산자가 양수 0이든 음수 0이든 간에 동일할 것이다. 그러나 동일한 값의 두 형태가 존재하기 위해서는 0과의 동일성을 확인할 때 단일 비교가 아닌 2가지 형태가 필요하다는 것이 단점이다. 1의 보수 뺄셈은 또한 최종 차입을 초래할 수도 있다(아래 설명). 이것은 덧셈/뺄셈 논리를 더 복잡하게 만들거나, 뺄셈이 덧셈에 전달될 때에 단순히 2번째 피연산자의 비트를 뒤집어야 하기 때문에 더 단순하게 만든다고 주장할 수 있다. PDP-1, CDC 160 시리즈, CDC 3000 시리즈, CDC 6000 시리즈, UNIVAC 1100 시리즈, LINC 컴퓨터는 각각 보수를 사용한다.

2의 보수는 하드웨어에서 구현하기 가장 쉬웠는데 이것이 널리 광범위한 인기를 얻게 된 궁극적인 이유일 수도 있다.^[1] 초기 메인프레임의 프로세서는 종종 수천 개의 트랜지스터로 구성되었는데 많은 수의 트랜지스터를 제거하면서 비용을 크게 절감했다. IBM System/360, GE-600 시리즈, PDP-6, PDP-10과 같은 메인프레임은^[2] PDP-5, PDP-8, PDP-11 및 VAX와 같은 미니 컴퓨터처럼 2의 보수 연산 장치를 사용한다. 초기 집적 회로 기반 CPU(Intel 8080 등)의 설계자들은 2의 보수 연산(complemental math)을 사용하기로 결정했다. IC 기술이 발전함에 따라 사실상 모두 2의 보수 연산 기술을 채택했다. x86^[3], m68k, 파워 ISA^[4], MIPS, SPARC, ARM, Itanium, PA-RISC, DEC 알파 프로세서는 모두 2의 보수를 기반으로 하는 프로세서이다.

부호화된 크기 표시

이 표현은 "부호-크기" 또는 "부호 및 크기" 표현이라고도 한다. 이러한 접근법에서 숫자의 부호는 부호 비트로 표현된다: 부호 비트는 양수 또는 양수 0에 대해 비트(종종 가장 의미 있는 비트)를 0으로 설정하고 음수 또는 음수 0에 대해 1로 설정한다. 숫자의 나머지 비트는 크기(또는 절댓값)를 나타낸다. 예를 들어, 8비트 바이트에서는 7비트만 크기를 나타내며 0000000(0) ~ 1111111(127)의 범위를 지정할 수 있다. 따라서 부호 비트(8번째 비트)가 추가되면 -127₁₀부터 +127₁₀까지의 숫자를 나타낼 수 있다. 예를 들어 8비트 바이트로 인코딩된 -43₁₀은 10101011이고 43₁₀은 00101011이다. 부호화된 표현을 사용하면 구현이 더 복잡해지는 여러 가지 결과가 발생한다.^[5]

0을 나타내는 방법은 00000000 (0)과 10000000 (-0) 두 가지가 있다.
덧셈과 뺄셈은 부호 비트에 따라 다른 행동을 요구하는 반면 1의 보수는 부호 비트를 무시하고 순환 자리올림(end around carry)만 할 수 있고 2의 보수는 부호 비트를 무시하고 오버플로 동작에 의존할 수 있다.
비교 과정에서는 부호 비트를 검사해야 하는 반면 2의 보수에서는 단순히 2개의 숫자를 빼서 결과가 양수인지 음수인지 확인할 수 있다.
2의 보수에서 최소 음수는 -128이 아니라 -127이다.

이러한 접근 방식은 부호를 표시하는 일반적인 방법(숫자의 크기 앞에 "+" 또는 "-"를 배치함)과 직접 비교할 수 있다. 일부 초기 이진법 컴퓨터(예: IBM 7090)는 일반적인 사용법과의 자연스러운 관계 때문에 이 표현을 사용한다. 부호화된 크기는 유의값과 부동 소수점 값을 나타내는 가장 일반적인 방법이다.

1의 보수

8비트의 1의 보수
이진법 수	1의 보수 해석	부호화되지 않은 해석
00000000	+0	0
00000001	1	1
⋮	⋮	⋮
01111101	125	125
01111110	126	126
01111111	127	127
10000000	−127	128
10000001	−126	129
10000010	−125	130
⋮	⋮	⋮
11111101	−2	253
11111110	−1	254
11111111	−0	255

음수를 나타내는 과정에서는 1의 보수로 알려진^[6] 시스템을 사용할 수 있다. 이진법 음수의 보수는 비트 연산 NOT(bitwise NOT)으로 표현하는데 이는 이진법 양수를 "완성"하는 과정이다. 부호화된 크기 표시와 마찬가지로 1의 보수도 0: 00000000 (+0)과 11111111 (-0)의 2가지 표현을 갖고 있다.^[7]

예를 들어 00101011 (43₁₀)의 1의 보수는 11010100 (-43₁₀)이 된다. 1의 보수를 이용한 부호수의 범위(signed)는 −(2^N−1 − 1)에서 (2^N−1 − 1)까지와 ±0으로 나타낸다. 일반적인 8비트 바이트는 −127₁₀에서 +127₁₀까지이고 0은 00000000 (+0) 또는 11111111 (−0)이다.

이 시스템에 표시된 2가지 숫자를 추가하려면 기존의 이진법 추가 작업을 수행하지만 그 이후에는 순환 자리올림을 수행해야 한다. 즉 자리올림(carry)을 결과 합계에 다시 추가해야 한다.^[8] 이것이 필요한 이유를 보려면 -1 (11111110)을 +2 (00000010)에 추가한 경우를 보여주는 다음 예제를 고려해야 한다.

          이진법    십진법
        11111110     −1
     +  00000010     +2
     ───────────     ──
      1 00000000      0   ← 올바른 답이 아님
               1     +1   ← 자리올림 추가
     ───────────     ──
        00000001      1   ← 올바른 답

앞의 예에서 1번째 이진수 추가는 00000000을 제공하지만 올바른 답이 아니다. 올바른 결과(00000001)는 자리올림이 추가된 경우에만 나타난다.

용어에 대한 설명: 이 시스템은 "1의 보수"라고 부르는데 이는 양수 x(x의 비트 단위 NOT으로 표시)의 부정이 하나의 긴 수열인 0의 보수 표현(-0)에서 x를 빼서 형성될 수 있기 때문이다. 반면 2의 보수 연산은 +0에 해당하는 2개의 큰 검정력에서 x를 빼서 x의 부정을 형성한다.^[9] 따라서 1의 보수와 2의 보수 표현은 각각 다르다.

음수에 대한 이들의 보수 표현은 단순히 크기를 비트 단위 보수로 바꾸는 것만으로도 부호 크기 표현에서 얻을 수 있다는 점에 유의한다. 예를 들어 부호 크기 11111101을 나타내는 소수점 -125는 1의 보수인 10000010으로 표현할 수 있다.

2의 보수

8비트의 2의 보수
이진법 수	2의 보수 해석	부호화되지 않은 해석
00000000	0	0
00000001	1	1
⋮	⋮	⋮
01111110	126	126
01111111	127	127
10000000	−128	128
10000001	−127	129
10000010	−126	130
⋮	⋮	⋮
11111110	−2	254
11111111	−1	255

2의 보수에는 0이 하나만 있으며 00000000으로 표시된다. 숫자를 부정하는 것은(음수든 양수든) 모든 비트를 뒤집어서 나온 결과에 하나를 추가하는 방식으로 수행된다.^[10] 이는 실제로 모든 정수의 모듈 2^N의 환 구조를 반영한다: $\mathbb {Z} /2^{N}\mathbb {Z}$ . 2의 보수의 쌍을 추가하는 것은 부호가 없는 숫자의 쌍을 추가하는 것과 같다(만약 그것이 이루어진다면 오버플로의 탐지는 제외한다). 뺄셈이나 N개의 가장 낮은 유형의 비트(곱셈의 값)에 대해서도 같다. 예를 들어 127과 -128에 2의 보수를 더하는 것은 8비트의 2의 보수 표에서 볼 수 있듯이 부호가 없는 127과 128을 더하는 것과 같은 이진 비트 패턴을 제공한다.

2의 보수로 숫자의 부정을 얻는 더 쉬운 방법은 다음과 같다.

	예 1	예 2
1. 오른쪽에서 첫 번째 "1"을 찾음	00101001	00101100
2. 모든 비트를 해당 "1"의 왼쪽으로 반전시킴	11010111	11010100

방법 2:

숫자를 통해 모든 비트를 반전한다.
1을 추가한다.

예: 이진수가 00000010인 +2의 경우( ~ 문자는 C의 비트 연산 과정에서 NOT 연산자를 사용하기 때문에 ~ X는 "X의 모든 비트를 반전시킴"을 의미한다).

~00000010 → 11111101
11111101 + 1 → 111110 (-2는 2의 보수이다)

오프셋 이진법

8비트의 128 초과
이진법 수	128 초과의 해석	부호화되지 않은 해석
00000000	−128	0
00000001	−127	1
⋮	⋮	⋮
01111111	−1	127
10000000	0	128
10000001	1	129
⋮	⋮	⋮
11111111	+127	255

"K 초과"(excess-K) 또는 "편향된 표현"이라고도 하는 오프셋 이진법은 사전에 지정된 숫자 K를 편향된 값으로 사용한다. 값은 의도된 값보다 큰 부호가 없는 숫자로 표시된다. 따라서 0은 K로 표시되고 -K는 0인 비트 패턴으로 표시된다. 이는 앞에서 언급한 2의 보수를 약간 수정하고 일반화한 것으로 볼 수 있는데 이는 사실상 가장 중요한 비트가 부정된 초과(excess-(2^N−1)) 표현이다.

편향된 표현은 이제 주로 부동소수점 숫자의 지수에 사용된다. IEEE 754 부동소수점 표준은 단일 정밀도(32비트) 숫자의 지수(exponent) 부분을 8비트의 127 초과(excess-127) 필드로 정의한다. 이중 정밀도(64비트) 지수 부분은 11비트의 1023 초과(excess-1023) 부분이 된다. 또한 이진 코드 십진수에는 3 초과 부호(excess-3)가 사용되었다.

밑 -2

기존의 이진법 시스템에서 밑(radix)은 2이다. 따라서 가장 오른쪽에 있는 비트는 2⁰, 다음 비트는 2¹, 그 다음 비트는 2² 등을 나타낸다. 그러나 기본값이 -2인 이진법 시스템도 사용할 수 있는데 맨 오른쪽에 있는 비트는 (-2)⁰ = +1, 다음 비트는 (-2)¹ = -2, 다음 비트는 (-2)² = +4 등을 나타내면서 번갈아 표시한다. 4비트로 나타낼 수 있는 숫자는 아래의 비교 표에 나와 있다.

나타낼 수 있는 숫자의 범위는 비대칭이다. 만약 단어가 짝수 비트를 갖고 있다면 나타낼 수 있는 가장 큰 음수의 크기는 나타낼 수 있는 가장 큰 양수의 2배이고 그 반대의 경우는 홀수 비트를 갖고 있다.

대조표

다음 표는 4비트를 사용하여 표현할 수 있는 양의 정수와 음의 정수를 보여준다.

4비트 정수 표현
소수	부호화되지 않음	부호 및 크기	1의 보수	2의 보수	8 초과 (편향)	밑 -2
+16	빈칸	빈칸	빈칸	빈칸	빈칸	빈칸
+15	1111	빈칸	빈칸	빈칸	빈칸	빈칸
+14	1110	빈칸	빈칸	빈칸	빈칸	빈칸
+13	1101	빈칸	빈칸	빈칸	빈칸	빈칸
+12	1100	빈칸	빈칸	빈칸	빈칸	빈칸
+11	1011	빈칸	빈칸	빈칸	빈칸	빈칸
+10	1010	빈칸	빈칸	빈칸	빈칸	빈칸
+9	1001	빈칸	빈칸	빈칸	빈칸	빈칸
+8	1000	빈칸	빈칸	빈칸	빈칸	빈칸
+7	0111	0111	0111	0111	1111	빈칸
+6	0110	0110	0110	0110	1110	빈칸
+5	0101	0101	0101	0101	1101	0101
+4	0100	0100	0100	0100	1100	0100
+3	0011	0011	0011	0011	1011	0111
+2	0010	0010	0010	0010	1010	0110
+1	0001	0001	0001	0001	1001	0001
+0	0000	0000	0000	0000	1000	0000
−0	0000	1000	1111	0000	1000	0000
−1	빈칸	1001	1110	1111	0111	0011
−2	빈칸	1010	1101	1110	0110	0010
−3	빈칸	1011	1100	1101	0101	1101
−4	빈칸	1100	1011	1100	0100	1100
−5	빈칸	1101	1010	1011	0011	1111
−6	빈칸	1110	1001	1010	0010	1110
−7	빈칸	1111	1000	1001	0001	1001
−8	빈칸	빈칸	빈칸	1000	0000	1000
−9	빈칸	빈칸	빈칸	빈칸	빈칸	1011
−10	빈칸	빈칸	빈칸	빈칸	빈칸	1010
−11	빈칸	빈칸	빈칸	빈칸	빈칸	빈칸

같은 표인 "이러한 이진 비트가 주어지면 표현 시스템에서 해석한 숫자는 무엇인가?"에서 볼 수 있다.

이진수	부호화되지 않음	부호 및 크기	1의 보수	2의 보수	8 초과	밑 −2
0000	0	0	0	0	−8	0
0001	1	1	1	1	−7	1
0010	2	2	2	2	−6	−2
0011	3	3	3	3	−5	−1
0100	4	4	4	4	−4	4
0101	5	5	5	5	−3	5
0110	6	6	6	6	−2	2
0111	7	7	7	7	−1	3
1000	8	−0	−7	−8	0	−8
1001	9	−1	−6	−7	1	−7
1010	10	−2	−5	−6	2	−10
1011	11	−3	−4	−5	3	−9
1100	12	−4	−3	−4	4	−4
1101	13	−5	−2	−3	5	−3
1110	14	−6	−1	−2	6	−6
1111	15	−7	−0	−1	7	−5

그 외의 시스템

구글의 프로토콜 버퍼인 "지그재그 인코딩"(zig-zag encoding)은 부호 및 크기와 유사한 시스템이지만 부호 표현에 가장 덜 중요한 비트를 사용하며 단일 표현은 0이다. 이를 통해 부호가 없는 정수를 위한 가변 길이 수량 인코딩을 부호가 있는 정수에 효율적으로 사용할 수 있다.^[11]

또다른 접근 방식은 각 숫자마다 부호를 부여하여 부호가 있는 숫자 표현을 제공하는 것이다. 예를 들어 존 콜슨(John Colson)은 1726년에 1, 2, 3, 4, 5를 사용하여 "작은 숫자" 표현을 줄이는 것을 주장했다. 1840년에는 오귀스탱 루이 코시(Augustin Louis Cauchy)가 계산 오류를 줄이기 위해 수정된 십진수에 대한 선호를 표명했다.

같이 보기

각주

↑ Hunsoo, Choo; Muhammad, K.; Roy, K. (2003년 2월). “Two's complement computation sharing multiplier and its applications to high performance DFE”. 《IEEE Transactions on Signal Processing》 51 (2): 458-469. doi:10.1109/TSP.2002.806984.
↑ 《GE-625 / 635 Programming Reference Manual》. General Electric. 1966년 1월. 2013년 8월 15일에 확인함.
↑ 〈Section 4.2.1〉. 《Intel 64 and IA-32 Architectures Software Developer’s Manual》 (PDF). Intel. 2013년 8월 6일에 확인함.
↑ 〈Section 1.4〉. 《Power ISA Version 2.07》. Power.org. 2014년 1월 9일에 원본 문서에서 보존된 문서. 2013년 8월 6일에 확인함.
↑ Bacon, Jason W. (2010년–2011년). “Computer Science 315 Lecture Notes”. 2020년 2월 14일에 원본 문서에서 보존된 문서. 2020년 2월 21일에 확인함.
↑ “Array multiplier operating in one's complement format (1의 보수 형식으로 작동하는 어레이 승수, 미국 특허 제4484301호)”. 1981년 3월 10일.
↑ “One's complement cryptographic combiner (1의 보수 암호 결합기, 미국 특허 제6760440호)”. 1999년 12월 11일.
↑ Shedletsky, John J. (1977년). “Comment on the Sequential and Indeterminate Behavior of an End-Around-Carry Adder” (PDF). 《IEEE Transactions on Computers》 26 (3): 271-272. doi:10.1109/TC.1977.1674817.
↑ Donald Knuth: The Art of Computer Programming, Volume 2: Seminumerical Algorithms, chapter 4.1
↑ Thomas Finley (2000년 4월). “Two's Complement”. Cornell University. 2015년 9월 15일에 확인함.
↑ Protocol Buffers: Signed Integers

[1] Hunsoo, Choo; Muhammad, K.; Roy, K. (2003년 2월). “Two's complement computation sharing multiplier and its applications to high performance DFE”. 《IEEE Transactions on Signal Processing》 51 (2): 458-469. doi:10.1109/TSP.2002.806984.

[2] 《GE-625 / 635 Programming Reference Manual》. General Electric. 1966년 1월. 2013년 8월 15일에 확인함.

[3] 〈Section 4.2.1〉. 《Intel 64 and IA-32 Architectures Software Developer’s Manual》 (PDF). Intel. 2013년 8월 6일에 확인함.

[4] 〈Section 1.4〉. 《Power ISA Version 2.07》. Power.org. 2014년 1월 9일에 원본 문서에서 보존된 문서. 2013년 8월 6일에 확인함.

[cs315-5] Bacon, Jason W. (2010년–2011년). “Computer Science 315 Lecture Notes”. 2020년 2월 14일에 원본 문서에서 보존된 문서. 2020년 2월 21일에 확인함.

[6] “Array multiplier operating in one's complement format (1의 보수 형식으로 작동하는 어레이 승수, 미국 특허 제4484301호)”. 1981년 3월 10일.

[7] “One's complement cryptographic combiner (1의 보수 암호 결합기, 미국 특허 제6760440호)”. 1999년 12월 11일.

[8] Shedletsky, John J. (1977년). “Comment on the Sequential and Indeterminate Behavior of an End-Around-Carry Adder” (PDF). 《IEEE Transactions on Computers》 26 (3): 271-272. doi:10.1109/TC.1977.1674817.

[9] Donald Knuth: The Art of Computer Programming, Volume 2: Seminumerical Algorithms, chapter 4.1

[10] Thomas Finley (2000년 4월). “Two's Complement”. Cornell University. 2015년 9월 15일에 확인함.

[11] Protocol Buffers: Signed Integers

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]