Komplemen dua

Komplemen dua adalah metode paling umum untuk merepresentasikan bilangan bertanda (positif, negatif, dan nol) bilangan bulat pada komputer,^[1] dan secara lebih umum, nilai biner titik tetap. Seperti pada sistem Komplemen satu dan Tanda-magnitudo, komplemen dua menggunakan Bit paling signifikan sebagai tanda untuk menunjukkan bilangan positif (0) atau negatif (1), dan bilangan tak-negatif diberikan representasi tak bertanda (6 adalah 0110, nol adalah 0000); tetapi, dalam komplemen dua, bilangan negatif direpresentasikan dengan mengambil Komplemen bit dari magnitudonya lalu menambahkan satu (−6 adalah 1010). Jumlah bit dalam representasi dapat ditingkatkan dengan menambahkan semua bit tinggi tambahan dari bilangan negatif atau positif dengan 1 atau 0 masing-masing, atau dikurangi dengan menghapus 1 atau 0 terdepan tambahan.

Berbeda dengan skema Komplemen satu, skema komplemen dua hanya memiliki satu representasi untuk nol, dengan ruang untuk satu bilangan negatif tambahan (rentang bilangan 4-bit adalah −8 hingga +7). Selain itu, implementasi aritmetika yang sama dapat digunakan pada bilangan bulat bertanda maupun tak bertanda,^[2] dan hanya berbeda dalam situasi Luapan bilangan bulat, karena jumlah representasi bilangan positif dan negatifnya adalah 0 (dengan bit carry diset).

Prosedur

Berikut prosedur untuk memperoleh representasi komplemen dua dari suatu bilangan negatif dalam digit biner:

Langkah 1: mulai dengan representasi biner absolut dari bilangan, dengan bit awal sebagai bit tanda;^[3]
Langkah 2: balikkan (atau ubah) semua bit – setiap 0 menjadi 1, dan setiap 1 menjadi 0;
Langkah 3: tambahkan 1 ke seluruh bilangan yang sudah dibalik, abaikan luapan. Memperhitungkan luapan akan menghasilkan nilai yang salah.

Sebagai contoh, untuk menghitung bilangan −6 dalam biner dari bilangan 6:

Langkah 1: +6 dalam desimal adalah 0110 dalam biner; bit signifikan paling kiri (0 pertama) adalah tanda (hanya 110 dalam biner akan menjadi −2 dalam desimal).
Langkah 2: balik semua bit dalam 0110, menghasilkan 1001.
Langkah 3: tambahkan nilai tempat 1 ke bilangan yang dibalik 1001, menghasilkan 1010.

Untuk memverifikasi bahwa 1010 memang bernilai −6, jumlahkan nilai tempatnya, tetapi kurangi nilai tanda dari perhitungan akhir. Karena nilai paling signifikan adalah nilai tanda, maka harus dikurangkan untuk menghasilkan hasil yang benar: 1010 = −(1×2³) + (0×2²) + (1×2¹) + (0×2⁰) = 1×−8 + 0 + 1×2 + 0 = −6.

Bits:	1	0	1	0
Nilai bit desimal:	−8	4	2	1
Perhitungan biner:	−(1×2³)	(0×2²)	(1×2¹)	(0×2⁰)
Perhitungan desimal:	−(1×8)	0	1×2	0

Perhatikan bahwa langkah 2 dan 3 bersama-sama merupakan metode yang valid untuk menghitung Invers aditif $-n$ dari bilangan bulat (positif atau negatif) $n$ di mana input dan output keduanya dalam format komplemen dua. Alternatif untuk menghitung $-n$ adalah menggunakan pengurangan $0-n$ . Lihat di bawah untuk pengurangan bilangan bulat dalam format komplemen dua.

Teori

