XOR

• XOR adalah operasi yang menghasilkan 1 ketika dua bit berbeda, dan dapat dipahami dengan menghubungkan exclusive OR, tidak sama, inversi bersyarat, serta penjumlahan/pengurangan mod 2 sebagai satu perilaku
• XOR bitwise pada bilangan bulat memproses tiap posisi secara independen untuk menampilkan perbedaan per bit, bertindak seperti penjumlahan biner tanpa carry sambil mempertahankan sifat komutatif, asosiatif, identitas 0, dan invers diri
• Dalam kriptografi, XOR dipakai untuk menggabungkan plaintext dengan keystream; pada grafik piksel masa lalu, menggambar ulang gambar yang sama dapat menghapusnya sehingga mengurangi beban memori dan CPU
• Sifat XOR dimanfaatkan langsung dalam komputasi yang menciptakan perbedaan lalu membatalkannya kembali, seperti identitas half-adder, pertukaran bit, swap XOR tiga kali, dan kondisi menang dalam permainan Nim
• XOR juga terhubung ke selisih simetris himpunan, grup berindeks 2, nim-sum, GF(2), aljabar linear dan polinomial di atasnya, serta teknik deteksi/koreksi kesalahan dan kriptografi seperti Hamming code, CRC, AES, GCM, dan Classic McEliece

---

Makna dasar XOR

• XOR adalah operasi Boolean dengan dua bit input dan satu bit output; tabel kebenarannya adalah 00→0, 01→1, 10→1, 11→0
• Jika dilihat sebagai “exclusive OR”, hasilnya 1 ketika hanya salah satu dari dua input yang benar, dan 0 ketika keduanya benar
• Jika dilihat sebagai “not equals”, a XOR b sama dengan a ≠ b, menghasilkan 1 ketika dua nilai Boolean berbeda
• Jika dilihat sebagai inversi bersyarat, ketika a=0 nilai b dibiarkan apa adanya, dan ketika a=1 nilai b dibalik
  • Dengan alasan yang sama, bisa juga ditafsirkan bahwa b menjadi input kontrol untuk membalik a
• Dari sudut pandang paritas, XOR memberi tahu apakah jumlah input yang bernilai 1 itu ganjil
  • Untuk dua bit, ini sama dengan a+b mod 2
  • Ini juga sama dengan a-b mod 2
  • Jika beberapa nilai di-XOR, kita dapat mengetahui apakah jumlah 1 di seluruh input ganjil atau genap

Sifat aljabar XOR

• XOR memenuhi hukum komutatif dan hukum asosiatif
  • a XOR b = b XOR a
  • (a XOR b) XOR c = a XOR (b XOR c)
  • Dalam daftar XOR yang panjang, urutan dan cara pengelompokan tidak memengaruhi hasil
• 0 adalah elemen identitas XOR
  • a XOR 0 = 0 XOR a = a
  • Dalam daftar XOR yang panjang, 0 boleh dihapus
• Setiap nilai adalah invers dari dirinya sendiri
  • a XOR a = 0
  • Jika variabel yang sama muncul dua kali, kedua suku itu dapat dihapus bersama
  • Seperti (a XOR b) XOR b = a, dari nilai yang sudah tercampur kita bisa menghapus suku yang diketahui dengan meng-XOR-nya sekali lagi

XOR bitwise pada bilangan bulat

• XOR bitwise pada bilangan bulat menempatkan dua bilangan bulat sebagai bilangan biner dan meng-XOR bit pada tiap posisi secara independen
• Sifat XOR satu bit berlaku apa adanya juga pada bilangan bulat
  • a XOR b = b XOR a
  • (a XOR b) XOR c = a XOR (b XOR c)
  • a XOR 0 = a
  • a XOR a = 0
• XOR bitwise memberi tahu perbedaan per bit antara dua bilangan bulat
  • Jika a=b, maka a XOR b = 0
  • Jika a≠b, maka setidaknya satu bit berbeda sehingga a XOR b ≠ 0
  • Bit 1 pada hasil menunjukkan posisi tempat kedua input berbeda
