Dairesel kaydırma

Kombinatoryal matematikte, bir dairesel kaydırma, bir demetteki (tuple) girdilerin, son girdiyi ilk konuma taşıyıp diğer tüm girdileri bir sonraki konuma kaydırarak veya bu işlemin tersini uygulayarak yeniden düzenlenmesi işlemidir.

Bir dairesel kaydırma, devirli permütasyonun özel bir türüdür ve bu da permütasyonun özel bir türüdür. Resmi tanıma göre, dairesel kaydırma, demetteki n girdinin bir σ permütasyonudur; öyle ki tüm i = 1, ..., n girdileri için:
 mod n
veya
 mod n
olur.

Belirli bir demete tekrar tekrar dairesel kaydırma uygulamanın sonucu da o demetin dairesel kaydırmaları olarak adlandırılır.

Örneğin, (a, b, c, d) dörtlü demetine (4-tuple) tekrar tekrar dairesel kaydırma uygulamak sırasıyla şunları verir:
 (d, a, b, c),
 (c, d, a, b),
 (b, c, d, a),
 (a, b, c, d) (orijinal dörtlü demet),
ve ardından dizi tekrarlanır; bu nedenle bu dörtlü demetin dört farklı dairesel kaydırması vardır. Ancak, tüm n-demetlerinin n adet farklı dairesel kaydırması yoktur. Örneğin, (a, b, a, b) 4-lü demetinin yalnızca 2 farklı dairesel kaydırması vardır. Bir n-demetinin farklı dairesel kaydırmalarının sayısı 'dır; burada , tüm alt desenlerdeki maksimum tekrar sayısını belirten bir  bölenidir.

Bilgisayar programlamada, bitsel rotasyon (bitwise rotation) veya dairesel kaydırma, işlenileninin (operand) tüm bitlerini kaydıran bir bitsel işlemdir. Aritmetik kaydırmanın aksine, dairesel kaydırma bir sayının işaret bitini korumaz veya bir kayan noktalı sayının üssünü anlamlı kısmından (significand) ayırmaz. Mantıksal kaydırmanın aksine, boş kalan bit konumları sıfırlarla doldurulmaz, bunun yerine diziden dışarı kaydırılan bitlerle doldurulur.

 Dairesel kaydırmaların uygulanması 
Dairesel kaydırmalar, bit dizilerini permütasyona uğratmak (yerini değiştirmek) amacıyla kriptografide sıklıkla kullanılır. Ne yazık ki, C dahil olmak üzere birçok programlama dili, dairesel kaydırma için operatörlere veya standart fonksiyonlara sahip değildir; oysa hemen hemen tüm işlemciler bunun için bitsel işlem talimatlarına sahiptir (örneğin Intel x86'da ROL ve ROR vardır). 

Ancak, bazı derleyiciler iç işlevler (intrinsic functions) aracılığıyla işlemci talimatlarına erişim sağlayabilir. Ek olarak, standart ANSI C kodundaki bazı yapılar, bir derleyici tarafından, böyle bir talimata sahip CPU'larda "döndürme" (rotate) çevirici dili talimatına optimize edilebilir. Çoğu C derleyicisi aşağıdaki deyimi tanır ve bunu tek bir 32-bitlik döndürme talimatına derler.GCC: "Yaygın döndürme yapılarını optimize et" ("Optimize common rotate constructs")"ROTL/ROTR DAG birleştirici kodundaki temizlikler", bu kodun CellSPU'daki "rotate" talimatını desteklediğinden bahseder.

/*
 * C dilinde kaydırma işlemleri, yalnızca negatif olmayan ve 
 * sizeof(değer) * CHAR_BIT değerinden küçük olan kaydırma değerleri için tanımlanır.
 * Bitsel-ve (&) ile kullanılan maske, kaydırma sayısı 0 olduğunda veya 
 * unsigned int genişliğine eşit veya daha büyük olduğunda tanımsız davranışı önler.
 */

#include <stdint.h>  // int boyutu ne olursa olsun 32-bit genişliğinde döndürmeler elde etmek için uint32_t.
#include <limits.h>  // CHAR_BIT için

uint32_t rotl32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value << count) | (value >> (-count & mask));
}

