Komplement dvojke,dopunski kod,potpuni komplement ilidrugi komplement predstavljamatematičku operaciju nadbinarnim brojevima, kao i reprezentaciju označenihbrojeva baziranu na tim operacijama.
Komplement dvojke nekog N-bitnog broja dobija se kao dopuna do broja 2N, odnosno vrednost komplementa dvojke za neki broj dobija se oduzimanjem tog broja od broja 2N.Ekvivalentno ovoj metodi, komplement dvojke nekog broja može se dobiti i pomoću komplementa jedinice.[појаснити]
Najpre se izračunaprvi komplement broja tako što se svaka binarna cifra polaznog broja promeni (nula u jedinicu, a jedinica u nulu), pa se zatim dobijenombinarnom broju doda jedinica.Sabiranje sa jedinicom obavlja se po principima binarnog sabiranja.Binarni brojevi se sabiraju isto kao i decimalni, s tim što se prenos na više mesto događa kada zbir premaši 1, a ne 9, kao što je u decimalnom sistemu. Drugi komplement negativnog binarnog broja dobija se tako što se sve nule i prva jedinica s desne strane prepišu, a ostale cifre se invertuju.[појаснити]U komplementu dvojke može se predstaviti bilo koji celobrojni označeni broj iz intervala -2N-1 do 2N-1-1, dok se u komplementu jedinice mogu predstaviti samo brojevi iz intervala od -(2N-1-1) do 2N-1-1.
Dve glavne prednosti predstavljanja broja u komplementu dvojke:Osnovnearitmetičke operacije kao što su sabiranje, oduzimanje i množenje su iste kao i za neoznačene celobrojne brojeve sve dok su ulazni podaci zapisani u istom broju bita i dok se svako prekoračenje preko tog broja bitova isključuje iz rešenja.
Postoji samo jedna predstava broja 0, čime je izbegnuta konfuzija koja se stvara u komplementu jedinice prilikom definisanja nule dva puta (jednom kao pozitivnog, a drugi put kao negativnog broja.)
| Prikaz sa 8 bita | Vrednost u neoznačenom sistemu | Vrednost u komplement dvojke |
|---|---|---|
| 1111 1111 | 255 | -1 |
| 1111 1110 | 254 | -2 |
| 1000 0010 | 130 | -126 |
| 1000 0001 | 129 | -127 |
| 1000 000 | 128 | -128 |
| 0111 1111 | 127 | 127 |
| 0111 1110 | 126 | 126 |
| 0000 0010 | 2 | 2 |
| 0000 0001 | 1 | 1 |
| 0000 0000 | 0 | 0 |
Komplement je pojam koji se često koristi kada se govori obrojevnim sistemima. Praktični smisao uviđa se prilikom prikazivanja negativnih brojeva i oduzimanja brojeva, odnosno prilikom realizacije ove operacije kroz operaciju sabiranja. Komplementi pozitivnih brojeva su isti kao i ti sam brojevi.
Najopštija, uprošćena definicija komplementa bila bi da je to dopuna datog broja do neke unapred definisane vrednosti.U binarnom brojnom sistemu definisana su samo dva komplementa i oba su od praktičnog značaja.Komplement jedinice (kao komplement najveće cifre) i komplement dvojke (kao komplement osnove sistema).
Sistem komplementa dvojke kodira pozitivne i negativne brojeve u binarnoj prezentaciji. Težina svakog bita je stepen broja dva, osim zanajvažniji bit (MSB), čija težina je negativ od odgovarajućeg stepena broja dva.
Vrednost w N-bitnog integera data je pomoću sledeće formule:
Najvažniji bit određuje znak broja i ponekad se naziva znak bit. Za razliku od sign-and-magnitude prezentacije, sign bit takođe ima težinu −(2N − 1) pokazanu iznad. Korišćenjem N bitova, svi celi brojevi od −(2N − 1) to 2N − 1 − 1 mogu biti prezentovani.
U notaciji komplementa dvojke, ne-negativni broj je prikazan u svojoj uobičajenoj prezentaciji; u ovom slučaju. najvažniji bit je 0. Opseg prikazanih brojeva nije isti kao kod neoznačenih (unsigned) binarnih brojeva. Na primer, 8-bitni neoznačeni broj može predstavljati vrednosti između 0 i 255 (11111111). 8-bitni broj komplementa dvojke može da predstavlja cele pozitivne brojeve od 0 do 127 (01111111), jer ostatak kombinacija bitova sa najvažnijim bitom setovanim na '1' predstavlja cele negativne brojeve od -1 do -128. Operacija komplementa dvojke je aditivno inverzna operacija, pa su negativni brojevi predstavljeni drugim komplementom apsolutne vrednosti.
Da bi se dobio komplement dvojke binarnog broja, bitovi se invertuju korišćenjem binarne NOT operacije; rezultujućoj vrednosti se dodaje 1, ignorišući overflow prestup koji se pojavljuje kada se uzima komplement dvojke broja 0.Na primer, koristeći 1 bajt (= 2 nibla = 8 bitova), decimalni broj 5 je prikazan kao
Najvažniji bit je 0, pa ova kombinacija predstavlja ne-negativni broj. Za konverziju u -5 u notaciji komplementa dvojke, bitovi suinvertovani; 0 postaje 1, i 1 postaje 0;
U ovom trenutku, prikazani broj predstavlja -5 u komplementu jedinice. Kako bi se dobio komplement dvojke, 1 se dodaje rezultatu, dajući:
Rezultat je označeni binarni broj koji predstavlja decimalnu vrednost -5 u formi komplementa dvojke. Najvažniji bit je 1, pa je prikazana vrednost negativna.
Komplement dvojke negativnog broja je njegova odgovarajuća pozitivna vrednost. Na primer, invertovanje bitova od -5 (iznad) daje:
Dodavanjem jedinice daje konačnu vrednost:
Komplement dvojke broja 0 je 0: Invertovanjem svi bitovi postaju 1, a zatim dodavanjem jedinice, svi bitovi ponovo postaju nule (overflow prestup se ignoriše). Komplement dvojke najnegativnijeg broja koji se može prikazati (na primer broj sa setovanim najvažnijim bitom i svim ostalim bitovima na nuli) je isti taj broj. Iz ovoga se zaključuje da postoji još jedan dodatni negativan broj.
Zbir broja i njegovog komplementa jedinice je N-bitna reč sa svim bitovima vrednosti 1, koja je 2N-1 Dodavanje broja njegovom komplementu dvojke rezultuje setovanjem N najnižih bitova na 0 icarry bita na 1, gde carry bit ima težinu 2N. Tako, u neoznačenoj binarnoj aritmetici vrednost komplementa dvojke negativnog broja x* od pozitivnog x zadovoljava jednakost x* = 2N − x[1]
Na primer, da bi smo pronašli 4-bitnu prezentaciju broja -5
x = 510 pa je x = 01012
sa N = 4:
x* = 2N − x = 24 − 510 = 100002 − 01012=10112
Proračun može biti urađen kompletno u dekadnom sistemu, konvertujući u binarni sistem na samom kraju.
x* = 2N − x = 24 − 510 = 1110 = 10112
Prečica za ručnu konverziju binarnog broja u njegov komplement dvojke je započinjenje kodnajmanje važnog bita (LSB) i kopiranje svihnula (radeći od LSB prema MSB) sve dok se ne dođe do prve jedinice; ta jedinica se kopira, a preostali bitovi se invertuju (Ostavite MSB kao 1 ako je inicijalni broj bio u sign-and-magnitude prezentaciji). Ova prečica nam omogućuje da pretvorimo broj u njegov komplement dvojke bez prethodnog pravljenja njegovog komplementa jedinice. Na primer: komplement dvojke od "0011 1100" je "1100 0100", gde su podvučene cifre koje se ne menjaju opracijom kopiranja (dok je ostatak cifara invertovan).Ukompjuterskoj tehnologiji, ova metoda nije brža od "komplement i dodaj jedan" metode; Obe metode zahtevajusekvencijalni rad sa desna na levo, propagirajući logičke promene. Metoda komplementiranja i dodavanja jedinice može biti ubrzana pomoću standardnog carry look-ahead adder kola; LSB prema MSB metoda može biti ubrzana sličnom logičkom transformacijom.
| Decimalno 7-bitna notacija: | 42 | 1010110 | 1101 0110 |
| 8-bitna notacija: | −42 | 0101010 | 0010 1010 |
Ponavljanje sign bita u 7 i 8 bitnim integerima korišćenjem komplementa dvojke
Pretvaranjem komplementa dvojke nekog broja sa određenim brojem bitova u neki sa više bitova (na primer kopiranje sa 1 bajtne promenljive u dvobajtnu promenljivu), najvažniji bit mora biti ponovljen u svim dodatnim i nižim bitovima. Neki procesori imaju instrukciju da ovo obave u jednoj instrukciji. Na drugimprocesorima mora biti postavljen uslov sa kodom za setovanje relevantnih bitova ili bajtova. Slično, kada je komplement dvojke nekog broja pomeranjeovan na desno, najvažniji bit, koji sadrži informaciju o vrednosti i znaku mora biti očuvan. Kada se pomeranjeuje u levo, 0 ulazi unutra sa desne strane. Ova pravila čuvaju opštu semantiku da leva pomeranjeovanja množe broj sa sva i da desna pomeranjeovanja broj dele sa dva. I pomeranjeovanje i dupliranje preciznosti su važni za neke multiplikacijske algoritme. Može se primetiti da su za razliku od sabiranja i oduzimanja, proširenje preciznosti i desno pomeranjeovanje urađeni na jedan način za označene, a na drugi način za neoznačene brojeve.
Sa samo jednim izuzetkom, počev od bilo kog broja u komplementu dvojke, ukoliko se svi bitovi invertuju i doda 1, dobija se komplement dvojke negativa tog broja. Pozitivna 12 postaje negativna 12, pozitivna 5 postaje negativna 5, nula postaje nula (+overflow), itd.
−128 1000 0000invertovani bitovi 0111 1111dodavanje jedinice 1000 0000Komplement dvojke broja -128 daje isti 8 bitni binarni broj.Komplement dvojke minimalnog broja u opsegu neće imati željeni efekat od negacije broja. Na primer, komplementdvojke od -128 u 8-bitnom sistemu rezultuje istim binarnim brojem. Ovo je zbog toga [to pozitivna vrednost 128 ne može biti predstavljena sa 8-bitnim označenim binarnim brojem.
Sabiranje brojeva u komplementu dvojke ne traži nikakvo posebno procesiranje ako operandi imaju suprotan znak: Znak rezultata je određen automatski. Na primer, sabiranje 15 i -5:
11111 111 (carry) 0000 1111 (15)+ 1111 1011 (−5)================== 0000 1010 (10)
Ovaj process zavisi od ograničavanja na 8 bitnu preciznost; carry na (nepostojeći) deveti najvažniji bit je ignorisan, rezultujući sa aritmetički tačnim 1010.
Poslednja dva bita u carry redu (čitajući sa desna na levo) sadrže vitalne informacije: da li je proračun doneo aritmetički prestup, broj prevelik da bi bio prikazan u binarnom sistemu (u ovom slučaju veći od 8 bita). Stanje prestupa postoji kada su ova poslednja dva bita različita jedan od drugog. Kao što je već navedeno, znak broja je kodiran u najvažnijem bitu rezultata. Drugim rečima, ako su oba leva carry bita (oni sa leve strane na samom vrhu našeg primera) 1 ili su oba 0, rezultat je ispravan; ako si leva dva carry bita "1 0" ili "0 1", pojavio se znak overflowa. XOR operacija nad ovim bitovima može brzo da nam odredi da li postoji uslov prestupa. Na primer, označeno 4-bitno sabiranje 7 i 3:
0111 (carry) 0111 (7)+ 0011 (3)============= 1010 (−6) invalid!
U ovom slučaju, krajnje leva dva (MSB) carry bita su "01", što znači da je došlo do prestupa sabiranja komplementa dvojke. Tako je 10102=1010izvan dozvoljenog opsega od -8 do 7.
Uopšteno, bilo koja dva N-bitna broja mogu biti sabrana bez prestupa, prethodnim proširenjem oba na N+1 bit, i onda ih sabrati kao na primeru. N+1 bit rezultat je dovoljno velik da prikaže bilo koji mogući zbir (N=5 komplement dvojke može da prikaže vrednosti od -16 do 15) pa se prestup nikada neće pojaviti. Onda je moguće, ukoliko se to želi, skratiti rezultat nazad na N bitova čuvajući vrednost ako i samo ako je odbačeni bit ekstenzija odgovarajućeg znaka ostatka rezultujućih bitova. Ovo omogućuje drugi metod detektovanja prestupa koji je ekvivalentan metodi poređenja carry bitova, samo što može biti jednostavniji za primenu u nekim situacijama, jer ne zahteva pristup detaljima sabiranja.
...................................................................................................................
Kompjuteri obično koriste metodu komplementa da bi implementirali oduzimanje. Korišćenje komplementa za oduzimanje je blisko vezano zakorišćenje komplemenata za prikaz negativnih brojeva, jer kombinacija dozvoljava sve znake operanada i rezultata; takođe, direktno oduzimanje radi i sa brojevima komplementa dvojke. Kao i sabiranje, prednost korišćenja komplementa dvojke je u eliminaciji analize znaka operanada kako bi se odredilo da li je neophodno sabiranje ili oduzimanje. Na primer oduzimanje -5 od 15 je u stvari sabiranje 5 i 15. Ovo je skriveno prezentacijom komplementa dvojke:
11110 000 (borrow) 0000 1111 (15)− 1111 1011 (−5) =========== 0001 0100 (20)
Prestup je otkriven na isti način kao i za sabiranje, posmatranjem poslednja dva leva (najvažnija) bita od pozajmice; prestup se pojavio ukoliko su različiti.
Drugi primer je operacija oduzimanja gde je rezultat negativan: 15-35=-20:
11100 000 (borrow) 0000 1111 (15)− 0010 0011 (35) =========== 1110 1100 (−20)
Kao i kod sabiranja, prestup kod oduzimanja može biti izbegnut (ili otkriven posle operacije) povećanjem broja bitova oba ulaza za po jedan bit.
..........................................................................................................................................
Proizvod dva N-bitna broja zahteva 2N bitova da bi sadržao sve moguće vrednosti. Ukoliko je preciznost dva operanda u komplementu dvojke duplirana pre množenja, direktno množenje (odbacujući višak bitova izvan te preciznosti) će dati tačan rezultat.Na primer, uzmimo 6 x -5 = -30. Prvo, preciznost je proširena sa 4 bita na 8. Potom su brojevi pomnoženi, odbacujući bitove iza 8 (prikazanih kao 'x'):
00000110 (6)* 11111011 (−5)============ 110 1100 00000 110000 1100000 11000000 x10000000 xx00000000============ xx11100010
Ovo je vrlo neefikasno; Duplirajući preciznost unapred, sva sabiranja moraju biti duple preciznosti i najmanje duplo više delimičnih proizvoda je potrebno nego za efikasnijealgoritme implementirane u kompjuterima. Neki multiplikacioni algoritmi su projektovani za komplement dvojke, recimoBooth ov multiplikacioni algoritam. Metode za množenje sign-magnitude brojeva ne funkcionišu sa brojevima u komplementu dvojke bez adaptacije. Obično nema problema kada je multiplikant (broj koji se više puta sabira kako bi se dobio proizvod) negativan; Potrebno je tačno postaviti početne bitove proizvoda kada je množilac negativan. Najčešće dve metode zaprilagođenje algoritama kako bi prihvatili brojeve u komplementu dvojke su:
Prvo proverite da da li je množilac negativan. Ako jeste, negirajte oba operanda pre množenja)
Množilac postaje pozitivan pa će algoritam raditi. Pošto su oba operanda negirana, rezultat će još uvek imati tačan znak
Oduzimanje delimičnog proizvoda nastalog od MSB (pseudo znak bit) umesto sabiranja kao drugi delimični proizvodi. Ova metoda zahteva multiplikantovo proširenje znak bita za jednu poziciju, kako bi bio sačuvan za desne pomeranje akcije.[2]
Kao primer druge metode, uzmimo opšti add-and-shift algoritam za množenje. Umesto pomeranjeovanja delimičnih proizvoda na levo kao što se radi sa olovkom i papirom, akumulirani proizvod je pomeren desno, u drugi regitar koji će eventualno držati manje važnu polovinu proizvoda. Pošto se najmanje važni bitovi nisu promenili jednom kada su izračunati, dodavanja mogu biti jednostruke preciznosti akumulirajući u registru ono što će eventualno držati najvažniju polovinu proizvoda. U sledećem primeru, ponovo množeći 6 sa -5, dva registra i proširen bit znaka su podeljeni sa "|":
0 0110 (6) (multiplikant sa proširenim znak bitom)× 1011 (−5) (množilac)=|====|====0|0110|0000 (prvi delimični proizvod (krajnji desni bit je 1)) 0|0011|0000 (pomeranje desno, čuvajući prošireni znak bit) 0|1001|0000 (sabiranje drugog delimičnog proizvoda (sledeći bit je 1)) 0|0100|1000 (pomeranje desno, očuvanje proširenog znak bita) 0|0100|1000 (sabiranje trećeg delimičnog proizvoda: 0 pa nema promene) 0|0010|0100 (pomeranje desno, očuvanje proširenog znak bita) 1|1100|0100 (oduzimanje poslednjeg delimičnog proizvoda jer je od znak bita) 1|1110|0010 (pomeranje desno, očuvanje proširenog znak bita)
|1110|0010 (odbacivanje proširenog znak bita, davanje konačnog odgovora, -30)
Podaci na Vikipodacima