• XOR bitwise juga dapat dilihat sebagai pembalik bit bersyarat
  • Bit data dibalik hanya pada posisi bit 1 dalam nilai kontrol
  • Pada ASCII dan sebagian encoding penerusnya, huruf Latin kapital dan kecil hanya berbeda satu bit, sehingga meng-XOR nilai karakter dengan 32 dapat mengubah kapitalisasi
  • Aturan ini tidak berlaku untuk semua karakter Unicode, dan banyak karakter tidak memiliki konsep huruf besar/kecil atau tidak mengikuti aturan tersebut
• XOR bitwise sama dengan penjumlahan biner tanpa carry
  • Di tiap posisi hanya dilakukan penjumlahan mod 2, tanpa meneruskan carry ke posisi berikutnya

XOR dalam kriptografi

• Dalam kriptografi, digunakan cara membuat keystream dengan panjang yang sama seperti plaintext, lalu menggabungkan byte atau word plaintext dengan keystream untuk membuat ciphertext
• Pada tahap penggabungan ini, XOR umumnya digunakan
  • Penerima dapat memulihkan plaintext asli dengan meng-XOR keystream yang sama sekali lagi
  • Fakta bahwa pengirim dan penerima memakai operasi yang sama juga sedikit lebih praktis
• Cara membuat keystream itu sendiri bisa lebih kompleks
  • One-time pad menggunakan data acak sungguhan sebesar seluruh pesan dan tidak dapat dipecahkan, tetapi sangat tidak praktis untuk sebagian besar tujuan
  • Biasanya stream cipher atau block cipher yang berjalan dalam counter mode membuat keystream sepanjang yang diperlukan dari kunci kecil
• Metode ini dapat menyediakan kerahasiaan jika keystream-nya baik, tetapi tidak menyediakan integritas untuk mendeteksi modifikasi pesan
  • Perlindungan integritas adalah masalah terpisah
  • Menghilangkan integritas adalah kesalahan umum dalam perancangan sistem kriptografi oleh pemula, dan juga menghasilkan akibat yang buruk dalam skema enkripsi yang lebih kompleks
• Dalam hardware, XOR lebih sederhana daripada penjumlahan
  • Penjumlahan membutuhkan propagasi carry antarbit, sehingga memerlukan lebih banyak ruang chip dan waktu
  • XOR tidak memiliki carry, sehingga lebih murah dalam rangkaian khusus

Gambar XOR dan grafik piksel

• Komputer rumahan tahun 1980-an memiliki jumlah bit per piksel layar dan RAM yang terbatas, sehingga sulit menyimpan dua salinan penuh layar
• Jika objek bergerak digambar dengan XOR, layar asli dapat dipulihkan hanya dengan menggambar ulang objek yang sama
  • Nilai piksel S di-XOR dengan piksel objek bergerak M untuk membuat C, lalu kemudian M yang sama di-XOR lagi untuk mengembalikan S
• Pada layar yang beberapa pikselnya dipacked dalam satu byte atau memakai struktur bit plane, komposit berbasis penjumlahan menjadi rumit
  • Penjumlahan biasa dapat membuat carry dari satu piksel masuk ke piksel berikutnya
  • XOR sama sekali tidak memiliki carry, sehingga tidak memiliki masalah ini
• Jika garis digambar dengan XOR, piksel tempat dua garis berpotongan dibalik dua kali dan kembali menjadi warna latar, sehingga bisa terlihat seperti cacat kecil
  • Cacat ini diterima sebagai harga agar saat satu garis dihapus, garis lain tidak ikut rusak
• Gambar XOR juga menguntungkan untuk animasi sederhana
  • Menggambar satu garis baru dan menggambar ulang satu garis lama untuk menghapusnya menghasilkan frame berikutnya
  • Tidak perlu menggambar ulang semua piksel atau semua garis pada layar saat ini, sehingga penggunaan memori dan CPU lebih kecil
  • Teknik ini digunakan pada garis bergerak di game tahun 1981 Qix, serta pada outline pemindahan jendela di GUI awal

Identitas half-adder