Komplemen dua adalah contoh dari komplemen basis. “Dua” dalam namanya mengacu pada bilangan $2 N$ – "dua pangkat N", yang merupakan nilai acuan terhadap mana komplemen dihitung dalam sistem $N$ -bit (satu-satunya kasus di mana tepat menghasilkan “dua” adalah $N = 1$ , untuk sistem 1-bit, tetapi ini tidak memiliki kapasitas untuk tanda dan nol). Dengan demikian, definisi tepat dari komplemen dua dari bilangan $N$ -bit adalah komplemen bilangan itu terhadap $2 N$ .

Sifat utama dari “komplemen terhadap $2 N$ ” adalah bahwa penjumlahan bilangan ini dengan bilangan asalnya menghasilkan $2 N$ . Misalnya, menggunakan biner hingga tiga bit ( $N = 3$ dan $2 N = 2 3 = 8 = 1000 2$ , di mana '₂' menunjukkan representasi biner), komplemen dua dari bilangan 3 ( $0112$ ) adalah 5 ( $1012$ ), karena jika dijumlahkan dengan bilangan asalnya memberikan $23 = 1000 2 = 011 2 + 101 2$ . Ketika korespondensi ini digunakan untuk merepresentasikan bilangan negatif, hal ini berarti bahwa ruang bilangan 0 sampai 7 dibagi dua: empat bilangan pertama (0–3) tetap sama, sementara empat sisanya mewakili bilangan negatif, dengan urutan yang sama, sehingga 4 mewakili −4, 5 mewakili −3, 6 mewakili −2, dan 7 mewakili −1. Representasi biner juga memiliki kegunaan tambahan, karena bit paling signifikan menunjukkan kelompok (dan tanda): 0 untuk kelompok bilangan tak-negatif pertama, dan 1 untuk kelompok negatif kedua. Tabel di bawah menunjukkan sifat ini.

Bilangan bulat tiga-bit
Bit	Nilai tak bertanda	Nilai bertanda (Komplemen dua)
000	0	0
001	1	1
010	2	2
011	3	3
100	4	−4
101	5	−3
110	6	−2
111	7	−1

Bilangan bulat delapan-bit
Bit	Nilai tak bertanda	Nilai bertanda (Komplemen dua)
0000 0000	0	0
0000 0001	1	1
0000 0010	2	2
0111 1110	126	126
0111 1111	127	127
1000 0000	128	−128
1000 0001	129	−127
1000 0010	130	−126
1111 1110	254	−2
1111 1111	255	−1

Perhitungan komplemen dua biner dari bilangan positif pada dasarnya berarti mengurangkan bilangan itu dari $2 N$ . Namun, seperti pada contoh tiga-bit dan empat-bit $10002$ ( $23$ ), bilangan $2 N$ sendiri tidak dapat direpresentasikan dalam sistem terbatas $N$ bit, karena berada tepat di luar ruang $N$ bit (bilangan ini tetap menjadi titik acuan dari "komplemen dua" dalam sistem $N$ -bit). Karena itu, sistem $N$ -bit harus memecah pengurangan menjadi dua operasi: pertama kurangi dari bilangan maksimum dalam sistem $N$ -bit, yaitu $2 N -1$ (bilangan ini dalam biner merupakan bilangan sederhana yang terdiri dari 'semua 1', dan pengurangan dari bilangan tersebut dapat dilakukan hanya dengan membalik semua bit, yang juga dikenal sebagai operasi bitwise NOT), lalu tambahkan satu. Kebetulan, bilangan antara sebelum penambahan satu ini juga digunakan dalam ilmu komputer sebagai metode lain dari representasi bilangan bertanda dan disebut Komplemen satu (disebut demikian karena penjumlahan bilangan seperti itu dengan bilangan asal menghasilkan 'semua 1').

Dibandingkan dengan sistem lain untuk merepresentasikan bilangan bertanda (misalnya Komplemen satu), komplemen dua memiliki keunggulan karena operasi aritmetika dasar Penjumlahan, Pengurangan, dan Perkalian identik dengan bilangan biner tak bertanda (selama input diwakili dalam jumlah bit yang sama dengan output, dan setiap luapan di luar bit tersebut dibuang dari hasilnya). Sifat ini membuat sistem lebih mudah diimplementasikan, terutama untuk aritmetika presisi tinggi. Selain itu, tidak seperti sistem komplemen satu, komplemen dua tidak memiliki representasi untuk nol negatif, sehingga bebas dari kesulitan yang terkait dengannya. Jika tidak, kedua skema memiliki sifat yang diinginkan bahwa tanda bilangan bulat dapat dibalik dengan mengambil komplemen dari representasi binernya, tetapi komplemen dua memiliki satu pengecualian – bilangan negatif terkecil, seperti terlihat pada tabel.^[4]

