투의 보어

2의 보법은 컴퓨터에서 부호화된(양, 음수, 0) 정수를 표현하는 가장 일반적인 방법이며,^[1] 더 일반적으로는 고정 소수점 이진 값입니다. 2의 보어는 가장 큰 자리 값을 가진 이진 숫자를 기호로 사용하여 이진 숫자가 양수인지 음수인지 나타냅니다. 가장 중요한 비트가 1이면 숫자는 음수로 서명되고 가장 중요한 비트가 0이면 숫자는 양수로 서명됩니다.

둘의 보완 체계와 달리 둘의 보완 체계는 0에 대한 표현이 하나뿐입니다. 또한 산술 구현은 부호 없는 정수뿐만^[2] 아니라 부호 없는 정수에서도 사용할 수 있으며 정수 오버플로우 상황에서만 다릅니다.

절차.

두 정수의 여집합은 다음과 같이 계산됩니다.

• 1단계: 선두 비트가 부호 비트인 숫자의 이진법 표현으로 시작합니다.
• 2단계: 모든 비트를 반전(또는 반전) - 0에서 1까지, 1에서 0까지 바꿉니다.
• 3단계: 오버플로우를 무시하고 전체 반전 숫자에 1을 더합니다. 오버플로우에 대한 회계 처리는 결과에 대한 잘못된 값을 생성합니다.

예를 들어 숫자 6에서 이진법으로 10진수 -6을 계산하는 방법은 다음과 같습니다.

• 1단계: 10진수에서 +6은 이진수에서 0110이고, 가장 왼쪽에 있는 비트(첫 번째 0)는 부호입니다(진수에서 110만 소수에서 -2가 됩니다).
• 2단계: 0110에서 모든 비트를 뒤집어서 1001을 줍니다.
• 3단계: 1010을 부여하는 플립된 숫자 1001에 자릿값 1을 더합니다.

1010이 실제로 -6의 값을 갖는지 확인하려면 자리 값을 함께 추가하되 최종 계산에서 부호 값을 빼십시오. 부호값이 가장 큰 값이므로 이를 빼야 정확한 결과가 나옵니다. 1010 = -(1×2) + (0×2) + (1×2) + (0×2) = 1×-8 + 0 + 1×2 + 0 = -6입니다.

2단계와 3단계는 입력과 출력이 모두 2의 보형 형식인$$ 임의의 (양의) 정수 $n{\displaystyle }$ ${\displaystyle n}$의 가산$$ 역${\displaystyle n}$ ${\displaystyle -n}$을 계산하는 유효한 방법입니다. ${\displaystyle -n}$을 계산하는 대안은 $뺄셈{\displaystyle \mathrm{}0}$ - n$${\$displaystyle 0-n$}을 사용하는$$ 것입니다$.$ 2의 보형 형식에서 정수를 뺄셈은 아래를 참조하십시오.

이론.

Two의 보어는 기수 보어의 한 예입니다. 이름의 '2'는 N-비트 시스템에서 완전히 확장된 용어로 실제로는 "N의 거듭제곱에 2" - 2를 나타냅니다(이 용어에서 정확히 '2'가 생성되는 유일한 경우는 N = 1이므로 1-비트 시스템의 경우에는 부호와 0 모두에 대한 용량이 없습니다). 그리고 보완이 계산되는 것은 이 전체 기간뿐입니다. 따라서 N-비트 수에 대한 둘의 보형물에 대한 정확한 정의는 2에^N 대한 N-비트 수에 대한 보형물입니다.

2에^N 대한 수에 대한 보어의 정의적 성질은 단순히 이 수와 원래 생산물 2의^N 합을 합한 것입니다. 예를 들어, 최대 3비트(즉, N = 3 및 2 = 2 = 8 = 1000)의 이진수를 사용하는 경우, 숫자 3(011)에 대한 2의 보체는 5(101)입니다. 왜냐하면 원래를 합하면 2 = 1000 = 011 + 101을 제공하기 때문입니다. 이 대응이 음수를 표현하는 데 사용되는 경우, 10진수와 숫자 공간을 유사하게 사용하고 8개의 음수가 아닌 숫자 0~7만 허용하는 숫자 공간을 사용하여 숫자 공간을 두 세트로 나누는 것을 효과적으로 의미합니다: 숫자 0 1 2 3 중 처음 4개는 동일하게 유지되고 나머지 4개는 음수를 인코딩합니다. 증가하는 순서를 유지하므로 4 인코딩 -4, 5 인코딩 -3, 6 인코딩 -2 및 7 인코딩 -1을 만듭니다. 그러나 이진 표현은 가장 중요한 비트가 그룹(및 부호)을 나타내기 때문에 추가적인 유용성을 갖습니다. 첫 번째 그룹의 비음수는 0이고 두 번째 그룹의 음수는 1입니다. 오른쪽 표는 이 특성을 보여줍니다.