• Dalam penjumlahan satu bit, bit rendah dari a+b adalah a XOR b, dan bit tingginya adalah a AND b
• Relasi yang sama juga berlaku untuk operasi bitwise pada bilangan bulat
  • a + b = (a XOR b) + 2 × (a AND b)
  • a XOR b adalah nilai yang dijumlahkan tanpa carry, sedangkan a AND b berisi bit carry yang seharusnya muncul di tiap posisi
• Relasi ini dapat dilihat sebagai identitas half-adder
  • Half-adder hardware membuat carry dan bit rendah dari penjumlahan dua bit dengan gerbang AND dan XOR
  • Ini bukan berarti seluruh penjumlahan bilangan bulat dibuat hanya dari operasi sederhana; tanda + di ruas kanan menyelesaikan propagasi carry
• Identitas ini dapat dipakai ketika menghitung rata-rata dua bilangan bulat tanpa overflow
  • Jika sekadar melakukan a+b lalu shift kanan, bit tertinggi dari jumlah 33-bit bisa hilang
  • Pada CPU yang tidak memiliki carry flag atau instruksi seperti RRX/RCR, atau ketika itu tidak nyaman digunakan, bentuk (a XOR b) >> 1 + (a AND b) menjadi alternatif
  • Sebagai contoh, MIPS, RISC-V, dan DEC Alpha tidak memiliki carry flag, dan Arm Thumb awal tidak menyertakan RRX
• Pada CPU tanpa instruksi XOR, identitas ini dapat dibalik untuk membuat XOR
  • a XOR b = (a + b) − 2 × (a AND b)
  • CPU Data General tahun 1970-an memiliki AND tetapi tidak memiliki bitwise XOR

Pertukaran bit dan nilai

• Masalah menukar dua bit dapat direduksi menjadi: jika dua bit sama, tidak perlu melakukan apa pun; jika berbeda, balik keduanya
• Dengan XOR dan shift, kita dapat menemukan apakah dua bit berbeda dan, jika perlu, membalik kedua posisi
  • diff_all = input XOR (input >> distance) menghitung perbedaan pasangan bit yang berjarak tertentu
  • AND memilih hanya posisi yang diminati
  • Perbedaan yang dipilih disalin ke posisi lain, lalu di-XOR dengan input sehingga kedua bit dibalik hanya jika diperlukan
• Cara yang sama juga dapat dipakai untuk menukar banyak pasangan bit dengan jarak yang sama sekaligus
  • Gunakan mask berisi banyak bit, bukan mask satu bit
  • Beneš network dapat merepresentasikan permutasi arbitrer dengan menukar banyak pasangan berjarak sama dalam beberapa tahap
• Swap XOR tiga kali juga memungkinkan untuk menukar dua nilai secara keseluruhan
  • a = a XOR b
  • b = b XOR a
  • a = a XOR b
  • Dua nilai saling bertukar tanpa variabel sementara
• Swap XOR tiga kali memiliki masalah aliasing
  • Ini berfungsi saat menukar variabel yang berbeda
  • Jika dua nama menunjuk ke lokasi penyimpanan yang sama, seperti menukar sebuah elemen array dengan dirinya sendiri, nilainya bisa menjadi 0

Permainan Nim dan XOR

• Nim adalah permainan dengan beberapa tumpukan; pemain bergiliran memilih satu tumpukan dan menghapus satu atau lebih bidak sebanyak yang diinginkan, dan kalah jika tidak bisa bergerak lagi
• Dalam versi sederhana Nim, posisi kalah adalah posisi ketika XOR bitwise dari semua ukuran tumpukan bernilai 0
• Jika dari posisi dengan XOR 0 ukuran satu tumpukan a diubah menjadi nilai lain b, XOR keseluruhan berubah sebesar a XOR b, dan karena a≠b, hasilnya tidak lagi 0
• Dari posisi dengan XOR tidak nol, lihat bit 1 tertinggi dari nilai XOR keseluruhan x, pilih tumpukan yang memiliki bit tersebut bernilai 1, lalu kurangi ukurannya menjadi pile XOR x untuk membuat XOR keseluruhan menjadi 0
• Sebagai contoh, ukuran tumpukan 12, 10, 3 dalam biner adalah 1100, 1010, 0011, dan XOR-nya adalah 0101
  • Hanya tumpukan terbesar 12 yang berkurang menjadi 9 saat di-XOR dengan 0101
  • Langkah menangnya adalah menghapus 3 dari 12 sehingga menjadi 9