Sejarah

Metode komplemen telah lama digunakan untuk melakukan pengurangan dalam mesin hitung dan kalkulator mekanik desimal. John von Neumann menyarankan penggunaan representasi biner komplemen dua dalam proposal tahun 1945-nya First Draft of a Report on the EDVAC untuk komputer digital berbasis program tersimpan.^[5] EDSAC tahun 1949, yang terinspirasi dari First Draft tersebut, menggunakan representasi komplemen dua untuk bilangan bulat biner negatif.

Banyak komputer awal, termasuk CDC 6600, LINC, PDP-1, dan UNIVAC 1107, menggunakan notasi Komplemen satu; turunan dari UNIVAC 1107, yaitu Seri UNIVAC 1100/2200, terus menggunakannya. Mesin ilmiah Seri IBM 700/7000 menggunakan notasi tanda-magnitudo, kecuali untuk register indeks yang menggunakan komplemen dua. Komputer komersial awal yang menyimpan nilai negatif dalam bentuk komplemen dua termasuk English Electric DEUCE (1955) dan Digital Equipment Corporation PDP-5 (1963) serta PDP-6 (1964). System/360, yang diperkenalkan pada 1964 oleh IBM, kemudian menjadi representasi biner paling luas digunakan dalam industri komputer. PDP-8 yang diperkenalkan pada 1965, menggunakan aritmetika komplemen dua, demikian juga Data General Nova tahun 1969, PDP-11 tahun 1970, dan hampir semua komputer mini serta mikrokomputer sesudahnya.

Lihat pula

Komplemen satu, konvensi bilangan biner alternatif
Algoritma pembagian, termasuk pembagian pemulihan dan tanpa pemulihan dalam representasi komplemen dua
Offset binary
Bilangan p-adik
Metode komplemen, generalisasi ke basis bilangan lain, digunakan pada kalkulator mekanik

Referensi

↑ "Signed integers are two's complement binary values that can be used to represent both positive and negative integer values", Bagian 4.2.1 dalam Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1: Basic Architecture, November 2006
↑ Bergel, Alexandre; Cassou, Damien; Ducasse, Stéphane; Laval, Jannik (2013). Deep into Pharo (PDF). hlm. 337.
↑ "Two's Complement" (PDF). University of Rochester Academic Success Center.
↑ Lilja, David J.; Sapatnekar, Sachin S. (2005). Designing Digital Computer Systems with Verilog. Cambridge University Press. ISBN 9780521828666.
↑ von Neumann, John (1945), First Draft of a Report on the EDVAC (PDF), diakses tanggal 20 Februari 2021

Bacaan lanjutan

Penjelasan Komplemen Dua (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.

Pranala luar

Simulator pengali array komplemen dua berbasis JavaScript

[1] "Signed integers are two's complement binary values that can be used to represent both positive and negative integer values", Bagian 4.2.1 dalam Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1: Basic Architecture, November 2006

[2] Bergel, Alexandre; Cassou, Damien; Ducasse, Stéphane; Laval, Jannik (2013). Deep into Pharo (PDF). hlm. 337.

[3] "Two's Complement" (PDF). University of Rochester Academic Success Center.

[4] Lilja, David J.; Sapatnekar, Sachin S. (2005). Designing Digital Computer Systems with Verilog. Cambridge University Press. ISBN 9780521828666.

[von_Neumann_1945-5] von Neumann, John (1945), First Draft of a Report on the EDVAC (PDF), diakses tanggal 20 Februari 2021

[1]

[2]

[3]

[4]

[5]