uint32_t rotr32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value >> count) | (value << (-count & mask));
}

Bu güvenli ve derleyici dostu uygulama John Regehr tarafından geliştirilmişC/C++'ta Güvenli, Verimli ve Taşınabilir Döndürme ve Peter Cordes tarafından daha da ilerletilmiştir.Stackoverflow: C/C++'ta döndürmeler için en iyi uygulamalarStandartları ihlal etmeyen neredeyse sabit zamanlı döndürme

count (sayaç) 1 ila 31 bit aralığıyla sınırlandığında daha basit bir sürüm sıklıkla görülür:
uint32_t rotl32 (uint32_t value, unsigned int count) {
    return (value << count) | (value >> (32 - count));
}
Bu sürüm tehlikelidir çünkü count 0 veya 32 ise, 32-bitlik bir kaydırma ister; bu da C dil standardında tanımsız davranıştır (undefined behaviour). Ancak, yine de bu kod, çalışma eğilimindedir çünkü çoğu mikroişlemci value >> 32 işlemini ya 32-bitlik bir kaydırma (0 üretir) ya da 0-bitlik bir kaydırma (orijinal value değerini üretir) olarak uygular ve her ikisi de bu uygulamada doğru sonucu üretir.

Örnek
Eğer  bit dizisi bir bitlik dairesel kaydırmaya tabi tutulursa: (aşağıdaki resimlere bakınız)

 sola doğru şu sonucu verir: 
küçükresim|sol|upright=1.36|Sola dairesel kaydırma. sağa doğru şu sonucu verir: .
küçükresim|sol|upright=1.36|Sağa dairesel kaydırma.

Eğer  bit dizisi aşağıdaki işlemlere tabi tutulursa:

 1 konum sola dairesel kaydırma:              2 konum sola dairesel kaydırma:  3 konum sola dairesel kaydırma:  4 konum sola dairesel kaydırma:  5 konum sola dairesel kaydırma:  6 konum sola dairesel kaydırma:  7 konum sola dairesel kaydırma:  8 konum sola dairesel kaydırma: 

 1 konum sağa dairesel kaydırma:  2 konum sağa dairesel kaydırma:  3 konum sağa dairesel kaydırma:  4 konum sağa dairesel kaydırma:  5 konum sağa dairesel kaydırma:  6 konum sağa dairesel kaydırma:  7 konum sağa dairesel kaydırma:  8 konum sağa dairesel kaydırma: 

 Uygulamalar 

Döngüsel kodlar, bir kod sözcüğünün dairesel kaydırılmasının her zaman başka bir kod sözcüğü ürettiği özelliğe sahip bir blok kod türüdür. Bu, aşağıdaki genel tanımı motive eder: Bir Σ alfabesi üzerindeki bir s dizisi (string) için, shift(s) 'nin dairesel kaydırmalarının kümesini belirtsin ve L dizi kümesi için, shift(L) L içindeki dizilerin tüm dairesel kaydırmalarının kümesini belirtsin. Eğer L devirsel bir kod ise, o zaman shift(L) ⊆ L; bu, L'''nin bir devirsel dil olması için gerekli bir koşuldur. shift(L) işlemi biçimsel dil kuramınde incelenmiştir. Örneğin, eğer L bir bağlamdan bağımsız dil ise, shift(L) de yine bağlamdan bağımsızdır.T.
Oshiba, "Bağlamdan bağımsız diller ailesinin dairesel kaydırma işlemi altında kapalılık özelliği" ("Closure property of the family of context-free languages under the cyclic shift operation"), Transactions of IECE, 55D:119–122, 1972.A.
N. Maslov, "Diller için dairesel kaydırma işlemi" ("Cyclic shift operation for languages"), Problems of Information Transmission 9:333–338, 1973. Ayrıca, eğer L uzunluğu n olan bir düzenli ifade ile tanımlanıyorsa, shift(L)'yi tanımlayan O(n''3) uzunluğunda bir düzenli ifade vardır..

 Kaynakça 

Kategori:Temel matematik
Kategori:Bilgisayar aritmetiği