Przesunięcie kołowe - Circular shift

Matryce 8-elementowych przesunięć kołowych w lewo i prawo

W kombinatorycznych matematyki , o okrągłym przesunięcie jest operacja rozmieszczanie wpisy w krotce , albo przez przesunięcie ostatecznego wpisu do pierwszej pozycji, natomiast przesunięcie wszystkie inne wpisy do następnej pozycji, lub wykonując operację odwrotną. Przesunięcie kołowe jest szczególnym rodzajem permutacji cyklicznej , która z kolei jest szczególnym rodzajem permutacji . Formalnie przesunięcie kołowe jest permutacją σ n wpisów w krotce, tak że albo

${\ Displaystyle \ sigma (i) \ równoważnik (i + 1)}$ modulo n , dla wszystkich wpisów i = 1, ..., n

lub

${\ Displaystyle \ sigma (i) \ równoważnik (i-1)}$ modulo n , dla wszystkich wpisów i = 1, ..., n .

Rezultat wielokrotnego stosowania kołowych przesunięć do danej krotki jest również nazywany kołowymi przesunięciami krotki.

Na przykład wielokrotne stosowanie kołowych przesunięć do czterech krotek ( a , b , c , d ) kolejno daje

• ( d , a , b , c ),
• ( c , d , a , b ),
• ( b , c , d , a ),
• ( a , b , c , d ) (oryginalna czterokrotka),

a następnie sekwencja się powtarza; ta czwórka ma zatem cztery wyraźne przesunięcia kołowe. Jednak nie wszystkie n -krotki mają n wyraźnych przesunięć kołowych. Na przykład 4-krotka ( a , b , a , b ) ma tylko 2 wyraźne przesunięcia kołowe. Na ogół liczba kolistych przesunięć w n -tuple mogło być dzielnikiem z n , w zależności od pozycji w krotce.

W programowaniu komputerowym , o obrót bitowe , znany również jako przesunięcia kołowego, to operacja bitowe że przesuwa wszystkie bity jej argumentu. W przeciwieństwie do arytmetycznego przesunięcia , okrągły shift nie zachowuje pewna liczba jest bitem znaku lub odróżnić liczbę zmiennoprzecinkową dydaktycznego wykładnik od jej mantysy . W przeciwieństwie do przesunięcia logicznego , puste pozycje bitów nie są wypełniane zerami, ale są wypełniane bitami, które są przesunięte z sekwencji.

Wdrażanie zmian kołowych

Przesunięcia kołowe są często używane w kryptografii w celu permutacji sekwencji bitów. Niestety wiele języków programowania, w tym C , nie ma operatorów ani standardowych funkcji do przesuwania kołowego, mimo że praktycznie wszystkie procesory mają do tego bitowe instrukcje operacyjne (np. Intel x86 ma ROL i ROR). Jednak niektóre kompilatory mogą zapewniać dostęp do instrukcji procesora za pomocą funkcji wewnętrznych . Dodatkowo, niektóre konstrukcje w standardowym kodzie ANSI C mogą być zoptymalizowane przez kompilator do instrukcji asemblera "rotate" na procesorach, które mają taką instrukcję. Większość kompilatorów C rozpoznaje następujący idiom i kompiluje go do pojedynczej 32-bitowej instrukcji obracania.

/*
 * Shift operations in C are only defined for shift values which are
 * not negative and smaller than sizeof(value) * CHAR_BIT.
 * The mask, used with bitwise-and (&), prevents undefined behaviour
 * when the shift count is 0 or >= the width of unsigned int.
 */

#include <stdint.h>  // for uint32_t, to get 32-bit-wide rotates, regardless of the size of int.
#include <limits.h>  // for CHAR_BIT

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));
}

Ta bezpieczna i przyjazna dla kompilatora implementacja została opracowana przez Johna Regehra i dopracowana przez Petera Cordesa.

Prostsza wersja jest często spotykana, gdy countjest ograniczona do zakresu od 1 do 31 bitów:

uint32_t rotl32 (uint32_t value, unsigned int count) {
    return value << count | value >> (32 - count);
}

Ta wersja jest niebezpieczna, ponieważ jeśli countjest to 0 lub 32, prosi o 32-bitowe przesunięcie, co jest niezdefiniowanym zachowaniem w standardzie języka C. Jednak i tak działa, ponieważ większość mikroprocesorów implementuje value >> 32albo przesunięcie 32-bitowe (tworząc 0) albo przesunięcie 0-bitowe (tworząc oryginał value), i każdy z nich daje poprawny wynik w tej aplikacji.

Przykład

Jeśli sekwencja bitów 0001 0111 została poddana przesunięciu kołowemu o jedną pozycję bitową... (patrz rysunki poniżej)

po lewej dałoby się: 0010 1110 Przesunięcie kołowe w lewo.

po prawej dałoby: 1000 1011. Przesunięcie kołowe w prawo.

Jeżeli ciąg bitów 1001 0110 został poddany następującym operacjom:

Aplikacje

Kody cykliczne są rodzajem kodu blokowego z tą właściwością, że przesunięcie kołowe słowa kodowego zawsze da inne słowo kodowe. To uzasadnia następującą ogólną definicję: Dla ciągu s nad alfabetem Σ niech przesunięcie ( s ) oznacza zbiór kołowych przesunięć s , a dla zbioru L strun niech przesunięcie ( L ) oznacza zbiór wszystkich kołowych przesunięć ciągów w L . Jeśli L jest kodem cyklicznym, to przesunięcie ( L ) ⊆ L ; jest to warunek konieczny, aby L był językiem cyklicznym . Operacja przesunięcia ( L ) była badana w teorii języka formalnego . Na przykład, jeśli L jest językiem bezkontekstowym , wtedy przesunięcie ( L ) jest znowu bezkontekstowe. Ponadto, jeśli L jest opisane wyrażeniem regularnym o długości n , istnieje wyrażenie regularne o długości O ( n ³ ) opisujące przesunięcie ( L ).

Zobacz też

• Przerzutnik lufy
• Operacja bitowa
• Cyrkulant
• Słowo Lyndona
• Naszyjnik — przedmiot podobny do krotki, ale dla którego przesunięcia kołowe są uważane za równoważne.

Bibliografia