To komplement - Two's complement

To's komplement er en matematisk operation på binære tal og er et eksempel på et radix -komplement . Det bruges i computing som en metode til signeret nummerrepræsentation .

De tos komplement af et N -bit -tal er defineret som dets komplement i forhold til 2 ^N ; summen af et nummer og dens to-komplement er 2 ^N . For eksempel til de tre-bit nummer 010 ₂ , den to-komplement er 110 ₂ , fordi 010 ₂ + 110 ₂ = 1000 ₂ = 8 ₁₀ som er lig med 2 ³ . De to komplement beregnes ved at vende bitene og tilføje et.

To's komplement er den mest almindelige metode til at repræsentere signerede heltal på computere og mere generelt binære værdier med fast punkt . I dette skema, hvis det binære tal 010 ₂ koder for det underskrevne heltal 2 ₁₀ , koder dets tos komplement, 110 ₂ , det inverse: −2 ₁₀ . Med andre ord kan tegnet på de fleste heltal (alle undtagen et af dem) vendes i dette skema ved at tage de tos komplement til dets binære repræsentation. Tabellerne til højre illustrerer denne ejendom.

Sammenlignet med andre systemer til repræsentation af signerede tal ( f.eks. Ens komplement ) har tos komplement den fordel, at de grundlæggende aritmetiske operationer for addition , subtraktion og multiplikation er identiske med dem for usignerede binære tal (så længe input er repræsenteret i det samme antal bits som output, og eventuelt overløb ud over disse bits kasseres fra resultatet). Denne egenskab gør systemet enklere at implementere, især for aritmetik med højere præcision. I modsætning til ens komplementsystemer har tos komplement ingen repræsentation for det negative nul og lider derfor ikke af de tilhørende vanskeligheder.

En anden måde at finde tos komplement til et tal på er bekvemt at tage sit ens komplement og tilføje et: summen af ​​et tal og dets ens komplement er alle '1' bits eller 2 ^N - 1 ; og per definition, er summen af et nummer og dens to s komplement er 2 ^N .

Historie

Den fremgangsmåde til komplementer havde længe været anvendt til at udføre subtraktion i decimal additionsmaskiner og mekaniske regnemaskiner . John von Neumann foreslog brug af tos komplementær binær repræsentation i sit 1945 første udkast til en rapport om EDVAC- forslaget til en elektronisk lagret program digital computer. EDSAC fra 1949 , som var inspireret af det første udkast , brugte tos komplementrepræsentation af binære tal.

Mange tidlige computere, herunder CDC 6600 , LINC , PDP-1 og UNIVAC 1107, bruger deres komplement- notation; efterkommere af UNIVAC 1107, UNIVAC 1100/2200 serien , fortsatte med at gøre det. De IBM 700/7000 serien videnskabelige maskiner bruger tegn / størrelsesorden notation, bortset fra de indeksregistre som er to-komplement. Tidlige kommercielle tokomplementcomputere omfatter Digital Equipment Corporation PDP-5 og PDP-6 fra 1963 . Det System / 360 , der blev indført i 1964 af IBM , så den dominerende aktør i computerindustrien, lavet to-komplement den mest udbredte binær repræsentation i computerindustrien. Den første minicomputer, PDP-8, der blev introduceret i 1965, bruger tos komplementaritmetik ligesom 1969 Data General Nova , 1970 PDP-11 og næsten alle efterfølgende minicomputere og mikrocomputere.

Konvertering fra tos komplementrepræsentation

Et to-komplement talsystem koder for positive og negative tal i en binær talrepræsentation. Vægten af ​​hver bit er en effekt på to, bortset fra den mest betydningsfulde bit , hvis vægt er negativ af den tilsvarende effekt af to.

Værdien  w af et N -bit heltal er givet ved følgende formel: ${\ displaystyle a_ {N-1} a_ {N-2} \ prikker a_ {0}}$

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

Den mest betydningsfulde bit bestemmer tegn på tallet og kaldes undertiden tegnbit . I modsætning til i tegn-og-størrelse repræsentation har tegnbitten også vægten- (2 ^{N  -1} ) vist ovenfor. Ved hjælp af N bits kan alle heltal fra - (2 ^{N  - 1} ) til 2 ^{N  - 1} - 1 repræsenteres.

