Lihat sumber 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
: <math>\sigma(i) \equiv (i + 1)</math> [[Aritmetika modulus|modulus]] ''n'' untuk semua entri 
atau
: <math>\sigma(i) \equiv (i - 1)</math> [[Aritmetika modulus|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 [[Perpangkatan|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 [[Unit Pemroses Sentral|prosesor]] memiliki instruksi untuk itu (misalnya, [[x86|Intel x86]] memiliki perintah <code>ROL</code> dan <code>ROR</code>), banyak [[bahasa pemrograman]], termasuk [[C (bahasa pemrograman)|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.<ref>[https://gcc.gnu.org/ml/gcc-patches/2007-11/msg01112.html Optimize common rotate constructs]. ''GCC''.</ref>

<syntaxhighlight lang=C>
/*
 * Operasi geseran dalam C hanya didefinisikan untuk jumlah geseran
 * yang nonnegatif dan lebih kecil daripada sizeof(nilai) * CHAR_BIT.
 * Maskernya, yang dipakai dalam operasi AND (&), mencegah perilaku
 * tak terdefinisi ketika jumlah geseran 0 atau lebih besar daripada
 * lebar unsigned int.
 */

#include <stdint.h>  // untuk uint32_t, untuk memakai rotasi 32 bit tanpa memandang ukuran int
#include <limits.h>  // untuk CHAR_BIT

uint32_t rotl32(uint32_t nilai, unsigned int jumlah) {
    const unsigned int masker = CHAR_BIT * sizeof(nilai) - 1;
    jumlah &= masker;
    return (nilai << jumlah) | (nilai >> (-jumlah & masker));
}

uint32_t rotr32(uint32_t nilai, unsigned int jumlah) {
    const unsigned int masker = CHAR_BIT * sizeof(nilai) - 1;
    jumlah &= masker;
    return (nilai >> jumlah) | (nilai << (-jumlah & masker));
}
</syntaxhighlight>

Implementasi yang aman dan ramah kompilator di atas dikembangkan oleh [[John Regehr]]<ref>[http://blog.regehr.org/archives/1063 Safe, Efficient, and Portable Rotate in C/C++].</ref> dan dirapikan lebih lanjut oleh Peter Cordes.<ref>[https://stackoverflow.com/a/776523/224132 Best practices for rotates in C/C++]. ''StackOverflow''.</ref><ref>[https://stackoverflow.com/a/31488147/224132 Near constant time rotate that does not violate the standards]. ''StackOverflow''.</ref>

Bentuk yang lebih sederhana biasa ditemui ketika <code>jumlah</code> dibatasi dari 1 sampai 31 bit.

<syntaxhighlight lang=C>
uint32_t rotl32(uint32_t nilai, unsigned int jumlah) {
    return nilai << jumlah | nilai >> (32 - jumlah);
}
</syntaxhighlight>

Bentuk tersebut cukup berbahaya karena ia akan menggeser sebanyak 32 bit bila <code>jumlah</code> bernilai 0 atau 32 yang tidak didefinisikan dalam bahasa C. Namun, hal ini biasanya tetap bisa dipakai karena kebanyakan [[mikroprosesor]] menafsirkan <code>nilai >> 32</code> 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]].

<syntaxhighlight lang=cpp>
#include <climits>
// https://stackoverflow.com/a/776550/3770260
template <typename INT>
#if __cplusplus > 201100L // Pakai constexpr dalam C++ 11 untuk mempermudah pengoptimalan
constexpr
#endif // Lihat pula https://stackoverflow.com/a/7269693/3770260
INT rol(INT nilai, size_t jumlah) {
#if __cplusplus > 201100L && _wp_force_unsigned_rotate // Pakai pemeriksaan tak bertanda C++ 11 agar masuk akal
    static_assert(std::is_unsigned<INT>::value,
                  "Geseran kiri hanya masuk akal untuk jenis bilangan bulat tak bertanda");
#endif
    return (nilai << jumlah) | ((unsigned) nilai >> (-jumlah & (sizeof(INT) * CHAR_BIT - 1)));
}
</syntaxhighlight>

== Contoh ==
Bila barisan bit  digeser melingkar sebanyak satu bit, barisan tersebut akan menjadi berikut: (lihat gambar)
<ul style="margin-left: 0px;">
<li style="display: inline-block;"></li>
<li style="display: inline-block;"></li>
</ul>

Apabila geseran melingkar diteruskan, hasil pergeserannya adalah sebagai berikut:
<ul style="margin-left: 0px;">
<li style="display: inline-table;">
{| class="wikitable plainrowheaders" style="text-align: center;"
! ''n''
! scope=col colspan=8 | Geseran melingkar ke kiri
|-
! scope=row | 0
| 0 || 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1
|-
! scope=row | 1
| 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0
|-
! scope=row | 2
| 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0
|-
! scope=row | 3
| style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0 || 0
|-
! scope=row | 4
| 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0 || 0 || style="background: yellow;" | 1
|-
! scope=row | 5
| style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0 || 0 || style="background: yellow;" | 1 || 0
|-
! scope=row | 6
| style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1
|-
! scope=row | 7
| style="background: yellow;" | 1 || 0 || 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1
|-
! scope=row | 8
| 0 || 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1
|}</li>
<li style="display: inline-table;">
{| class="wikitable plainrowheaders" style="text-align: center;"
! ''n''
! scope=col colspan=8 | Geseran melingkar ke kanan
|-
! scope=row | 0
| 0 || 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1
|-
! scope=row | 1
| style="background: yellow;" | 1 || 0 || 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1
|-
! scope=row | 2
| style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1
|-
! scope=row | 3
| style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0 || 0 || style="background: yellow;" | 1 || 0
|-
! scope=row | 4
| 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0 || 0 || style="background: yellow;" | 1
|-
! scope=row | 5
| style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0 || 0
|-
! scope=row | 6
| 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0 || 0
|-
! scope=row | 7
| 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || 0
|-
! scope=row | 8
| 0 || 0 || 0 || style="background: yellow;" | 1 || 0 || style="background: yellow;" | 1 || style="background: yellow;" | 1 || style="background: yellow;" | 1
|}</li>
</ul>

== Referensi ==
<references />

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Geseran+melingkar&oldid=25436911 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.

<!-- WIKI_UNISSULA_PRESENTATION_V4 -->