Menukar Nilai Dua Variable Tanpa Perantara
Menukar nilai dua buah variable adalah salah satu algoritma dasar dalam struktur data. Biasanya untuk menulis fungsi swap ini, kita membutuhkan tambahan satu variable sebagai perantara. Berikut ini adalah algoritma untuk menukar nilai dua buah variable dengan perantara.
tmp = x; x = y; y = tmp;
Pada contoh di atas nilai variable x dan y bertukar melalui perantara tmp. Berikut ini adalah algoritma untuk menukar nilai dua buah variable tanpa perantara.
x = x ^ y; y = x ^ y; x = x ^ y;
Singkat dan sederhana, nilai variable x dan y sudah bertukar. Tanda caret ^ dalam bahasa pemrograman Java dan C adalah operator bitwise (logika) XOR (Eksklusif Or). Pada eksklusif or berlaku hukum alternatif, yaitu hanya salah satu saja yang boleh bernilai true. Perbedaannya dengan inklusif or (OR) adalah berlaku hukum kumulatif, yaitu boleh salah satu atau keduanya bernilai true.
x y OR XOR -------------- 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0
Penjelasan dari keajaiban pertukaran di atas adalah karena operator XOR memiliki dua sifat. Pertama, menggabungkan/mencampurkan informasi, dan kedua, mampu memisahkannya kembali (sekaligus menghapus jejak penggabungannya) dengan cara melakukan lagi operasi XOR kepadanya.
Pada baris pertama, nilai x dan y digabungkan sehingga membentuk suatu nilai hybrid di antara keduanya (sifat 1). Simpan nilai hybrid tersebut di x. Pada baris kedua nilai hybrid di-XOR-kan lagi dengan y yang akan memunculkan lagi nilai x semula (sifat 2). Simpan nilai x semula di y. Terakhir nilai hybrid di-XOR-kan dengan y (ingat y sekarang bernilai x semula) sehingga memunculkan lagi nilai y semula (sifat 2). Simpan nilai y semula di x.
Supaya lebih jelas lagi, kita coba dengan contoh. Misalnya int x bernilai 5 (0101) dan int y bernilai 9 (1001).
x = 5 = 0101; y = 9 = 1001; x = x ^ y; // x = 0101 ^ 1001 = 1100 = hybrid y = x ^ y; // y = 1100 ^ 1001 = 0101 = 5 x = x ^ y; // x = 1100 ^ 0101 = 1001 = 9
Implementasi pertukaran nilai dengan operator logika XOR dalam bahasa pemrograman Java adalah sebagai berikut.
int x = 5, y = 9; x ^= y; // x = hybrid y ^= x; // y = 5 x ^= y; // x = 9
Begitulah cerita dibalik dua nilai variable yang tertukar :D. Pembahasan lebih mendalam tentang XOR Swap Algorithm bisa dibaca di Wikipedia.