Konvertering til tos komplementrepræsentation

I tos komplementnotation repræsenteres et ikke-negativt tal ved dets almindelige binære repræsentation ; i dette tilfælde er den mest betydningsfulde bit 0. Selvom antallet af repræsenterede tal ikke er det samme som med usignerede binære tal. For eksempel kan et 8-bit usigneret tal repræsentere værdierne 0 til 255 (11111111). Et tos komplement 8-bit tal kan dog kun repræsentere positive heltal fra 0 til 127 (01111111), fordi resten af ​​bitkombinationerne med den mest betydende bit som '1' repræsenterer de negative heltal -1 til -128.

De tos komplementoperation er den additive inverse operation, så negative tal repræsenteres af de tos komplement af den absolutte værdi .

Fra demes komplement

For at få de tos komplement til et negativt binært tal vendes bitene eller "vendes" ved at bruge den bitvise NOT -operation; værdien af ​​1 tilføjes derefter til den resulterende værdi, idet der ignoreres overløbet, der opstår, når de to komplementerer 0.

For eksempel ved hjælp af 1 byte (= 8 bits) er decimaltallet 5 repræsenteret med

0000 0101 ₂

Den mest betydningsfulde bit er 0, så mønsteret repræsenterer en ikke-negativ værdi. For at konvertere til −5 i to-komplement notation, er bitene først omvendt, det vil sige: 0 bliver 1 og 1 bliver 0:

1111 1010 ₂

På dette tidspunkt er repræsentationen dem, der supplerer decimalværdien −5. For at opnå de to komplement føjes 1 til resultatet, hvilket giver:

1111 1011 ₂

Resultatet er et underskrevet binært tal, der repræsenterer decimalværdien -5 i to-komplement-form. Den mest betydningsfulde bit er 1, så den repræsenterede værdi er negativ.

De tos komplement til et negativt tal er den tilsvarende positive værdi, undtagen i et specielt tilfælde. For eksempel giver invertering af bitene på −5 (ovenfor):

0000 0100 ₂

Og tilføjelse af en giver den endelige værdi:

0000 0101 ₂

På samme måde er de tos komplement til nul nul: invertering giver alle dem, og tilføjelse af en ændrer dem tilbage til nuller (da overløbet ignoreres).

De tos komplement til det mest negative tal, der kan repræsenteres (f.eks. Et som den mest signifikante bit og alle andre bits nul) er sig selv. Derfor er der et 'ekstra' negativt tal, for hvilket tos komplement ikke giver negationen, se § Mest negative tal nedenfor.

Subtraktion fra 2 ^N

Summen af ​​et tal og dets ens komplement er et N -bit ord med alle 1 bits, hvilket er (læsning som et usigneret binært tal) 2 ^N -1 . Derefter tilsætning af et nummer til sine to-komplement resultater i N laveste bit sat til 0 og carry bit 1, hvor sidstnævnte har vægten (læse det som et binært tal uden fortegn) af 2 ^N . Derfor, i den usignerede binære aritmetik opfylder værdien af ​​to-komplement negative tal x * af et positivt x ligestillingen x * = 2 ^N - x .

For eksempel at finde 4-bit repræsentationen af ​​−5 (abonnementer angiver repræsentationens basis ):

x = 5 ₁₀ derfor x = 0101 ₂

Derfor med N = 4 :

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

Beregningen kan udføres helt i base 10, og konverteres til base 2 i slutningen:

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

Arbejder fra LSB mod MSB