Struktur matematika yang tampak seperti XOR

• Dalam teori himpunan, selisih simetris X∆Y adalah operasi yang memasukkan suatu elemen ketika elemen itu berada tepat di salah satu dari dua himpunan
  • Jika keanggotaan elemen dilihat sebagai nilai Boolean, selisih simetris sama dengan XOR
  • Karena itu, ia berbagi sifat XOR seperti hukum komutatif dan asosiatif
• Dalam teori grup, grup berindeks 2 adalah grup yang semua elemennya merupakan invers dirinya sendiri
  • Operasi grup semacam ini memenuhi hukum asosiatif, dan sebagai latihan standar juga mengikuti hukum komutatif
  • Sifat bahwa dua elemen yang sama saling membatalkan mirip dengan XOR
  • Semua grup berindeks 2 dapat dipahami sebagai bentuk XOR bitwise dari fungsi-fungsi bernilai {0,1}
• Dalam analisis Sprague-Grundy, banyak posisi impartial game diberi Grundy number
  • Grundy number dari composite yang menggabungkan beberapa subgame dihitung sebagai bitwise XOR dari Grundy number tiap game penyusunnya
  • Dalam game theory, bitwise XOR dari bilangan bulat non-negatif juga disebut nim-sum
• Field GF(2) adalah finite field yang hanya memiliki elemen 0 dan 1
  • Penjumlahan dan pengurangan bertindak seperti XOR
  • Perkalian bertindak seperti AND
  • Karena itu, a AND (b XOR c) = (a AND b) XOR (a AND c) berlaku

Aljabar linear di atas GF(2) dan koreksi kesalahan

• Vektor dan matriks di atas GF(2) adalah struktur yang komponennya 0 atau 1, dan penjumlahan vektor atau matriks adalah XOR per komponen
• Mengalikan matriks M dengan vektor v sama dengan menjumlahkan kolom-kolom M yang dipilih oleh komponen 1 dari v menggunakan XOR
• Kode koreksi kesalahan memperluas pesan m bit menjadi codeword n bit yang lebih panjang agar sebagian kesalahan bit dapat dideteksi atau diperbaiki
  • Jika codeword yang valid berbeda satu sama lain pada banyak bit, sedikit kesalahan bit tidak akan mengubahnya menjadi codeword valid lain
  • Jika dua codeword valid berbeda minimal k bit, kesalahan yang kurang dari k dapat dideteksi, dan kesalahan yang kurang dari k/2 dapat diperbaiki dengan mencari codeword terdekat
• Kode linear menggunakan generator matrix dan check matrix di atas GF(2)
  • Sender memperluas pesan m bit menjadi codeword n bit dengan generator matrix
  • Receiver memeriksa apakah codeword yang diterima valid dengan check matrix, dan jika ada kesalahan, memperoleh syndrome
  • Pola kesalahan yang sama menghasilkan syndrome yang sama terlepas dari pesannya
• Hamming code adalah contoh untuk kasus panjang kode n sebesar 2^d−1
  • Jika n=15, posisi 15 bit dinomori dengan angka non-nol 4-bit dari 0001 hingga 1111
  • Receiver meng-XOR semua indeks bit yang bernilai 1; jika hasilnya 0, codeword tersebut valid
  • Jika satu bit terbalik, hasil XOR langsung menjadi indeks bit yang terbalik, sehingga kesalahan 1 bit dapat diperbaiki tanpa lookup table
  • Hamming code 15-bit memuat 11 bit data dan menggunakan 4 bit untuk koreksi kesalahan

Polinomial GF(2), CRC, dan finite field yang lebih besar

