Bilangan Bertanda

Semua data di dalam prosesor hanyalah pola bit tanpa tanda, sehingga bilangan negatif perlu disepakati dalam bentuk pola tertentu. Topik ini membahas komplemen dua (two’s complement), representasi bilangan bertanda yang dipilih hampir semua prosesor modern. Pembahasan bergerak dari gagasan bit tanda beserta kelemahannya, komplemen satu, hingga alasan komplemen dua menang. Rentang n bit dinyatakan dalam rumus, deteksi overflow (hasil meluber keluar rentang) dijelaskan dengan contoh 4 bit, dan seluruh konversinya diperagakan dalam kode Python yang memperlakukan bit sebagai data.

Bit tanda dan masalahnya#

Cara paling intuitif menyimpan tanda adalah menyisihkan satu bit untuk itu, dan bit itu disebut bit tanda (sign bit). Pada skema tanda-magnitudo (sign-magnitude), bit tanda bernilai 0 untuk positif dan 1 untuk negatif, sedangkan bit sisanya menyatakan besarnya bilangan. Dengan lebar 4 bit, +5 menjadi 0101 dan -5 menjadi 1101. Skema ini mudah dibaca manusia, tetapi menyimpan dua masalah yang mahal bagi perangkat keras.

Masalah pertama adalah nol ganda. Pola 0000 dan 1000 keduanya bernilai nol menurut tanda-magnitudo, sehingga perbandingan dengan nol harus menangani dua pola yang berbeda. Masalah kedua lebih serius, yaitu penjumlah biner biasa langsung salah pada representasi ini. Penjumlahan 5 dan -5, yaitu 0101 + 1101, menghasilkan 0010 dengan carry, padahal jawaban yang benar adalah 0000. Agar benar, rangkaian harus membandingkan tanda dan magnitudo kedua operand lebih dahulu, lalu memilih penjumlahan atau pengurangan, dan logika tambahan semacam itu mahal.

Tabel di atas merangkum perbedaan kedua skema pada contoh yang sama. Kolom komplemen dua memperlihatkan satu pola untuk nol, dan pola 1000 yang tadinya menyandikan -0 justru dialihkan menjadi -8, satu nilai negatif tambahan di tepi rentang.

Komplemen satu dan komplemen dua#

Komplemen satu (one’s complement) memperbaiki sebagian masalah dengan aturan yang sederhana, yaitu menyalin pola bilangan positif lalu membalik semua bitnya untuk bilangan negatif. Dengan aturan ini, -5 pada 4 bit menjadi 1010, kebalikan persis dari 0101. Penjumlahan campuran pun sebagian besar benar, dengan syarat carry keluar tingkat terakhir dikembalikan ke bit terendah, langkah yang dikenal sebagai end-around carry.

Komplemen dua melangkah satu langkah lebih jauh, yaitu komplemen satu yang ditambah satu. Pola -5 pada 4 bit menjadi 1010 + 1 = 1011. Langkah tambahan itu menghilangkan nol ganda karena hanya 0000 yang berarti nol, dan carry keluar tingkat terakhir boleh langsung dibuang tanpa dikembalikan. Yang terpenting, penjumlah biner biasa langsung benar untuk campuran operand positif dan negatif, sehingga tidak diperlukan rangkaian pengurang terpisah.

def negasi(bits):
    balik = [1 - b for b in bits]   # komplemen satu: semua bit dibalik
    hasil = []
    carry = 1                        # komplemen dua: tambah satu lewat carry
    for b in balik:
        hasil.append(b ^ carry)
        carry = carry & b
    return hasil

Penambahan satu pada fungsi di atas memakai perambatan carry yang sama dengan penjumlah biner. Bit pertama yang bernilai 0 berubah menjadi 1 dan perambatan berhenti di situ, sedangkan deretan bit 1 yang panjang membuat carry berjalan sampai ujung. Dengan dua langkah balik dan tambah itu, negasi bilangan apa pun dihitung langsung pada pola bitnya, tanpa membaca nilai bilangannya.

Mengapa komplemen dua menang#

Tiga keunggulan menjelaskan dominasi komplemen dua pada prosesor. Pertama, nol punya tepat satu pola, sehingga pengujian kesamaan dengan nol menjadi perbandingan bit biasa. Kedua, penjumlahan dan pengurangan memakai rangkaian yang sama, karena a - b dihitung sebagai a ditambah negasi b. Satu adder melayani keduanya, dan tidak ada pembanding tanda yang perlu ditambahkan. Ketiga, rentangnya asimetris, dan asimetri itu justru konsekuensi wajar dari satu nol pada jumlah pola yang selalu genap.

Nilai sebuah pola n bit dibaca dengan memberi bobot negatif pada bit tandanya:

Rentang nilai yang terwakili dapat dibaca langsung dari bobot itu:

Pada lebar 8 bit, rentangnya -128 sampai 127. Sisi negatif memuat satu nilai lebih banyak daripada sisi positif karena pola 10000000 menyandikan -128 tanpa pasangan positifnya. Asimetri ini bukan cacat desain, melainkan akibat pasti dari satu nol dan jumlah pola yang genap. Banyaknya nilai tetap sama dengan banyaknya pola, yaitu $2^n$, karena setiap pola mewakili tepat satu nilai tanpa pola sisa.

Deteksi overflow pada penjumlahan bertanda#

Overflow terjadi apabila hasil penjumlahan bilangan bertanda jatuh di luar rentang yang terwakili. Pada lebar 4 bit, 7 + 1 melebihi batas atas 7, dan pola hasilnya 1000 yang justru terbaca -8. Untuk aritmetika tanpa tanda, kejadian serupa hanya berarti carry keluar yang wajar. Carry dan overflow karenanya menjawab pertanyaan yang berbeda dan wajib dibedakan sejak perancangan.

Deteksi overflow tidak memerlukan pemeriksaan nilai operand, cukup dua carry terakhir. Misalkan $c_{n-1}$ adalah carry masuk ke bit tanda dan $c_n$ adalah carry keluar dari bit tanda. Keduanya berbeda tepat ketika hasil meluber, sehingga berlaku:

Contoh 4 bit pada 0111 + 0001 menunjukkan cara kerjanya. Tiga bit rendah melahirkan carry yang masuk ke bit tanda, sehingga $c_3 = 1$, sedangkan carry keluar dari bit tanda bernilai $c_4 = 0$. Nilai $V = 1 \oplus 0 = 1$ melaporkan overflow. Sebagai pembanding, 0011 + 0010 menghasilkan $c_3 = 0$ dan $c_4 = 0$, sehingga $V = 0$ dan hasil 0101 sah.

Peristiwa melompat antara dua ujung rentang semacam itu disebut lilitan rentang, dan terlihat jelas pada lingkaran pola 4 bit berikut. Menambah satu pada 0111 melompat ke 1000, sedangkan menambah satu pada 1111 kembali ke 0000. Tepi lingkaran itulah yang dilintasi ketika overflow terjadi.

Konversi bolak-balik dalam kode#

Implementasi berikut mengubah bilangan desimal bertanda menjadi bit komplemen dua 8 bit dan membacanya kembali. Untuk bilangan negatif, jalurnya persis definisinya, yaitu ambil nilai mutlak, balik semua bit, lalu tambah satu. Pembacaan kembali memberi bobot negatif pada bit tanda. Konversi ke dan dari desimal hanya melayani tampilan, sedangkan mekanisme representasinya murni operasi bit.

Fungsi ke_bit_tanda memisahkan dua jalur masukan, yaitu bilangan positif yang langsung diambil bit demi bit dan bilangan negatif yang melewati tiga tahap negasi. Fungsi tambah_satu berperan sebagai penjumlah satu dengan carry awal 1, sedangkan dari_bit_tanda memberi bobot pada setiap bit lalu mengurangi $2^{8}$ apabila bit tanda menyala. Fungsi tambah mengembalikan tiga nilai sekaligus, yaitu hasil, carry akhir, dan carry masuk ke bit tanda, karena pasangan carry terakhir itulah bahan baku rumus V.

"""Konversi bilangan bertanda dan komplemen dua 8 bit.

Bit disimpan sebagai daftar 0/1 dengan bit paling rendah di indeks 0.
Encoding dan decoding memakai operasi bit, bukan format bawaan Python.
"""

LEBAR = 8


def ke_bit_tanda(n, lebar=LEBAR):
    """Mengubah bilangan bertanda menjadi bit komplemen dua (bit rendah di indeks 0)."""
    if n < 0:
        mutlak = -n
        bit = [(mutlak >> i) & 1 for i in range(lebar)]
        balik = [1 - b for b in bit]      # komplemen satu
        return tambah_satu(balik)         # komplemen dua
    return [(n >> i) & 1 for i in range(lebar)]


def tambah_satu(bits):
    """Menambah satu pada deretan bit melalui perambatan carry."""
    hasil = []
    carry = 1
    for b in bits:
        hasil.append(b ^ carry)
        carry = carry & b
    return hasil


def dari_bit_tanda(bits):
    """Membaca deretan bit komplemen dua sebagai bilangan bertanda (untuk tampilan)."""
    nilai = 0
    for i in range(len(bits) - 1, -1, -1):
        nilai = (nilai << 1) | bits[i]
    if bits[-1] == 1:                     # bit tanda menyala
        nilai -= 1 << len(bits)           # bobot negatif 2^lebar pada bit tanda
    return nilai


def tampil(bits):
    """Menampilkan daftar bit dalam urutan baca, bit tertinggi di kiri."""
    return "".join(str(b) for b in reversed(bits))


def tambah(a_bits, b_bits):
    """Penjumlah biner: mengembalikan hasil, carry akhir, dan carry masuk bit tanda."""
    hasil = []
    carry = 0
    carry_tanda = 0
    for i in range(len(a_bits)):
        carry_tanda = carry
        s = a_bits[i] ^ b_bits[i] ^ carry
        carry = (a_bits[i] & b_bits[i]) | (carry & (a_bits[i] ^ b_bits[i]))
        hasil.append(s)
    return hasil, carry, carry_tanda