En genvej til manuelt at konvertere et binært tal til dets to komplement er at starte med den mindst signifikante bit (LSB) og kopiere alle nuller, der arbejder fra LSB mod den mest betydende bit (MSB), indtil den første 1 er nået; kopier derefter den 1, og vend alle de resterende bits (Lad MSB'en være en 1, hvis det oprindelige tal var i tegn-og-størrelsesrepræsentation). Denne genvej giver en person mulighed for at konvertere et tal til sine tos komplement uden først at danne sit ens komplement. For eksempel: i tos komplementrepræsentation er negationen af ​​"0011 1100" "1100 0 100 ", hvor de understregede cifre var uændrede ved kopieringen (mens resten af ​​cifrene blev vendt).

I computerkredsløb er denne metode ikke hurtigere end metoden "komplement og tilføj en"; begge metoder kræver, at der arbejdes i rækkefølge fra højre til venstre og spredes logiske ændringer. Metoden til komplementering og tilføjelse af en kan fremskyndes ved hjælp af et standardfremmende fremadrettet adder- kredsløb; LSB mod MSB -metoden kan fremskyndes ved en lignende logisk transformation.

Skilt forlængelse

Når man drejer et to-komplement-tal med et bestemt antal bits til et med flere bits (f.eks. Ved kopiering fra en 1-byte-variabel til en 2-byte-variabel), skal den mest signifikante bit gentages i alle de ekstra bits . Nogle processorer gør dette i en enkelt instruktion; på andre processorer skal der bruges en betinget efterfulgt af kode for at indstille de relevante bits eller bytes.

På samme måde, når et to-komplement-nummer flyttes til højre, skal den mest signifikante bit, som indeholder størrelse og tegninformationen, opretholdes. Men når der skiftes til venstre, flyttes der et 0 til. Disse regler bevarer den almindelige semantik, at venstre skift multiplicerer tallet med to og højre skift dividerer tallet med to.

Både forskydning og fordobling af præcisionen er vigtige for nogle multiplikationsalgoritmer. Bemærk, at i modsætning til addition og subtraktion udføres breddeudvidelse og højre forskydning forskelligt for signerede og usignerede numre.

Mest negative tal

Med kun en undtagelse, der starter med et hvilket som helst tal i to-komplement-repræsentation, hvis alle bitene vendes og 1 tilføjes, opnås to-komplement-repræsentationen af ​​det negative af dette tal. Positiv 12 bliver negativ 12, positiv 5 bliver negativ 5, nul bliver til nul (+overløb) osv.

At tage de tos komplement til minimumstallet i intervallet vil ikke have den ønskede effekt at negere tallet. For eksempel er de to komplement af −128 i et 8 bit system −128. Selvom det forventede resultat ved at negere −128 er +128, er der ingen repræsentation af +128 med et 8 bit tos komplementsystem, og det er derfor faktisk umuligt at repræsentere negationen. Bemærk, at de to komplement, der er det samme tal, opdages som en overløbstilstand, da der var en indføring i, men ikke ud af den mest betydningsfulde bit.

Dette fænomen handler grundlæggende om matematikken i binære tal, ikke detaljerne i repræsentationen som tos komplement. Matematisk set er dette et supplement til det faktum, at negativet på 0 igen er 0. For et givet antal bits k er der et lige antal binære tal 2 ^k , at tage negativer er en gruppeaktion (i gruppen af ​​rækkefølge 2) på binære tal, og da nulbanen har rækkefølge 1, skal mindst et andet tal have en bane i rækkefølge 1, for at orbiternes ordrer kan tilføje til rækkefølgen af ​​sættet. Et andet tal må således være uforanderligt under at tage negative (formelt set med orbit-stabilisator sætning ). Geometrisk kan man se k -bit binære tal som den cykliske gruppe , som kan visualiseres som en cirkel (eller korrekt en almindelig 2 ^k -gon), og at tage negativer er en refleksion, som løser elementerne i rækkefølge, der deler 2: 0 og det modsatte punkt, eller visuelt zenit og nadir. ${\ displaystyle \ mathbb {Z} /2^{k}}$

Tilstedeværelsen af ​​det mest negative tal kan føre til uventede programmeringsfejl, hvor resultatet har et uventet tegn eller fører til en uventet overløbsundtagelse eller fører til helt mærkelig adfærd. For eksempel,

• operatøren for unary negation må ikke ændre tegnet på et nummer uden nul. f.eks. - ( - 128) → −128.

• en implementering af absolut værdi kan returnere et negativt tal. f.eks. abs (−128) → −128.

• På samme måde fungerer multiplikation med −1 muligvis ikke som forventet. f.eks. (−128) × (−1) → −128.

• Division med −1 kan forårsage en undtagelse (som den, der er forårsaget ved at dividere med 0). Selv beregning af resten (eller modulo) med −1 kan udløse denne undtagelse. f.eks. (−128) ÷ (−1) → crash, (−128) % (−1) → crash.

I programmeringssprog C og C ++ er ovenstående adfærd udefineret, og det kan ikke kun give mærkelige resultater, men kompilatoren kan frit antage, at programmøren har sikret, at udefinerede beregninger aldrig sker, og foretage konklusioner fra denne antagelse. Dette muliggør en række optimeringer, men fører også til en række mærkelige fejl i sådanne udefinerede programmer.

Det mest negative tal i tos komplement kaldes undertiden "det underlige tal", fordi det er den eneste undtagelse. Selvom tallet er en undtagelse, er det et gyldigt tal i almindelige tos komplementsystemer. Alle aritmetiske operationer fungerer med det både som en operand og (medmindre der var et overløb) et resultat.

Hvorfor det virker

I betragtning af et sæt af alle mulige N -bit -værdier kan vi tildele den nederste (med den binære værdi) helheden til at være heltalene fra 0 til (2 ^{N  -1} -1) inklusive og den øverste halvdel til at være -2 ^{N  -1} til −1 inklusiv. Den øvre halvdel (igen ved den binære værdi) kan bruges til at repræsentere negative heltal fra -2 ^{N  - 1} til -1, fordi de under additionsmodul 2 ^N opfører sig på samme måde som de negative heltal. Det vil sige, at fordi i + j mod 2 ^N = i + ( j + 2 ^N ) mod 2 ^N enhver værdi i sættet {  j + k  2 ^N | k er et heltal}  kan bruges i stedet for  j .

For eksempel med otte bits er de usignerede bytes 0 til 255. Ved at trække 256 fra den øverste halvdel (128 til 255) får de signerede bytes −128 til −1.

Forholdet til tos komplement realiseres ved at bemærke, at 256 = 255 + 1 , og (255 - x ) er demnes komplement af  x .

Eksempel

I dette underafsnit er decimaltal suffikset med et decimalpunkt "."

For eksempel kan et 8 bit -tal kun repræsentere hvert helt tal fra −128. til 127., inklusive, siden (2 ^{8 - 1} = 128.) . −95. modulo 256. svarer til 161. siden

−95. + 256.

= −95. + 255. + 1

= 255. - 95. + 1

= 160. + 1.

= 161.

   1111 1111 255.
 - 0101 1111 - 95.
 =================
   1010 0000 (ens komplement) 160.
 + 1 + 1
 =================
   1010 0001 (tos komplement) 161.

Grundlæggende repræsenterer systemet negative heltal ved at tælle baglæns og vikle rundt . Grænsen mellem positive og negative tal er vilkårlig, men konventionelt har alle negative tal en bit til venstre ( mest betydende bit ) på en. Derfor er det mest positive 4 bit -tal 0111 (7.) og det mest negative er 1000 (−8.). På grund af brugen af ​​bit til venstre som tegnbit er den absolutte værdi af det mest negative tal (| −8. | = 8.) for stor til at repræsentere. Negering af en tos komplementnummer er enkelt: Vend alle bitene og tilføj en til resultatet. For eksempel ved at negere 1111 får vi 0000 + 1 = 1 . Derfor skal 1111 i binært repræsentere -1 i decimal.

Systemet er nyttigt til at forenkle implementeringen af ​​regning på computerhardware. Tilføjelse af 0011 (3.) til 1111 (−1.) Ser først ud til at give det forkerte svar på 10010. Hardwaren kan dog simpelthen ignorere den bit til venstre for at give det korrekte svar på 0010 (2.). Overløbskontroller skal stadig eksistere for at fange operationer som f.eks. Summering 0100 og 0100.

Systemet tillader derfor tilføjelse af negative operander uden et subtraktionskredsløb eller et kredsløb, der registrerer tegn på et tal. Desuden kan dette additionskredsløb også udføre subtraktion ved at tage de tos komplement til et tal (se nedenfor), hvilket kun kræver en ekstra cyklus eller sit eget adderkredsløb. For at udføre dette fungerer kredsløbet blot, som om der var en ekstra venstre-bit på 1.

Aritmetiske operationer

Tilføjelse

Tilføjelse af to-komplement tal kræver ingen særlig behandling, selvom operanderne har modsatte tegn: resultatet af resultatet bestemmes automatisk. For eksempel tilføjer 15 og −5:

  11111 111 (bære)
   0000 1111 (15)
 + 1111 1011 (−5)
 ============
   0000 1010 (10)

Eller beregningen af ​​5 - 15 = 5 + (−15):

          1 (bære)
   0000 0101 (5)
 + 1111 0001 (−15)
 ============
   1111 0110 (−10)

Denne proces afhænger af begrænsning til 8 bits præcision; en overførsel til den (ikke -eksisterende) 9. mest betydningsfulde bit ignoreres, hvilket resulterer i det aritmetisk korrekte resultat på 10 ₁₀ .

De to sidste bits i bære rækken (læsning fra højre til venstre) indeholder vigtig information: om beregningen resulterede i et aritmetisk overløb , et tal for stort til at det binære system kan repræsentere (i dette tilfælde større end 8 bits). Der findes en overløbstilstand, når disse to sidste bits er forskellige fra hinanden. Som nævnt ovenfor er tegnet på nummeret indkodet i MSB'en for resultatet.

Med andre ord, hvis de to venstre bærebit (dem længst til venstre i den øverste række i disse eksempler) begge er 1'er eller begge 0'er, er resultatet gyldigt; hvis de venstre to bærebit er "1 0" eller "0 1", er der sket et tegnoverløb. En XOR -operation på disse to bits kan hurtigt bestemme, om der eksisterer en overløbstilstand. Overvej som et eksempel den signerede 4-bit tilføjelse af 7 og 3:

  0111 (bære)
   0111 (7)
 + 0011 (3)
 =======
   1010 (−6) ugyldig!

I dette tilfælde er de yderste venstre to (MSB) bærestykker "01", hvilket betyder, at der var et to-komplement-tilføjelsesoverløb. Det vil sige, at 1010 ₂ = 10 ₁₀ er uden for det tilladte område på −8 til 7. Resultatet ville være korrekt, hvis det blev behandlet som et usigneret heltal.

Generelt kan to N -bit -tal tilføjes uden overløb ved først at forlænge dem begge til N  + 1 bits og derefter tilføje som ovenfor. The N  + 1 bit resultat er stor nok til at repræsentere enhver mulig sum ( N = 5 to-komplement kan repræsentere værdier i området -16 til 15), så overløb vil aldrig forekomme. Det er derefter muligt, hvis det ønskes, at 'trunke' resultatet tilbage til N bits, samtidig med at værdien bevares, hvis og kun hvis den kasserede bit er en ordentlig tegnforlængelse af de bevarede resultatbits. Dette giver en anden metode til at detektere overløb - hvilket svarer til metoden til sammenligning af bærebitene - men som i nogle situationer kan være lettere at implementere, fordi det ikke kræver adgang til tilsætningens indvendige dele.

Subtraktion

Computere bruger normalt metoden til komplementeringer til at implementere subtraktion. Brug af komplementer til subtraktion er tæt forbundet med at bruge komplementer til at repræsentere negative tal, da kombinationen tillader alle tegn på operander og resultater; direkte subtraktion fungerer også med to-komplement tal. Ligesom tilføjelse er fordelen ved at bruge tos komplement elimineringen af ​​at undersøge operandernes tegn for at afgøre, om addition eller subtraktion er nødvendig. For eksempel at trække −5 fra 15 er virkelig at tilføje 5 til 15, men dette er skjult af de to komplementære repræsentation:

  11110 000 (lån)
   0000 1111 (15)
 - 1111 1011 (−5)
 ============
   0001 0100 (20)

Overløb registreres på samme måde som for tilføjelse ved at undersøge de to yderste (mest betydningsfulde) bits i lånene; overløb er sket, hvis de er forskellige.

Et andet eksempel er en subtraktionsoperation, hvor resultatet er negativt: 15 - 35 = −20:

  11100 000 (lån)
   0000 1111 (15)
 - 0010 0011 (35)
 ============
   1110 1100 (−20)

Med hensyn til tilføjelse kan overløb i subtraktion undgås (eller detekteres efter operationen) ved først at forlænge begge input med en ekstra bit.

Multiplikation

Produktet af to N -bit tal kræver 2 N bits for at indeholde alle mulige værdier.

Hvis præcisionen af ​​de to operander, der bruger tos komplement, er fordoblet før multiplikationen, vil direkte multiplikation (kassering af overskydende bits ud over denne præcision) give det korrekte resultat. Tag f.eks. 6 × (−5) = −30 . For det første udvides præcisionen fra fire bits til otte. Derefter multipliceres tallene og kasserer bitene ud over den ottende bit (som vist med " x "):

     00000110 (6)
 * 11111011 (−5)
 ==============
          110
         1100
        00000
       110000
      1100000
     11000000
    x10000000
 + xx00000000
 ==============
   xx11100010

Dette er meget ineffektivt; ved at fordoble præcisionen på forhånd skal alle tilføjelser være dobbeltpræcision og der er behov for mindst dobbelt så mange delprodukter end for de mere effektive algoritmer, der faktisk er implementeret i computere. Nogle multiplikationsalgoritmer er designet til tos komplement, især Booths multiplikationsalgoritme . Metoder til multiplikation af tegn i størrelsesorden fungerer ikke med to-komplement tal uden tilpasning. Der er normalt ikke et problem, når multiplicand (den der gentagne gange tilføjes for at danne produktet) er negativ; problemet er at indstille produktets indledende bits korrekt, når multiplikatoren er negativ. To metoder til at tilpasse algoritmer til at håndtere to-komplement-tal er almindelige:

• Kontroller først, om multiplikatoren er negativ. I så fald skal du negere ( dvs. tage de tos komplement af) begge operander, før du multiplicerer. Multiplikatoren vil derefter være positiv, så algoritmen fungerer. Fordi begge operander negeres, vil resultatet stadig have det korrekte tegn.
• Træk det delprodukt, der er resultatet af MSB (pseudotegnebit) i stedet for at tilføje det som de andre delprodukter. Denne metode kræver, at multiplikandens tegnbit forlænges med en position og bevares under skiftene til højre.

Som et eksempel på den anden metode skal du tage den almindelige tilføjelses-og-skift-algoritme til multiplikation. I stedet for at flytte delprodukter til venstre, som det gøres med blyant og papir, flyttes det akkumulerede produkt til højre, ind i et andet register, der i sidste ende vil indeholde den mindst betydelige halvdel af produktet. Da de mindst signifikante bits ikke ændres, når de er beregnet, kan tilføjelserne være enkeltpræcision, der akkumuleres i registret, der i sidste ende vil indeholde den mest betydningsfulde halvdel af produktet. I det følgende eksempel, igen ganget med 6 med −5, adskilles de to registre og den udvidede tegnbit med "|":

  0 0110 (6) (multiplikand med udvidet tegnbit)
  × 1011 (−5) (multiplikator)
  = | ==== | ====
  0 | 0110 | 0000 (første delprodukt (bit til højre er 1))
  0 | 0011 | 0000 (skift til højre, bevar udvidet tegnbit)
  0 | 1001 | 0000 (tilføj andet delprodukt (næste bit er 1))
  0 | 0100 | 1000 (skift til højre, bevar udvidet tegnbit)
  0 | 0100 | 1000 (tilføj tredje delprodukt: 0 så ingen ændring)
  0 | 0010 | 0100 (skift til højre, bevar udvidet tegnbit)
  1 | 1100 | 0100 (træk sidste delprodukt fra, da det er fra tegnbit)
  1 | 1110 | 0010 (skift til højre, bevar udvidet tegnbit)
   | 1110 | 0010 (kassér forlænget tegnbit, der giver det endelige svar, −30)

Sammenligning (bestilling)

Sammenligning implementeres ofte med en dummy -subtraktion, hvor flagene i computerens statusregister kontrolleres, men hovedresultatet ignoreres. Den nul flag angiver, om to værdier sammenlignes lige. Hvis eksklusiv-eller for tegn og overløbsflag er 1, var subtraktionsresultatet mindre end nul, ellers var resultatet nul eller større. Disse kontroller implementeres ofte på computere i betingede filinstruktioner .

Usignerede binære tal kan ordnes ved en simpel leksikografisk rækkefølge , hvor bitværdien 0 er defineret som mindre end bitværdien 1. For tos komplementværdier vendes betydningen af ​​den mest betydningsfulde bit (dvs. 1 er mindre end 0).

Den følgende algoritme (for en n -bit tos komplementarkitektur) sætter resultatregistret R til -1 hvis A <B, til +1 hvis A> B og til 0, hvis A og B er ens:

// reversed comparison of the sign bit

if A(n-1) == 0 and B(n-1) == 1 then
    return +1
else if A(n-1) == 1 and B(n-1) == 0 then
    return -1
end
 
// comparison of remaining bits

for i = n-2...0 do
    if A(i) == 0 and B(i) == 1 then
        return -1
    else if A(i) == 1 and B(i) == 0 then
        return +1 
    end
end
 
return 0

To komplement og 2-adiske tal

I et klassisk HAKMEM udgivet af MIT AI Lab i 1972 bemærkede Bill Gosper , at hvorvidt en maskines interne repræsentation var to-komplement eller ikke, kunne bestemmes ved at summere to successive beføjelser. I fantasiflyvning bemærkede han, at resultatet af at gøre dette algebraisk indikerede, at "algebra køres på en maskine (universet), som er to-komplement."

Gospers slutkonklusion er ikke nødvendigvis beregnet til at blive taget alvorligt, og det ligner en matematisk vittighed . Det kritiske trin er "... 110 = ... 111 - 1", dvs. "2 X = X  - 1", og dermed X  = ... 111 = −1. Dette forudsætter en metode, ved hvilken en uendelig streng på 1s betragtes som et tal, hvilket kræver en udvidelse af de begrænsede stedværdibegreber i elementær aritmetik. Det er meningsfuldt enten som en del af en to-komplement-notation for alle heltal, som et typisk 2-adisk tal , eller endda som en af ​​de generaliserede summer defineret for den divergerende række af reelle tal 1 + 2 + 4 + 8 + ·· · . Digitale aritmetiske kredsløb, der er idealiseret til at fungere med uendelige (strækker sig til positive kræfter på 2) bitstrenge, producerer 2-adisk addition og multiplikation, der er kompatibel med tos komplementrepræsentation. Kontinuitet i binær aritmetiske og bitvise operationer i 2-adic metric har også en vis anvendelse i kryptografi.

Fraktionskonvertering

For at konvertere et tal med en brøkdel, f.eks. .0101, skal man konvertere fra højre til venstre 1'erne til decimal som ved en normal konvertering. I dette eksempel er 0101 lig med 5 i decimal. Hvert ciffer efter flydende punkt repræsenterer en brøkdel, hvor nævneren er en multiplikator på 2. Så det første er 1/2, det andet er 1/4 og så videre. Efter allerede at have beregnet decimalværdien som nævnt ovenfor, bruges kun nævneren for LSB (LSB = start fra højre). Det endelige resultat af denne konvertering er 5/16.

For eksempel, at have den flydende værdi på .0110 for at denne metode fungerer, bør man ikke overveje den sidste 0 fra højre. Derfor beregner vi i stedet for at beregne decimalværdien for 0110 værdien 011, som er 3 i decimal (ved at forlade 0'en til sidst, ville resultatet have været 6 sammen med nævneren 2 ⁴  = 16, hvilket reducerer til 3/8). Nævneren er 8, hvilket giver et endeligt resultat, hvis 3/8.

Se også

• Divisionsalgoritme , herunder gendannelse og ikke-gendannelse af division i to-komplement-repræsentationer
• Offset binær
• p-adic nummer
• Komplementmetode , generalisering til andre talbaser, brugt på mekaniske regnemaskiner

Referencer

Yderligere læsning

• Two's Complement Forklaring, (Thomas Finley, 2000)

• Koren, Israel (2002). Computerekniske algoritmer . AK Peters. ISBN 1-56881-160-8.
• Flores, Ivan (1963). Computerregningens logik . Prentice-Hall.

eksterne links

• To komplement array multiplikator JavaScript simulator