• Polinomial di atas GF(2) adalah polinomial formal dengan koefisien 0 atau 1, dan penjumlahannya sama dengan meng-XOR koefisien pada derajat yang sama
• Perkalian polinomial dilakukan seperti polinomial biasa, dengan membuat partial product dan mereduksi koefisien mod 2
  • Jika representasi ini dilihat sebagai bit string, ia mirip dengan perkalian bilangan bulat, tetapi saat menggabungkan partial product digunakan XOR tanpa carry, bukan penjumlahan biasa
  • x86 menyediakan instruksi carryless multiplication termasuk CLMUL, dan Arm menyediakan keluarga instruksi polynomial multiplication
• CRC adalah metode yang menggunakan sisa pembagian polinomial GF(2) sebagai checksum
  • Bit string pesan yang dikirim dilihat sebagai polinomial besar M, lalu sisa M mod P dari pembagian dengan polinomial yang disepakati P dipertahankan
  • Digunakan untuk verifikasi paket jaringan seperti Ethernet
  • CRC tidak memperbaiki kesalahan, hanya mendeteksinya, dan cocok untuk situasi ketika hampir semua transmisi normal, tetapi sesekali terjadi bit flip atau noise
• Finite field yang lebih besar dapat dibuat sebagai struktur sisa pembagian polinomial di atas GF(p) dengan irreducible polynomial Q
  • Jika derajat Q adalah d, finite field baru memiliki p^d elemen
  • Jika p=2, irreducible polynomial dapat ditulis seperti pola bit sebagai bilangan bulat, dan deret tersebut terdaftar di OEIS A014580
• Finite field berukuran pangkat dua muncul dalam berbagai teknik kriptografi
  • Finite field berukuran 2^8 adalah komponen inti AES dan Twofish
  • Finite field berukuran 2^128 digunakan dalam GCM, yang menggabungkan bulk encryption dan integrity protection
  • Finite field berukuran pangkat dua juga muncul dalam sebagian elliptic-curve cryptography serta algoritme decoding Classic McEliece, sebuah metode post-quantum

[GN⁺]

Pendapat Hacker News

• Teknik XOR terkutuk favorit saya adalah XOR doubly linked list: https://en.m.wikipedia.org/wiki/XOR_linked_list
  Alih-alih setiap node menyimpan pointer next/prev secara terpisah, ia menyimpan satu nilai yang merupakan XOR dari keduanya. Tentu saja itu pointer yang tidak valid, tetapi saat melakukan traversal, jika pointer node sebelumnya di-XOR dengan pointer gabungan itu, pointer node berikutnya akan muncul, dan traversal dua arah juga dimungkinkan. Rasanya seperti sesuatu yang ilegal

  • Dibandingkan doubly linked list biasa, saat hanya memiliki alamat item, atau hanya memiliki iterator yang stabil bahkan terhadap penyisipan/penghapusan, kita kehilangan kemampuan untuk menghapus item tersebut. Padahal ini sering menjadi alasan utama memakai doubly linked list
    Kekurangan yang kurang mendasar: menulis XOR linked list dalam C yang benar-benar mengikuti standar itu sangat merepotkan. Standar tidak menjamin bahwa pointer yang sama, ketika di-cast ke integer, akan menjadi integer yang sama, jadi pada praktiknya kita harus membuat semuanya menjadi uintptr_t agar bisa mempertahankan versi cast integer yang ternormalisasi
  • Bahkan pada prosesor 64-bit, jika menganggap sebagian besar aplikasi cukup dengan RAM kurang dari 4GB, ruang penyimpanan bisa dikurangi lagi hanya dengan memakai ruang alamat 32-bit
    Lebih jauh lagi, pointer near/relatif 16-bit mungkin juga memungkinkan. Ini bisa cocok dengan data-oriented design, misalnya dengan blok berisi 64K elemen dan elemen di dalamnya ditunjuk memakai indeks uint16
  • Dengan begini, garbage collector pasti tidak akan menyukainya. Atau setidaknya akan menganggap struktur data ini sebagai sampah
  • Saya penasaran kenapa orang jadi ingin memakai teknik ini
  • Ini tidak jauh berbeda dari menyimpan selisih dua pointer, bukan pointer itu sendiri. Jika menyimpan selisihnya pun, tentu traversal dua arah tetap bisa dilakukan