if __name__ == "__main__":
    print("Konversi bolak-balik komplemen dua 8 bit:")
    for n in (5, -5, -1, 127, -128):
        bits = ke_bit_tanda(n)
        kembali = dari_bit_tanda(bits)
        print(f"  {n:>4} -> {tampil(bits)} -> {kembali:>4}")

    print()
    print("Tahap negasi -5:")
    mutlak = [(5 >> i) & 1 for i in range(LEBAR)]
    satu = [1 - b for b in mutlak]
    dua = tambah_satu(satu)
    print(f"  mutlak 5       = {tampil(mutlak)}")
    print(f"  komplemen satu = {tampil(satu)}")
    print(f"  komplemen dua  = {tampil(dua)}")

    print()
    print("Penjumlahan 8 bit dengan deteksi overflow:")
    for a, b in ((100, 50), (40, 60), (-128, -1)):
        hasil, carry, ct = tambah(ke_bit_tanda(a), ke_bit_tanda(b))
        v = ct ^ carry
        status = "overflow" if v else "valid"
        print(f"  {a:>4} + {b:>4} = {tampil(hasil)} terbaca {dari_bit_tanda(hasil):>4}  (V={v}, {status})")

Konversi bolak-balik komplemen dua 8 bit:
     5 -> 00000101 ->    5
    -5 -> 11111011 ->   -5
    -1 -> 11111111 ->   -1
   127 -> 01111111 ->  127
  -128 -> 10000000 -> -128

Tahap negasi -5:
  mutlak 5       = 00000101
  komplemen satu = 11111010
  komplemen dua  = 11111011

Penjumlahan 8 bit dengan deteksi overflow:
   100 +   50 = 10010110 terbaca -106  (V=1, overflow)
    40 +   60 = 01100100 terbaca  100  (V=0, valid)
  -128 +   -1 = 01111111 terbaca  127  (V=1, overflow)

Keluaran di atas memperlihatkan tiga hal sekaligus. Konversi bolak-balik kembali ke nilai asal untuk semua contoh, termasuk tepi rentang -128 dan 127. Tahap negasi -5 memperlihatkan pola 00000101, 11111010, lalu 11111011, sesuai definisi komplemen satu yang ditambah satu. Baris penjumlahan menunjukkan V=1 pada pasangan 100 + 50 dan -128 + -1, dengan hasil yang terbaca sebagai nilai lain karena meluber.

Kesalahan umum#

Tiga kesalahan berikut muncul berulang kali ketika komplemen dua baru dipraktikkan. Ketiganya berakibat hasil yang diam-diam salah tanpa pesan error apa pun.

• Menganggap carry sama dengan overflow. Keduanya dihitung dari jalur carry yang sama tetapi menjawab pertanyaan berbeda, sehingga memakai carry sebagai sinyal overflow pada aritmetika bertanda menghasilkan deteksi yang keliru. Gunakan rumus $V = c_{n-1} \oplus c_{n}$ khusus untuk kasus bertanda.
• Mengasumsikan rentang simetris. Pola 10000000 pada 8 bit adalah -128, dan negasinya tetap -128 karena +128 tidak muat. Kode yang memnegasi nilai tanpa memeriksa tepi rentang akan gagal diam-diam pada nilai terkecil. Pengujian dengan tepi rentang, yaitu -128 dan 127, menangkap kesalahan semacam ini dengan biaya yang murah.
• Melebar tanpa menyalin tanda. Menambah nol di depan pada bilangan negatif mengubah nilainya, karena 1100 yang terbaca -4 pada 4 bit menjadi 12 pada 8 bit apabila diisi 00001100. Perluasan tanda (sign extension) wajib mengulang bit tanda, sehingga 1100 menjadi 11111100. Kebalikannya juga perlu diwaspadai, karena menyempitkan bilangan bertanda tanpa memeriksa bit yang dibuang mengubah nilai dengan cara yang sama.

Ringkasan#

• Komplemen dua menandai bilangan negatif dengan bobot negatif pada bit tanda, sehingga nol tunggal dan penjumlah biner biasa tetap berlaku.
• Pengurangan dihitung sebagai penjumlahan terhadap negasi, yaitu balik semua bit lalu tambah satu, sehingga satu adder melayani keduanya.
• Rentang n bit adalah $-2^{n-1}$ sampai $2^{n-1} - 1$, dengan satu nilai negatif lebih banyak daripada sisi positifnya.
• Overflow dideteksi dari $V = c_{n-1} \oplus c_{n}$, sedangkan carry hanya bermakna bagi aritmetika tanpa tanda.

Referensi#

• Computer Systems: A Programmer’s Perspective — Carnegie Mellon — Membahas representasi komplemen dua, rentangnya, dan deteksi overflow pada bab aritmetika bilangan bulat.
• RISC-V Instruction Set Manual — RISC-V International — Menetapkan aritmetika komplemen dua sebagai dasar operasi bertanda pada ISA RV32I.