이진수 2의 양수의 보수를 계산한다는 것은 본질적으로 2에서^N 숫자를 뺀다는 것을 의미합니다. 그러나 3비트 예제와 4비트 1000₂(2³)에서 볼 수 있듯이, 숫자^N 2는 N비트 공간 밖에 있기 때문에 N비트로 제한된 시스템에서 그 자체로 표현할 수 없습니다(그럼에도 불구하고 숫자는 N비트 시스템에서 "2' 보완"의 기준점입니다). 이 때문에 최대 N비트를 가진 시스템은 감산을 두 가지 연산으로 구분해야 합니다: 먼저 N비트 시스템에서 최대 수를 뺀 값, 즉 2-1입니다^N. (이진법에서 이 용어는 실제로 '모든 1'로 구성된 단순한 수이다.) 비트와이즈 NOT 연산이라고도 알려진 숫자의 모든 비트를 반전시킨 다음 비트를 추가하면 간단히 이를 뺄 수 있습니다. 공교롭게도, 하나를 더하기 전의 중간 숫자는 컴퓨터 과학에서도 부호수 표현의 또 다른 방법으로 사용되며, 원의 보어(이러한 숫자를 원본과 합하면 '모든 1'이 나오기 때문에 명명됨)라고 불립니다.

부호화된 숫자를 표현하는 다른 시스템(예: 자신의 보형)과 비교하여, 양자의 보형은 기본적인 산술 연산인 덧셈, 뺄셈, 곱셈이 부호화되지 않은 이진수의 연산과 동일하다는 장점이 있습니다(입력이 출력과 동일한 수의 비트로 표현되는 한, 해당 비트를 초과하는 오버플로는 결과에서 삭제됩니다. 이 속성은 특히 고정밀 산술의 경우 시스템 구현을 더 쉽게 해줍니다. 또한 자신의 보체계와 달리 두 개의 보체계는 음의 0에 대한 표현이 없기 때문에 그와 관련된 어려움을 겪지 않습니다. 그렇지 않으면 두 체계 모두 이진 표현의 보표를 사용하여 정수의 부호를 되돌릴 수 있는 원하는 속성을 갖지만 표에서 볼 수 있듯이 두 개의 보표에는 가장 낮은 음수인 예외가 있습니다.^[3]

역사

보법은 십진법 덧셈 기계와 기계 계산기에서 뺄셈을 수행하는 데 오랫동안 사용되었습니다. 존 폰 노이만(John von Neumann)은 1945년 전자 저장 프로그램 디지털 컴퓨터에 대한 EDVAC 제안에 대한 보고서의 첫 번째 초안에서 두 개의 보완 이진 표현을 사용할 것을 제안했습니다.^[4] 1949년 제1차 초안에서 영감을 얻은 EDSAC는 음의 이진수라는 두 개의 보표를 사용했습니다.

CDC 6600, LINC, PDP-1, UNIVAC 1107 등 많은 초기 컴퓨터가 자신의 보표기를 사용하고 있으며, UNIVAC 1107의 후손인 UNIVAC 1100/2200 시리즈도 계속 사용하고 있습니다. IBM 700/7000 시리즈 과학 기계는 두 개의 보체인 인덱스 레지스터를 제외하고 기호/크기 표기법을 사용합니다. 음의 값을 두 개의 보형 형태로 저장하는 초기 상용 컴퓨터에는 English Electric DUCE(1955)와 Digital Equipment Corporation PDP-5(1963)와 PDP-6(1964)이 있습니다. 1964년 당시 컴퓨터 업계의 선두 주자였던 IBM이 도입한 System/360은 컴퓨터 업계에서 가장 널리 사용되는 이진법 표현으로 2의 보어를 만들었습니다. 최초의 미니 컴퓨터인 PDP-8은 1969년의 데이터 제너럴 노바, 1970년의 PDP-11, 그리고 거의 모든 후속 미니 컴퓨터와 마이크로 컴퓨터와 마찬가지로 두 개의 상보 연산을 사용합니다.

두 개의 보표에서 변환

2'-보완수 시스템은 양수와 음수를 이진수 표현으로 인코딩합니다. 각 비트의 가중치는 가장 중요한 비트를 제외하고 2의 거듭제곱이며, 그 가중치는 2의 해당 거듭제곱의 음수입니다.

${\displaystyle {N비트}_{}}$ 정수 ${\displaystyle {}_{}{}_{}{}_{}{N}_{}}$- ${\displaystyle 1_{}}$a ${\displaystyle {N\mathrm{}}_{}}$ -$$2 … 0 {\$display a_{N-1}a_{N-2$}\$dots$ a_${0}$의 값 w는 다음 공식으로 주어집니다$$.

${\displaystyle w=-a_{N-1}2^{N-1}+\sum _{i=0}^{N-2}a_{i}2^{i}}$

가장 중요한 비트는 숫자의 부호를 결정하며 때때로 부호 비트라고 불립니다. 부호 비트는 부호 및 크기 표현과 달리 위에 표시된 가중치 -(2^{N − 1})도 있습니다. N비트를 사용하면 -(2^{N − 1})부터^{N − 1} 2 - 1까지의 모든 정수를 나타낼 수 있습니다.

2개의 보완 표현으로 변환

2의 보표식에서 음수가 아닌 숫자는 일반적인 이진법으로 표시되며, 이 경우 가장 중요한 비트는 0입니다. 그러나 표시되는 숫자의 범위가 부호 없는 이진수와 같지 않습니다. 예를 들어, 8비트의 부호 없는 숫자는 0~255(111111)의 값을 나타낼 수 있습니다. 그러나 가장 중요한 비트가 '1'인 나머지 비트 조합은 -1에서 -128까지의 음의 정수를 나타내기 때문에 2의 보체 8비트 수는 0에서 127까지의 음이 아닌 정수만 나타낼 수 있습니다(01111111).

두 사람의 보연산은 덧셈 역연산이므로 음수는 두 사람의 절대값의 보연산으로 표현됩니다.

그들의 보필로

음의 이진수에 대한 두 개의 보표를 얻기 위해 비트와이즈 NOT 연산을 사용하여 모든 비트를 반전시키거나 "플립"합니다. 그런 다음 1의 값이 결과 값에 추가되어 두 개의 보표를 0으로 취할 때 발생하는 오버플로를 무시합니다.

예를 들어 1바이트(=8비트)를 사용하면 10진수 5는 다음과 같이 표시됩니다.

0000 0101₂

가장 중요한 비트(이 경우 가장 왼쪽 비트)는 0이므로 패턴은 음수가 아닌 값을 나타냅니다. 2's-complement 표기법에서 -5로 변환하려면 먼저 모든 비트가 반전됩니다. 즉, 0은 1이 되고 1은 0이 됩니다.

1111 1010₂

여기서 표현은 십진법 값 -5를 보완한 것입니다. 두 개의 여집합을 얻기 위해 결과에 1을 더하면 다음과 같습니다.

1111 1011₂

결과는 십진법 값 -5를 2's-complement 형태로 나타내는 부호화된 이진수입니다. 가장 중요한 비트는 1이므로 표시된 값은 음수입니다.

두 사람의 음수의 여집합은 가장 음수가 많은 특별한 경우를 제외하고는 그에 상응하는 양수입니다. 예를 들어, -5(위)의 비트를 반전하면 다음과 같은 결과를 얻을 수 있습니다.

0000 0100₂

그리고 하나를 더하면 최종 값을 얻을 수 있습니다.

0000 0101₂

마찬가지로, 두 개의 보형물 0은 0입니다. 반전하면 모든 것이 주어지고, 하나를 더하면 0이 됩니다(오버플로우가 무시되므로).

가장 부정적인 숫자(예를 들어, 가장 중요한 비트로서 하나와 다른 모든 비트 0으로서)를 나타내는 둘의 보완은 그 자체입니다. 따라서 2의 보어가 음수를 제공하지 않는 '추가' 음수가 있습니다. 아래의 § 대부분의 음수를 참조하십시오.

2에서^N 빼기

숫자와 그것의 보어의 합은 (부호가 없는 이진수로 읽기) 2^N - 1인 모든 1비트를 가진 N비트 단어입니다. 그런 다음 두 개의 보어에 숫자를 추가하면 N개의 가장 낮은 비트가 0으로 설정되고 운반 비트가 1로 설정되며 후자는 (부호 없는 이진수로 읽음) 2의^N 가중치를 갖습니다. 따라서 부호가 없는 이진 산술에서 양수 x의 2'-comple 음수 x*의 값은 동등 x* = 2 - x를 만족합니다.

예를 들어 -5의 4비트 표현을 찾는 방법은 다음과 같습니다(부제는 표현의 기본을 나타냅니다).

x = 5 따라서 x = 0101

따라서 N = 4인 경우:

x* = 2^N − x = 2⁴ − 5₁₀ = 16₁₀ - 5₁₀ = 10000₂ − 0101₂ = 1011₂

계산은 완전히 베이스 10에서 수행할 수 있으며, 마지막에 베이스 2로 변환됩니다.

x* = 2^N − x = 2⁴ − 5₁₀ = 11₁₀ = 1011₂

LSB에서 MSB 방향으로 작업

이진수를 두 개의 보체로 수동 변환하는 바로 가기는 LSB(최소 유효 비트)를 시작하고 모든 0을 복사하여 첫 번째 1에 도달할 때까지 LSB에서 가장 유효 비트(MSB)로 작업한 다음 1을 복사하는 것입니다. 나머지 비트를 모두 뒤집습니다(초기 숫자가 부호와 크기로 표시된 경우 MSB를 1로 유지합니다). 이 바로 가기를 사용하면 사람이 먼저 보완을 구성하지 않고 숫자를 두 개의 보완으로 변환할 수 있습니다. 예를 들어, 두 개의 보표에서 "0011 1100"의 음수는 "1100100"이며, 밑줄 친 숫자는 복사 작업에 의해 변경되지 않았습니다(다른 숫자는 뒤집었습니다).

컴퓨터 회로에서 이 방법은 "보완하고 하나를 더하는" 방법보다 빠르지 않습니다. 두 방법 모두 논리 변화를 전파하면서 오른쪽에서 왼쪽으로 순차적으로 작업해야 합니다. 하나를 보완하고 추가하는 방법은 표준 캐리 룩-어헤드 가산기 회로를 통해 속도를 높일 수 있고, LSB에서 MSB로 향하는 방법도 유사한 논리 변환을 통해 속도를 높일 수 있습니다.

부호확장

일정한 비트 수를 가진 두 개의 보완 숫자를 비트 수가 더 많은 숫자로 변환할 때(예: 1바이트 변수에서 2바이트 변수로 복사할 때), 가장 중요한 비트는 모든 추가 비트에서 반복되어야 합니다. 일부 프로세서는 단일 명령어로 이 작업을 수행합니다. 다른 프로세서에서는 관련 비트나 바이트를 설정하기 위해 코드 뒤에 조건을 사용해야 합니다.

마찬가지로 숫자가 오른쪽으로 이동할 때 부호 정보를 포함하는 가장 중요한 비트를 유지해야 합니다. 그러나 왼쪽으로 이동하면 약간의 이동이 발생합니다. 이러한 규칙은 왼쪽 시프트에 숫자를 두 배로 곱하고 오른쪽 시프트에 숫자를 두 배로 나누는 일반적인 의미론을 유지합니다. 그러나 가장 중요한 비트가 0에서 1로 변경될 경우(그리고 그 반대의 경우) 값이 부호화된 정수를 나타내는 경우 오버플로가 발생한다고 합니다.

일부 곱셈 알고리즘에서는 정확도를 이동하고 두 배로 늘리는 것이 모두 중요합니다. 덧셈과 뺄셈과는 달리 부호와 부호 없는 숫자에 대해 너비 확장과 오른쪽 시프트가 다르게 수행된다는 점에 유의하십시오.

가장 큰 음수

단 하나의 예외를 제외하고 모든 비트를 뒤집고 1을 더하면 두 개의 보완 표현이 얻어집니다. 양수 12는 음수 12, 양수 5는 음수 5, 0은 0(+과류)이 됩니다.

범위 내의 최소 수에 대한 두 개의 보형물(음)을 취하는 것은 수를 음화하는 데 원하는 효과를 발휘하지 못할 것입니다. 예를 들어, 8비트 시스템에서 -128이라는 두 개의 보수는 오른쪽 표와 같이 -128입니다. -128을 부정하는 것에서 예상되는 결과는 +128이지만, 8비트 2의 보체계로 +128의 표현이 없으므로 부정을 표현하는 것은 사실상 불가능합니다. 두 개의 보어가 동일한 숫자인 경우 가장 중요한 비트에 이월이 있었지만 제외되지 않았기 때문에 오버플로 조건으로 탐지됩니다.

0이 아닌 수를 자신의 부정과 동일하게 갖는 것은 0이 자신의 부정이고, 전체 수가 짝수라는 사실에 의해 강요됩니다. 증명: 0이 아닌 숫자(홀수)가 2^n - 1개 있습니다. 부정하면 0이 아닌 숫자를 크기 2의 집합으로 분할하지만 0이 아닌 숫자의 집합은 카디널리티가 균등하게 됩니다. 따라서 집합들 중 적어도 하나는 크기가 1입니다. 즉, 0이 아닌 숫자는 자신의 음수입니다.

가장 큰 음수가 있으면 예기치 않은 프로그래밍 버그가 발생할 수 있으며 결과에 예기치 않은 징후가 있거나 예기치 않은 오버플로 예외가 발생하거나 완전히 이상한 동작이 발생할 수 있습니다. 예를들면,

• 1차 부정 연산자는 0이 아닌 숫자의 부호를 변경하지 않을 수 있습니다. 예를 들어 -(-128) ⟼ -128(여기서 "⟼"는 "becomes"로 읽힙니다).

• 절대값의 구현은 음수를 반환할 수 있습니다. 예를 들어, abs (-128) ⟼ -128.

• 마찬가지로 -1 곱셈도 예상대로 작동하지 않을 수 있습니다. 예를 들어 (-128) × (-1) ⟼ -128입니다.

• -1로 나누면 예외가 발생할 수 있습니다(예: 0으로 나누면 발생). 나머지(또는 모듈로)를 -1로 계산해도 이 예외가 발생할 수 있습니다(예: (-128) ÷(-1) ⟼ [CRASH], (-128) %(-1) ⟼ [CRASH]).

C와 C++ 프로그래밍 언어에서 위의 동작은 정의되지 않고 이상한 결과를 반환할 수 있을 뿐만 아니라 컴파일러는 프로그래머가 정의되지 않은 수치 연산이 발생하지 않도록 보장했다고 자유롭게 가정하고 그 가정에서 추론합니다.^[7] 이는 여러 최적화를 가능하게 하지만 이러한 정의되지 않은 계산으로 프로그램에 이상한 버그가 많이 발생합니다.

2의 보어에서 가장 음수인 이 숫자는 "이상한 숫자"라고 불리기도 하는데, 이것이 유일한 예외이기 때문입니다.^[8][9] 숫자는 예외이지만, 일반적인 두 개의 보체계에서 유효한 숫자입니다. 모든 산술 연산은 피연산자로서 그리고 (오버플로우가 없는 경우) 결과로서 모두 작동합니다.

작동하는 이유

가능한 모든 N비트 값의 집합이 주어졌을 때, 우리는 (이진값으로) 하위 절반을 0에서 (2^{N − 1} - 1)까지의 정수로, 상위 절반을^{N − 1} -2에서 -1까지의 정수로 할당할 수 있습니다. 위 절반(다시 이진 값으로)은 -2에서^{N − 1} -1까지의 음의 정수를 나타내는 데 사용할 수 있습니다. 왜냐하면 모듈로^N 2를 더하면 음의 정수와 같은 방식으로 동작하기 때문입니다. 즉, i + j mod 2 = i + (j + 2) mod 2이므로 집합 {j + k 2 k는 정수 } 이므로 j 대신 사용할 수 있습니다.

예를 들어, 8비트의 부호 없는 바이트는 0에서 255입니다. 상단 절반(128~255)에서 256을 빼면 부호화된 바이트가 -128~-1이 됩니다.

둘의 보체에 대한 관계는 256 = 255 + 1, 그리고 (255 - x)가 둘의 x의 보체라는 것을 주목함으로써 실현됩니다.

예

이 하위 섹션에서는 십진 숫자에 소수점 ""로 접미사를 붙입니다.

예를 들어, (2 = 128.) -95. modulo 256. 이므로 8비트 숫자는 -128.부터 127.까지의 모든 정수만을 나타낼 수 있습니다. -95. modulo 256. 이므로,

−95. + 256.

= −95. + 255. + 1

= 255. − 95. + 1

= 160. + 1.

= 161.

   1111 1111                       255.  − 0101 1111                     −  95.  ===========                     ===== 1000000 (1명의 보조사) 160. + 1 + 1 =========== ===== 100000001 (2명의 보조사) 161. 

기본적으로, 이 시스템은 뒤로 계산하고 감싸서 음의 정수를 나타냅니다. 양수와 음수의 경계는 임의적이지만, 관례에 따라 모든 음수는 1의 왼쪽 끝 비트(가장 중요한 비트)를 가집니다. 따라서 가장 양의 4비트 수는 0111(7.)이고 가장 음의 수는 1000(-8.)입니다. 가장 왼쪽에 있는 비트를 부호 비트로 사용하기 때문에 가장 큰 음수(-8. = 8.)의 절대값이 너무 커서 나타낼 수 없습니다. 두 개의 보체 번호를 부정하는 것은 간단합니다. 모든 비트를 뒤집고 결과에 하나를 더합니다. 예를 들어, 1111을 음수로 하면 0000 + 1 = 1이 됩니다. 따라서 이진법의 1111은 10진법으로 -1을 나타내야 합니다.^[11]

이 시스템은 컴퓨터 하드웨어의 산술 구현을 단순화하는 데 유용합니다. 처음에 1111(-1.)에 0011(3.)을 더하면 10010이라는 오답이 나오는 것 같습니다. 그러나 하드웨어는 맨 왼쪽 비트를 무시하여 0010(2.)이라는 정답을 제시할 수 있습니다. 0100 및 0100 합계와 같은 작업을 잡으려면 오버플로 검사가 여전히 존재해야 합니다.

따라서 이 시스템은 뺄셈 회로나 숫자의 부호를 감지하는 회로 없이 음의 피연산자를 추가할 수 있습니다. 또한 이 덧셈 회로는 추가 주기나 자체 덧셈 회로만 있으면 되는 두 개의 수를 보함으로써 뺄셈도 수행할 수 있습니다(아래 참조). 이를 수행하기 위해 회로는 단지 1의 왼쪽 끝 비트가 있는 것처럼 작동합니다.

산술연산

추가

피연산자의 부호가 반대인 경우에도 두 개의 보수를 더하면 특별한 처리가 필요하지 않습니다. 결과의 부호는 자동으로 결정됩니다. 예를 들어 15와 -5를 더하면 다음과 같습니다.

   0000 1111  (15)  + 1111 1011  (−5)  ===========    0000 1010  (10) 

또는 5 - 15 = 5 + (-15)의 계산:

   0000 0101  (  5)  + 1111 0001  (−15)  ===========    1111 0110  (−10) 

이 프로세스는 정밀도가 8비트로 제한되는 것에 따라 달라집니다. (존재하지 않는) 9번째 중요한 비트로의 캐리는 무시되고 산술적으로 정확한 결과가₁₀ 10이 됩니다.

캐리 행의 마지막 두 비트(오른쪽에서 왼쪽으로 읽음)에는 계산 결과 산술 오버플로가 발생했는지 여부, 이진 시스템이 나타내기에는 너무 큰 숫자(이 경우 8비트보다 큼) 등의 중요한 정보가 포함되어 있습니다. 마지막 두 비트가 서로 다를 때 오버플로 상태가 발생합니다. 위에서 언급한 바와 같이, 숫자의 부호는 결과의 MSB에 인코딩됩니다.

즉, 왼쪽 두 개의 캐리 비트(이 예에서 맨 위 행의 맨 왼쪽에 있는 것)가 모두 1이거나 모두 0이면 결과는 유효하고, 왼쪽 두 개의 캐리 비트가 "10" 또는 "01"이면 부호 오버플로가 발생합니다. 편리하게도 이 두 비트에 대한 XOR 연산을 통해 오버플로우 조건이 존재하는지 여부를 빠르게 확인할 수 있습니다. 예를 들어 7과 3의 부호화된 4비트 덧셈을 생각해 보십시오.

  0111 (carry) 0111 (7) + 0011 (3) ====== 1010 (-6) 유효하지 않습니다! 

이 경우 맨 왼쪽에 있는 두 개(MSB) 캐리 비트는 "01"이며, 이는 두 개의 보완 추가 오버플로우가 있었다는 것을 의미합니다. 즉, 1010 = 10은 -8 내지 7의 허용 범위를 벗어납니다. 부호 없는 정수로 취급되면 결과가 정확할 것입니다.

일반적으로 N비트 숫자 2개는 오버플로우 없이 둘 다 N+1비트로 먼저 부호 확장한 후 위와 같이 더하면 됩니다. N + 1비트 결과는 가능한 총합을 나타낼 수 있을 정도로 크기가 크기 때문에 오버플로우가 발생하지 않습니다(N = 5 2의 보수는 -16 ~ 15 범위의 값을 나타낼 수 있습니다). 그런 다음 폐기된 비트가 보존된 결과 비트의 적절한 부호 확장인 경우에만 값을 보존하면서 원하는 경우 결과를 N 비트로 '절단'할 수 있습니다. 이것은 오버플로우를 탐지하는 또 다른 방법을 제공합니다. 이 방법은 캐리 비트를 비교하는 방법과 동일하지만 일부 상황에서는 추가 내부에 액세스할 필요가 없기 때문에 구현하기가 더 쉬울 수 있습니다.

뺄셈

컴퓨터는 보통 뺄셈을 구현하기 위해 보형물의 방법을 사용합니다. 뺄셈에 보어를 사용하는 것은 피연산자와 결과의 모든 부호를 허용하기 때문에 음수를 나타내기 위해 보어를 사용하는 것과 밀접한 관련이 있습니다. 직접 뺄셈은 두 개의 보어 숫자에도 적용됩니다. 또한 두 개의 보어를 사용할 때의 장점은 피연산자의 부호를 조사하여 덧셈 또는 뺄셈이 필요한지 여부를 판단할 수 있다는 점입니다. 예를 들어, 15에서 -5를 빼면 실제로는 5에서 15가 더해지지만, 이것은 두 개의 보어 표현에 의해 숨겨집니다.

  11110000 (borrow) 0000 1111 (15) - 1111 1011 (-5) =========== 000100 (20) 

오버플로우는 또한 가장 왼쪽에 있는 두 개의 차용 비트를 검사하여 동일한 방법으로 탐지되며, 둘이 다를 경우 오버플로우가 발생했습니다.

또 다른 예는 결과가 음수인 감산 연산(15 - 35 = -20)입니다.

  11100000 (borrow) 0000 1111 (15) - 001000 11 (35) =========== 1110 1100 (-20) 

또한 감산의 오버플로우는 먼저 두 입력 모두를 추가 비트만큼 부호 확장함으로써 피할 수 있습니다(또는 연산 후에 감지).

곱셈

두 개의 N-비트 숫자의 곱은 가능한 모든 값을 포함하는 2N 비트를 필요로 합니다.^[12]

곱하기 전에 두 개의 보를 사용하는 두 피연산자의 정밀도가 두 배로 증가하면 직접 곱하기(이 정밀도를 초과하는 비트는 폐기)가 올바른 결과를 제공합니다.^[13] 예를 들어, 6 × (-5) = -30을 가정합니다. 먼저 정밀도가 4비트에서 8비트로 확장됩니다. 그런 다음 숫자를 곱하여 8번째 비트를 초과하는 비트를 버립니다("로 표시됨).x"):

     00000110 (6) * 11111011 (-5) ============ 110 1100 00000 11000000 11000000 x10000000 + xx000000000000 ============ xx11100010 

이는 매우 비효율적입니다. 사전에 정밀도를 두 배로 높여서 모든 추가 작업은 두 배의 정밀도를 가져야 하며 실제 컴퓨터에서 구현되는 더 효율적인 알고리즘보다 최소한 두 배 이상의 부분 제품이 필요합니다. 몇몇 곱셈 알고리즘들은 두 개를 보완하기 위해 고안되었는데, 특히 부스의 곱셈 알고리즘이 이에 해당합니다. 부호 크기 수를 곱하는 방법은 적응하지 않고 두 개의 보어 수와 함께 작동하지 않습니다. 곱셈기가 음수일 때는 일반적으로 문제가 없습니다. 곱셈기가 음수일 때는 제품의 초기 비트를 올바르게 설정하는 것이 문제입니다. 알고리즘을 적용하여 두 개의 보수를 처리하는 두 가지 방법은 일반적입니다.

• 먼저 승수가 음수인지 확인합니다. 그렇다면 곱하기 전에 두 피연산자를 모두 부정합니다(즉, 두 피연산자의 보수를 취합니다). 그러면 곱셈기가 양수가 되므로 알고리즘이 작동합니다. 두 피연산자가 모두 음수이기 때문에 결과는 여전히 올바른 부호를 갖게 됩니다.
• 다른 부분 제품과 같이 추가하는 대신 MSB(의사 부호 비트)에서 나온 부분 제품을 빼줍니다. 이 방법을 사용하려면 피승수의 부호 비트를 한 위치만큼 확장하여 시프트 오른쪽 동작 중에 보존해야 합니다.^[14]

두 번째 방법의 예로, 곱셈에 대한 일반적인 덧셈과 시프트 알고리즘을 예로 들 수 있습니다. 축적된 제품은 연필과 종이로 하는 것처럼 부분적인 제품을 왼쪽으로 이동하는 것이 아니라 오른쪽으로 이동하여 두 번째 레지스터로 이동하여 최종적으로 제품의 가장 중요하지 않은 절반을 유지합니다. 최하위 비트는 한 번 계산되면 변경되지 않기 때문에 추가는 단일 정밀도가 될 수 있으며 결국 제품의 가장 중요한 절반을 보유하게 될 레지스터에 축적됩니다. 다음 예제에서는 다시 6에 -5를 곱하면 두 레지스터와 확장된 부호 비트가 ""로 구분됩니다.

  0110 (6) (multiplic 및 확장 부호 비트 포함) × 1011 (-5) (multip라이어) = ==== ==== 011000 (첫 번째 부분 곱(가장 오른쪽 비트는 1)) 001100 (시프트 우, 확장 부호 비트 보존) 010000 (두 번째 부분 곱 추가 (다음 비트는 1)) 01001000 (시프트 우, 확장 부호 비트 보존) 0 0100 1000 (3번째 부분 곱 추가 : 0 변경 없음) 0 00100 100 (시프트 우, 확장 부호 비트 보존) 1 1100 100 (시프트 우, 확장 부호 비트 보존) 1 11 100 100 100 10 (시프트 우, 확장 부호 비트 보존) 11 100 100 10 (discard 확장 부호 비트, 최종 답 제공, −30) 

비교(오더)

비교는 종종 더미 감산으로 구현되는데, 여기서 컴퓨터의 상태 레지스터에 있는 플래그를 확인하지만 주요 결과는 무시됩니다. 0 플래그는 비교된 두 값이 동일한지 나타냅니다. 부호 및 오버플로 플래그의 배타적 논리합이 1인 경우 감산 결과는 0보다 작으며 그렇지 않은 경우 결과는 0 이상입니다. 이러한 검사는 종종 컴퓨터에서 조건부 분기 명령으로 구현됩니다.

부호화되지 않은 이진수는 간단한 사전 순서로 정렬할 수 있으며, 여기서 비트 값 0은 비트 값 1보다 작은 것으로 정의됩니다. 두 개의 보형 값의 경우 가장 중요한 비트의 의미가 반대가 됩니다(즉, 1은 0보다 작습니다).

다음 알고리즘(n비트 2의 보형 아키텍처의 경우)은 결과 레지스터 R을 A < B인 경우 -1, A > B인 경우 +1, A와 B가 동일한 경우 0으로 설정합니다.

// 부호 비트의 역비교  한다면 A(n-1) == 0 그리고. B(n-1) == 1 그리고나서     돌아가다 +1 또 다른 한다면 A(n-1) == 1 그리고. B(n-1) == 0 그리고나서     돌아가다 -1 끝.   // 남은 비트의 비교  위해서 i = n-2...0 하     한다면 A(i) == 0 그리고. B(i) == 1 그리고나서         돌아가다 -1     또 다른 한다면 A(i) == 1 그리고. B(i) == 0 그리고나서         돌아가다 +1      끝. 끝.   돌아가다 0 

2의 여집합과 2-아딕 수

1972년 MIT AI 연구소가 발표한 고전적인 HAKMEM에서 빌 고스퍼는 기계의 내부 표현이 두 개의 상호보완적인지 여부는 두 개의 연속적인 거듭제곱의 합으로 결정될 수 있다고 언급했습니다. 상상 속에서, 그는 이것의 결과가 대수적으로 "대수는 두 개의 보완물인 기계(우주)에서 실행된다"^[15]는 것을 나타냈다고 언급했습니다.

고스퍼의 최종 결론은 반드시 진지하게 받아들여져야 하는 것은 아니며, 수학적 농담에 가깝습니다. 중요한 단계는 "...110 = ...111 - 1", 즉 "2X = X - 1", 따라서 X = ...111 = -1입니다. 이는 1s의 무한열을 숫자로 간주하는 방법을 전제로 하며, 이를 위해서는 기초산술에서 유한한 자릿값 개념을 확장해야 합니다. 이것은 모든 정수에 대한 2-상보 표기법의 일부로서, 전형적인 2-아딕 숫자로서, 또는 심지어 실수 1+2+4+8+··^[16]의 발산 급수에 대해 정의된 일반화된 합 중 하나로서도 의미가 있습니다. 무한대(2의 양의 거듭제곱까지 확장) 비트열로 작동하도록 이상화된 디지털 산술 회로는 2의 보표 표현과 호환되는 2-아딕 덧셈 및 곱셈을 생성합니다.^[17] 2-아딕 메트릭에서 이진 산술 및 비트와이즈 연산의 연속성은 암호학에서도 일부 사용됩니다.^[18]

분수변환

.0101과 같이 분수 부분이 있는 숫자를 변환하려면 일반 변환과 같이 오른쪽에서 왼쪽으로 시작하는 1을 10진수로 변환해야 합니다. 이 예에서 0101은 십진법으로 5와 같습니다. 부동 소수점 뒤의 각 숫자는 분모가 2의 승수인 분수를 나타냅니다. 그래서 첫 번째는 1/2, 두 번째는 1/4 등입니다. 위에서 언급한 바와 같이 십진법 값을 이미 계산한 후 LSB의 분모(LSB = 오른쪽에서 시작)만 사용합니다. 이번 전환의 최종 결과는 5/16입니다.

예를 들어 이 방법이 작동하려면 변동 값이 .0110이면 오른쪽에서 마지막 0을 고려하지 않아야 합니다. 따라서 0110에 대한 10진수 값을 계산하는 대신 011이라는 값을 계산합니다(끝에 0을 남겨두면 결과는 6이 되고 분모 2 = 16이 되어 3/8로 줄어듭니다). 분모는 8로 최종 결과는 3/8입니다.

참고 항목

• 자신의 보형물, 대안적인 이진수 규칙
• 두 개의 상보 표현에서의 복원 및 비복원 분할을 포함하는 분할 알고리즘
• 오프셋 이진법
• p-adic number
• 기계적 계산기에서 사용되는 보법, 다른 숫자 베이스에 대한 일반화 방법

메모들

참고문헌

더보기

• Two's Complemental Description, (Thomas Finley, 2000)

• Koren, Israel (2002). Computer Arithmetic Algorithms. A.K. Peters. ISBN 1-56881-160-8.
• Flores, Ivan (1963). The Logic of Computer Arithmetic. Prentice-Hall.

외부 링크

• Two's complement array multiplier 자바스크립트 시뮬레이터