• Ada yang terlewat. XOR juga merupakan fungsi hash linear independen 3-wise, sehingga bisa dipakai untuk pengambilan sampel hampir seragam secara probabilistik dari solusi fungsi boolean, dan untuk menghitung jumlahnya. Ini sangat berguna, dan dipakai untuk membuat counter yang probabilistik tetapi memberikan hitungan yang terbukti. Penjelasan yang lebih mudah dipahami saya tulis di sini https://www.msoos.org/2018/12/how-approximate-model-counting...
  Pada dasarnya, setiap kali ia mengurangi ruang solusi hampir tepat menjadi separuh. Jadi kita terus menambahkan kondisi XOR sampai, misalnya, tersisa 10 solusi; jika jumlah XOR yang ditambahkan adalah k, cukup kalikan 10 dengan 2^k. Karena setiap kali berkurang separuh, mencapai level sekitar 10 solusi pun cepat, sehingga skalabilitasnya bagus
  Makalah terkait ada di https://arxiv.org/abs/1306.5726 dan https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf, dan alatnya ada di https://github.com/meelgroup/approxmc dan https://github.com/meelgroup/unigen. Dalam kompetisi model counting terakhir, ketika digabungkan dengan counter eksak, ia jauh mengungguli pesaing lain; slide-nya ada di https://mccompetition.org/assets/files/2024/MC2024_awards.pd...

• Salah satu anekdot XOR favorit saya adalah cerita Bryan Cantrill dari Oxide, Joyent, dan Sun dalam presentasi ini https://speakerdeck.com/bcantrill/oral-tradition-in-software... dan video ini https://www.youtube.com/watch?v=4PaWFYm0kEw
  Ringkasnya agar tidak perlu mengeklik tautannya: saat di Sun, ia pernah berbicara dengan koleganya Roger Faulkner tentang mengapa C tidak punya XOR logis. Faulkner mengatakan alasannya karena tidak bisa melakukan short-circuit evaluation, dan Brian merasa itu aneh. Lalu Roger menanyakannya lewat email kepada Dennis Ritchie, dan Ritchie mengonfirmasi bahwa Faulkner benar. Cara Cantrill menceritakannya juga lucu, tetapi yang menakjubkan adalah mereka bisa bertanya langsung kepada orang yang bersangkutan

  • DMR adalah orang yang luar biasa ramah, suka membantu, dan mudah dihubungi. Saat saya mahasiswa S1 pada pertengahan 80-an, setelah membaca tentang kasus “pertama” porting Unix v6 ke Interdata 8/32, bukan PDP-11, saya nekat mengirim email ke [e-mail] untuk menanyakan apakah ada informasi arsitektur lebih lanjut
    Saat itu belum ada Google dan perpustakaan kampus juga tidak punya bahannya, tetapi beberapa hari kemudian ia menanyakan alamat fisik saya, lalu beberapa minggu setelahnya salinan manual ringkasan instruction set tiba di kotak surat. Rasanya seperti keluarga IBM 360, dan saya masih menyimpannya sampai sekarang
  • C memiliki XOR logis, yaitu operator !=. Berbeda dari operator logis lain, argumennya harus dinormalisasi menjadi satu nilai benar, dan ini cocok dengan idiom konversi boolean C !!
  • Saya tidak paham mengapa “karena tidak bisa melakukan short-circuit evaluation” menjadi hambatan untuk menambahkan operator. Semoga ada yang bisa menjelaskan
  • Topik tersebut dimulai pada 37:18
  • C sudah memiliki operator bitwise XOR ^ selama lebih dari 40 tahun: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

• Hari ini saya baru tahu bahwa jika emoji mobil di-XOR dengan 0x20, alias “dibuat huruf kecil”, hasilnya menjadi emoji dilarang pejalan kaki. Rasanya terlalu pas untuk sekadar kebetulan; penasaran apakah ada yang tahu apakah ini disengaja
  Kalau terlalu dipaksakan, orang juga bisa punya gagasan aneh bahwa huruf kecil dari emoji mobil adalah rambu “dilarang pejalan kaki”

  • Untuk menghindari pemroses komentar HN yang menghapus emoji, ini bisa dicek seperti berikut:
    >>> from unicodedata import lookup, name
