Unsigned Encodings
Section ini menjawab satu pertanyaan: kalau kita punya deretan angka 0 dan 1, bagaimana cara membacanya sebagai satu bilangan biasa?
Plus satu jaminan tambahan: pembacaan itu unik dan bisa dibalik.
Itu saja isinya. Sisanya cuma cara menuliskannya secara rapi.
Bagian 1: Membangun idenya dari nol
Langkah 0: Ingat dulu cara kerja angka desimal
Sebelum masuk biner, kita ulang dulu sesuatu yang sudah kita pakai sejak kecil tanpa sadar.
Ambil angka 507. Kenapa dia bernilai lima ratus tujuh?
Karena tiap posisi digit punya nilai tempat sendiri:
5 0 7
| | |
100 10 1 <- nilai tempat tiap posisi
Lalu kita kalikan dan jumlahkan:
5 x 100 = 500
0 x 10 = 0
7 x 1 = 7
-----
507
Perhatikan pola nilai tempatnya: 1, 10, 100, 1000 — naik sepuluh kali lipat tiap geser satu posisi ke kiri. Karena itu namanya sistem basis 10.
Catatan: Inti yang perlu dibawa ke langkah berikutnya: angka itu bukan sekadar deretan simbol. Tiap posisi punya bobot, dan nilai totalnya adalah jumlah dari digit dikali bobotnya.
Langkah 1: Biner memakai ide yang sama persis
Biner bekerja dengan cara yang sama. Yang berubah cuma dua hal:
- Digitnya cuma boleh 0 atau 1 (bukan 0 sampai 9)
- Nilai tempatnya naik dua kali lipat, bukan sepuluh kali lipat
Jadi nilai tempatnya jadi seperti ini:
... 8 4 2 1
Atau kalau ditulis sebagai pangkat dua:
... 2^3 2^2 2^1 2^0 ... 8 4 2 1
Tip: Kalau lupa, tinggal mulai dari 1 di paling kanan lalu kalikan dua terus ke kiri: 1, 2, 4, 8, 16, 32, 64, 128, ...
Langkah 2: Cara menomori posisi bit
Ini bagian yang bikin orang tersesat kalau kelewat, jadi pelan-pelan.
Buku menomori bit dari kanan, dimulai dari nol.
posisi: 3 2 1 0
| | | |
bit: [ 1 0 1 1 ]
| |
| +--- ini x_0, bit paling kanan
+--------------------- ini x_3, bit paling kiri
Jadi untuk vektor bit selebar w bit, penulisannya:
[ x_(w-1), x_(w-2), ... , x_1, x_0 ]
Buku juga memakai lambang x bertanda panah di atasnya untuk menyebut seluruh vektor sekaligus, sementara x_i menyebut satu bit tertentu.
Nomor posisi dihitung dari kanan dan dimulai dari 0, bukan dari kiri dan bukan dimulai dari 1. Kalau ini kebalik, semua rumus di sisa bab akan menghasilkan angka yang salah. Alasan penomorannya begitu: supaya nomor posisi langsung sama dengan pangkat duanya — posisi 3 bernilai 2 pangkat 3.
Langkah 3: Aturannya cuma satu kalimat
Sekarang aturan intinya:
- Kalau sebuah bit bernilai 1, dia menyumbang nilai tempatnya. Kalau bernilai 0, dia tidak menyumbang apa-apa.
Bayangkan tiap posisi bit sebagai saklar lampu yang punya harga tetap:
saklar 8 saklar 4 saklar 2 saklar 1
[ ] [ ] [ ] [ ]
Menyalakan saklar berarti membayar harganya. Nilai akhirnya adalah total harga saklar yang menyala.
Bagian 2: Rumus resminya
Langkah 4: Membongkar rumus 2.1
Buku menuliskan aturan tadi seperti ini:
w-1
B2U (x) = SUM x . 2^i
w i=0 i
Kelihatan menakutkan, padahal isinya persis kalimat di Langkah 3. Kita bongkar potongan demi potongan:
| Potongan | Artinya dalam bahasa sehari-hari |
|---|---|
B2U |
Singkatan dari binary to unsigned — "dari biner ke tak bertanda" |
w di bawah |
Lebarnya berapa bit |
SUM (lambang sigma) |
"Jumlahkan semuanya" |
i=0 sampai w-1 |
"Untuk tiap posisi, mulai dari posisi 0 sampai posisi terakhir" |
x_i |
Nilai bit di posisi itu, 0 atau 1 |
2^i |
Nilai tempat posisi itu |
x_i . 2^i |
Bit dikali nilai tempatnya — inilah "sumbangan" posisi itu |
Dibaca utuh: untuk tiap posisi bit, kalikan nilai bitnya dengan nilai tempatnya, lalu jumlahkan semuanya.
Catatan: {{{1}}}
Langkah 5: Empat contoh, dikerjakan pelan-pelan
Semua contoh di bawah memakai w = 4, jadi nilai tempatnya: 8, 4, 2, 1.
Contoh 1: [0001]
posisi: 3 2 1 0 bit: 0 0 0 1 nilai tempat: 8 4 2 1 sumbangan: 0 0 0 1
Hitung: 0 + 0 + 0 + 1 = 1
Contoh 2: [0101]
posisi: 3 2 1 0 bit: 0 1 0 1 nilai tempat: 8 4 2 1 sumbangan: 0 4 0 1
Hitung: 0 + 4 + 0 + 1 = 5
Contoh 3: [1011]
posisi: 3 2 1 0 bit: 1 0 1 1 nilai tempat: 8 4 2 1 sumbangan: 8 0 2 1
Hitung: 8 + 0 + 2 + 1 = 11
Contoh 4: [1111]
posisi: 3 2 1 0 bit: 1 1 1 1 nilai tempat: 8 4 2 1 sumbangan: 8 4 2 1
Hitung: 8 + 4 + 2 + 1 = 15
Ringkasan keempatnya
| Vektor bit | Perhitungan | Hasil |
|---|---|---|
[0001] |
0 + 0 + 0 + 1 | 1 |
[0101] |
0 + 4 + 0 + 1 | 5 |
[1011] |
8 + 0 + 2 + 1 | 11 |
[1111] |
8 + 4 + 2 + 1 | 15 |
Langkah 6: Cara membaca Figure 2.12
Gambar di buku itu sebenarnya cuma cara lain menyajikan tabel di atas.
Tiap posisi bit digambar sebagai batang biru yang panjangnya sesuai nilai tempatnya:
2^3 = 8 |========================|
2^2 = 4 |============|
2^1 = 2 |======|
2^0 = 1 |===|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Lalu tiap vektor bit digambar dengan menyambung batang-batang yang bitnya bernilai 1:
[0001] |===| -> 1 [0101] |============|===| -> 5 [1011] |========================|======|===| -> 11 [1111] |========================|============|======|===| -> 15
Jadi nilai sebuah vektor bit sama dengan total panjang batang yang tersambung. Gambar itu adalah cara menunjukkan penjumlahan tanpa menulis penjumlahan.
Bagian 3: Rentang nilainya
Langkah 7: Yang terkecil dan yang terbesar
Nilai terkecil
Semua saklar mati:
[0000] -> 0 + 0 + 0 + 0 = 0
Jadi nilai terkecil selalu 0. Tidak ada cara membuatnya lebih kecil, karena tidak ada bit yang bisa menyumbang nilai negatif.
Nilai terbesar
Semua saklar menyala:
[1111] -> 8 + 4 + 2 + 1 = 15
Buku memberi nama untuk nilai terbesar ini: UMax_w.
Untuk w = 4:
UMax_4 = 2^4 - 1 = 16 - 1 = 15
Rumus umumnya:
UMax_w = 2^w - 1
Kenapa dikurangi satu
Ini pertanyaan yang wajar dan jawabannya sederhana.
Dengan w bit, ada 2^w pola bit yang mungkin. Untuk w = 4 berarti ada 16 pola: dari [0000] sampai [1111].
Tapi kita mulai menghitung dari 0, bukan dari 1. Jadi:
pola ke-1 -> 0 pola ke-2 -> 1 pola ke-3 -> 2 ... pola ke-16 -> 15
Enam belas pola, tapi angka terbesarnya 15. Karena satu jatah terpakai untuk angka nol.
Tip: Analogi: kalau ada 16 kursi bernomor dan penomoran dimulai dari 0, kursi terakhir bernomor 15, bukan 16. Jumlah kursi dan nomor kursi terakhir memang selalu beda satu.
Tabel untuk lebar yang umum dipakai
| w | Banyak pola (2^w) | UMax_w | Tipe C yang biasa |
|---|---|---|---|
| 4 | 16 | 15 | (nibble) |
| 8 | 256 | 255 | unsigned char / uint8_t
|
| 16 | 65.536 | 65.535 | uint16_t
|
| 32 | 4.294.967.296 | 4.294.967.295 | unsigned int / uint32_t
|
| 64 | sekitar 1,8 x 10^19 | 2^64 - 1 | uint64_t
|
Dengan kedua batas itu, fungsi B2U bisa dinyatakan sebagai pemetaan:
B2U : {0,1}^w -> {0, 1, 2, ... , UMax_w}
w
Dibaca: "B2U mengambil masukan berupa deretan w buah angka 0-atau-1, dan menghasilkan keluaran berupa satu bilangan antara 0 sampai UMax_w."
Bagian 4: Arah sebaliknya dan sifat bijection
Langkah 8: Dari angka kembali ke bit
Kita sudah bisa jalan dari bit ke angka. Sekarang arah baliknya.
Fungsi kebalikan ini dinamai U2B_w (unsigned to binary).
Cara mengerjakannya: metode kurangi dari yang terbesar
Misal kita mau menulis 11 dalam 4 bit.
Langkah A. Tulis nilai tempatnya: 8, 4, 2, 1
Langkah B. Mulai dari yang terbesar. Tanya: "apakah 8 muat di dalam 11?"
8 muat di 11? Ya. -> bit posisi 3 = 1 Sisa: 11 - 8 = 3
Langkah C. Lanjut ke 4.
4 muat di 3? Tidak. -> bit posisi 2 = 0 Sisa tetap: 3
Langkah D. Lanjut ke 2.
2 muat di 3? Ya. -> bit posisi 1 = 1 Sisa: 3 - 2 = 1
Langkah E. Lanjut ke 1.
1 muat di 1? Ya. -> bit posisi 0 = 1 Sisa: 1 - 1 = 0
Hasil: [1011]. Sisanya nol, berarti pas.
Cek balik: 8 + 0 + 2 + 1 = 11 ✓
Langkah 9: Sifat bijection
Sekarang bagian yang paling penting di section ini — dan yang paling gampang dilewat karena kelihatannya cuma teori.
Buku menyatakan sebuah prinsip: fungsi B2U_w adalah bijection.
Apa itu bijection
Istilah matematika untuk fungsi yang jalan dua arah dengan rapi. Definisi dari buku: fungsi f yang memetakan nilai x ke nilai y, dan bisa juga bekerja terbalik, karena untuk setiap y ada tepat satu x yang menghasilkannya.
Dalam konteks kita, artinya dua jaminan sekaligus:
- Jaminan 1
- Tidak ada angka yang punya dua penulisan
- Angka 11 dalam 4 bit hanya bisa ditulis satu cara:
[1011]. Tidak ada pola bit lain yang juga berarti 11.
- Jaminan 2
- Tidak ada pola bit yang tidak berarti apa-apa
- Semua 16 pola pada w = 4 adalah angka yang sah. Tidak ada pola yang terbuang, ilegal, atau tanpa makna.
Analogi sederhana
Bayangkan sebuah kamus dua bahasa yang sempurna:
- tiap kata di bahasa A punya tepat satu terjemahan di bahasa B
- tiap kata di bahasa B punya tepat satu terjemahan balik di bahasa A
- tidak ada kata yang tidak kebagian pasangan
- tidak ada kata yang punya dua arti
Kamus semacam itulah yang disebut bijection. Dan itulah hubungan antara pola bit dan bilangan tak-negatif.
Pola bit Bilangan
(16 pola) (0 sampai 15)
[0000] <------------------> 0
[0001] <------------------> 1
[0010] <------------------> 2
... ...
[1111] <------------------> 15
Tidak ada yang menyilang, tidak ada yang menggantung.
Kenapa jaminan ini perlu disebut
Karena sifat ini tidak otomatis. Ada cara pengkodean lain yang justru gagal memenuhinya.
Contohnya sign-magnitude, yaitu skema di mana bit paling kiri dipakai sebagai tanda. Di skema itu:
[0000] -> +0 [1000] -> -0
Dua pola bit yang berbeda, tapi artinya sama-sama nol. Jaminan 1 langsung gugur. Akibatnya membandingkan dua angka jadi rumit, karena harus ada penanganan khusus untuk kasus nol ganda.
Bagian 5: Latihan mandiri
Kerjakan dulu tanpa melihat jawaban. Semua memakai w = 4.
1. [0110] = ? 2. [1100] = ? 3. [1010] = ? 4. [0111] = ? 5. Tulis 13 dalam 4 bit 6. Tulis 9 dalam 4 bit 7. Berapa UMax untuk w = 6? 8. Ada berapa pola bit yang mungkin untuk w = 6?
Jawaban
1. [0110] = 0 + 4 + 2 + 0 = 6 2. [1100] = 8 + 4 + 0 + 0 = 12 3. [1010] = 8 + 0 + 2 + 0 = 10 4. [0111] = 0 + 4 + 2 + 1 = 7 5. 13 = 8 + 4 + 1 -> [1101] 6. 9 = 8 + 1 -> [1001] 7. UMax_6 = 2^6 - 1 = 63 8. 2^6 = 64 pola
Catatan untuk kerja systems
- Sifat "tidak ada pola ilegal" adalah alasan overflow unsigned di C terdefinisi. Karena setiap hasil setelah dipotong ke w bit pasti jatuh ke pola bit yang sah, standar C bisa menyatakan dengan tegas bahwa hasilnya membungkus (wrap) secara modulo 2^w. Bandingkan dengan integer bertanda, yang overflow-nya justru dinyatakan sebagai undefined behavior.
- UMax muncul terus di kode nyata. Nilai 255, 65535, dan 4294967295 bukan angka acak — semuanya UMax untuk lebar 8, 16, dan 32 bit. Begitu melihat angka-angka itu di log atau di debugger, biasanya ada operasi unsigned yang membungkus.
- Pengurangan unsigned adalah sumber bug klasik. Karena tidak ada nilai negatif dalam encoding ini, ekspresi seperti
0u - 1utidak menghasilkan minus satu melainkan UMax. Bug perbandingan sepertifor (unsigned i = n-1; i >= 0; i--)tidak pernah berhenti, karena kondisii >= 0selalu benar untuk tipe unsigned. - Relevansi ke quantization. Rentang uint8 adalah 0 sampai UMax_8 = 255, tepat 256 level. Sifat bijection itulah yang membuat pemetaan bolak-balik antara nilai real dan level kuantisasi bersih: setiap level punya satu pola bit, dan setiap pola bit adalah level yang sah. Tidak ada pola terbuang yang perlu ditangani khusus.
- Lebar bit adalah parameter, bukan konstanta. Semua rumus di section ini memakai w. Kebiasaan berpikir dalam w, bukan dalam angka 32 atau 64, sangat membantu saat berpindah antara uint8, fp16, dan format kustom di pekerjaan akselerator.
Istilah kunci
- Bit vector
- Deretan bit; ditulis
xbertanda panah untuk keseluruhan, ataux_iuntuk bit di posisi ke-i. - w
- Lebar, yaitu banyaknya bit dalam vektor.
- Nilai tempat
- Bobot sebuah posisi bit, yaitu 2 pangkat nomor posisinya.
- B2U_w
- Fungsi yang memetakan vektor bit selebar w menjadi bilangan tak-negatif.
- U2B_w
- Fungsi kebalikannya, memetakan bilangan menjadi pola bit.
- UMax_w
- Nilai terbesar yang bisa direpresentasikan, yaitu 2^w - 1.
- Bijection
- Fungsi yang berpasangan satu-satu dua arah; tidak ada nilai ganda dan tidak ada yang tidak terpasangkan.