Geseran melingkar

Dalam matematika kombinatorika, geseran melingkar () adalah operasi penataan daftar dalam daftar berurut (tuple) yang menggeser entri terakhir ke awal lalu sisanya mengikuti (tergeser) atau sebaliknya. Geseran melingkar adalah jenis permutasi siklis yang khusus. Secara formal, geseran melingkar adalah permutasi σ dari n entri dalam daftar berurut sehingga

$\sigma (i)\equiv (i+1)$ modulus n untuk semua entri

atau

$\sigma (i)\equiv (i-1)$ modulus n untuk semua entri .

Hasil dari penerapan geseran melingkar pada suatu daftar berurut disebut pergeseran melingkar dari daftar berurut tersebut.

Misalnya, penerapan geseran melingkar untuk daftar berurut (a, b, c, d) berturut-turut menghasilkan

• (d, a, b, c),
• (c, d, a, b),
• (b, c, d, a),
• (a, b, c, d) (daftar berurut asli),

dan kemudian berulang; daftar berurut ini memiliki empat pergeseran melingkar yang berbeda. Namun, tidak semua daftar berurut jumlah n memiliki n pergeseran yang berbeda. Misalnya, daftar berurut (a, b, a, b) hanya memiliki dua pergeseran melingkar yang berbeda. Pada umumnya, jumlah pergeseran melingkar dari daftar berurut jumlah n dapat bernilai faktor-faktor n dan bergantung pada entri-entri dalam daftar berurut.

Dalam pemrograman, suatu rotasi tingkat bit, juga dikenal sebagai pergeseran melingkar, adalah operasi tingkat bit yang menggeser semua bitnya. Hal ini berbeda dengan pergeseran aritmetika. Pergeseran melingkar tidak memedulikan bit tanda bilangan atau membedakan pangkat dengan bilangan pokok dalam bilangan titik mengambang. Hal ini juga berbeda dengan pergeseran logika. Posisi bit yang kosong diisi oleh bit yang tergeser keluar dari barisannya.

Implementasi

Geseran melingkar sering dipakai dalam kriptografi untuk melakukan permutasi barisan bit. Sayangnya, meski hampir semua prosesor memiliki instruksi untuk itu (misalnya, Intel x86 memiliki perintah ROL dan ROR), banyak bahasa pemrograman, termasuk C, tidak memiliki operator atau fungsi baku untuk pergeseran melingkar. Namun, beberapa kompilator menerjemahkan kode yang melakukan hal yang sama ke instruksi geseran melingkar yang sesuai. Kebanyakan kompilator C mengenali polanya dan menerjemahkan ke instruksi tunggal.

Implementasi yang aman dan ramah kompilator di atas dikembangkan oleh John Regehr dan dirapikan lebih lanjut oleh Peter Cordes.

Bentuk yang lebih sederhana biasa ditemui ketika jumlah dibatasi dari 1 sampai 31 bit.

Bentuk tersebut cukup berbahaya karena ia akan menggeser sebanyak 32 bit bila jumlah bernilai 0 atau 32 yang tidak didefinisikan dalam bahasa C. Namun, hal ini biasanya tetap bisa dipakai karena kebanyakan mikroprosesor menafsirkan nilai >> 32 sebagai geseran 32 bit (menghasilkan nol) atau tanpa pergeseran dan keduanya menghasilkan nilai yang tepat untuk penggunaan ini.

Untuk C++, penggunaan templat dapat memperluas dukungan untuk semua jenis bilangan bulat.

Contoh

Bila barisan bit digeser melingkar sebanyak satu bit, barisan tersebut akan menjadi berikut: (lihat gambar)

Apabila geseran melingkar diteruskan, hasil pergeserannya adalah sebagai berikut:

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 25436911 (2024-03-15T06:04:40Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.