>>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
'NO PEDESTRIANS'
  • Huruf kecil dari mobil sepertinya go-kart
  • :tada: → :tophat:, :rocket: → :mountain_cableway: juga bisa

• Analogi dunia nyata yang bagus untuk menjelaskan XOR adalah saklar lampu di tangga rumah. Ada satu saklar di bawah, satu saklar di atas, dan keduanya mengendalikan lampu yang sama
  Awalnya keduanya berada di posisi mati, lalu ketika saklar bawah dinyalakan, lampu menyala. Setelah naik tangga dan menyalakan saklar atas, kedua saklar sama-sama berada di posisi “nyala”, tetapi lampunya mati. Lampu hanya menyala ketika satu saklar “nyala” dan yang lain “mati”; selain itu lampu mati

  • Mungkin teknisi listrik di kantor kami salah memasang kabel. Ada dua saklar di ruangan, dan kalau dipikir-pikir perilakunya lebih seperti gerbang AND daripada XOR. Dua saklar di ruang tamu jelas bekerja seperti XOR

• Saya benar-benar tidak suka fungsi logika ini lazim disebut XOR, yaitu “OR eksklusif”. Hampir selalu makna sebenarnya adalah “penjumlahan modulo 2”, alias paritas, bukan OR eksklusif
  “Penjumlahan modulo 2”/paritas dan “OR eksklusif” adalah fungsi logika yang berbeda, dan hanya kebetulan sama ketika operan inputnya ada 2. Itu karena hanya ada satu bilangan ganjil yang kurang dari atau sama dengan 2
  Ketika inputnya 3 atau lebih, apa yang kebanyakan orang sebut XOR sebenarnya adalah paritas, yang bernilai 1 ketika jumlah input yang bernilai 1 adalah ganjil. Sebaliknya, OR eksklusif untuk 3 input atau lebih adalah fungsi yang bernilai 1 hanya ketika tepat satu input bernilai 1 dan sisanya semua 0
  Dalam perangkat keras komputer, paritas jauh lebih penting daripada OR eksklusif. Alasan utamanya adalah penjumlahan modulo 2 dipakai sebagai komponen untuk mengimplementasikan penjumlahan bilangan yang lebih besar. Sebaliknya, dalam matematika, OR eksklusif jauh lebih penting daripada paritas
  Misalnya, kuantor yang menyatakan bahwa suatu predikat benar untuk sebagian elemen, semua elemen, atau satu-satunya elemen dalam sebuah himpunan masing-masing berbasis OR, AND, dan OR eksklusif. “or” dalam bahasa alami selalu berarti OR inklusif atau OR eksklusif, bukan paritas yang oleh banyak programmer disebut XOR
  Dalam pemrograman, jarang ada kebutuhan menghitung fungsi logika OR eksklusif, tetapi ia sering dipakai untuk menjelaskan perilaku program. Misalnya ketika menjelaskan bahwa salah satu dari pernyataan pertama, kedua, atau ketiga dalam konstruksi select/case/switch akan dijalankan, atau ketika menjelaskan tipe yang mungkin dimiliki nilai saat ini dari variabel union/sum type

  • Standar simbol elektroteknik IEC 60617 menangani bagian ini dengan benar. Gerbang XOR ditandai =1, sedangkan gerbang paritas ditandai 2k + 1. Namun ketika memakai perangkat lunak desain rangkaian untuk PCB atau FPGA, Anda tetap bisa terjebak karena mendapatkan sesuatu yang berbeda dari yang diharapkan
  • Yang disebut dalam matematika itu dinamakan kuantor keberadaan unik, dan punya simbol sendiri ∃!
  • Pernyataan bahwa “OR eksklusif” untuk 3 input atau lebih bernilai benar ketika tepat satu saja bernilai 1 membutuhkan dasar
  • Interpretasi ini juga dibahas dalam esai utama

• Ada juga tabel hash terdistribusi Kademlia: kademlia distributed hash table. Gagasan besarnya adalah setiap node mendapat bit acak dalam rentang [0, 2^m), dan jarak didefinisikan dengan XOR. Tujuannya mencari algoritma terdistribusi untuk mengirim informasi dengan cepat dari X ke Y tanpa mengetahui seluruh jaringan
  Secara matematis saja cara kerjanya bisa dibuktikan, tetapi intuisi visual yang saya suka adalah begini. Misalkan node awal X ingin mencari node k. Definisikan “pohon jarak-X” sebagai pohon biner dengan indeks daun 0, 1, 2..., dan setiap daun diberi label X^leaf_index untuk menunjukkan jaraknya dari X. Misalnya karena dist(x, x) = x^x = 0, label node asli X berada di daun paling kiri 0
  Interval [2^i, 2^(i+1)) adalah suatu subpohon dalam pohon jarak-X. Jika diketahui bahwa jarak k berada dalam interval itu, kita menanyai suatu node Y di dalamnya sebagai tetangga perkiraan
  Node Y mana pun yang dipilih, dalam pohon jarak-Y, prefiks hasil selalu menjadi suatu permutasi dari subpohon [2^i, 2^(i+1)) yang dipilih dalam pohon jarak-X. Lebih tepatnya, bisa dilihat sebagai labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)). Indeks didasarkan pada jarak, tetapi label bisa berbeda
  Untuk perbandingan dengan tabel hash terdistribusi lain seperti Chord, ada banyak materi yang jauh lebih ketat secara matematis maupun empiris. Namun intuisi visual ini memberi rasa tentang apa itu “simetri” Kademlia, bahwa setiap orang punya tetangga lokal dan subpohonnya sendiri
  Sebaliknya, Chord meskipun diimplementasikan dua arah memakan memori 2 kali lebih besar, implementasinya tampak lebih berisiko, dan sulit memperoleh tingkat “isolasi” seperti ini. Sliding window tetangga berukuran S selalu bergerak, dan untuk setiap bit ada 2^m tetangga berbeda. Walaupun sebagian besar tetangga tampak mirip, tetap tidak rapi
  Di Kademlia ada 1 + 2 + 4 ... + 2^m-1 tetangga, dan semuanya tertata

• Tambahan bagi yang penasaran, orang ini adalah Simon Tatham yang sama dari Simon Tatham's Portable Puzzle Collection. Kalau belum tahu, ini layak dicoba saat bosan secara offline
  Waktu SMA saya menghabiskan banyak waktu memainkan ini: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

  • Ia juga Simon Tatham yang membuat PuTTY: https://www.chiark.greenend.org.uk/~sgtatham/putty/
  • Bagian terbaiknya adalah algoritma Minesweeper-nya membuat permainan yang tidak perlu menebak

• Saat ini banyak solver optimasi khusus, misalnya Ising Machine, menggunakan masalah XOR sebagai benchmark. Sebenarnya, menyelesaikan beberapa klausa XOR bisa dilakukan dalam waktu polinomial dengan eliminasi Gauss, sehingga kegunaannya agak terbatas, tetapi karena semua solver menunjukkan penskalaan eksponensial, ini tetap menjadi cara yang baik untuk mengukur kinerja
  Implementasi menarik kedua berkaitan dengan kriptosistem McEliece. Ini adalah kriptografi kunci publik dari era 70-an, dan belakangan kembali mendapat perhatian karena ketahanannya terhadap komputasi kuantum. Serangan dekripsi adalah masalah mencari solusi dari sekumpulan persamaan XOR; ini juga polinomial, tetapi ada syarat bahwa jarak Hamming harus sama dengan suatu angka yang terdapat dalam kunci publik

• Saat belajar assembly Z80 untuk memprogram TI-83, setiap byte kode mesin sangat penting. Sebab, total ruang penyimpanan kalkulator hanya 24KB
  Untuk menginisialisasi register akumulator utama a menjadi 0, yang dipakai adalah XOR a, bukan LD a, 0. Dalam instruksi matematika, a adalah operand otomatis, jadi XOR a melakukan XOR antara a dan dirinya sendiri, dan keseluruhan instruksinya hanya 1 byte. Sebaliknya, untuk memuat 0 secara eksplisit ke a, literal 0 harus masuk ke opcode, sehingga LD a, 0 menjadi instruksi 2 byte