Kruhový posun - Circular shift

Matice 8prvkových kruhových posunů doleva a doprava

V kombinatorické matematice je kruhový posun operací přeskupení záznamů v n-tici , a to buď přesunutím finálního záznamu do první polohy, zatímco posunutím všech ostatních záznamů do další polohy, nebo provedením inverzní operace. Kruhový posun je speciální druh cyklické permutace , což je zase speciální druh permutace . Formálně je kruhový posun permutací σ z n záznamů v n-tici tak, že buď

${\ Displaystyle \ sigma (i) \ equiv (i + 1)}$ modulo n , pro všechny položky i = 1, ..., n

nebo

${\ Displaystyle \ sigma (i) \ equiv (i-1)}$ modulo n , pro všechny položky i = 1, ..., n .

Výsledek opakovaného použití kruhových posunů na danou n-tici se také nazývá kruhové posuny n-tice.

Například opakované použití kruhových posunů na čtyřici ( a , b , c , d ) postupně dává

• ( d , a , b , c ),
• ( c , d , a , b ),
• ( b , c , d , a ),
• ( a , b , c , d ) (původní čtyřnásobná n-tice),

a pak se sekvence opakuje; tato čtyřice má tedy čtyři odlišné kruhové posuny. Ne všechny n -tice však mají n výrazných kruhových posunů. Například 4-n-tice ( a , b , a , b ) má pouze 2 odlišné kruhové posuny. Obecně počet kruhových posunů o n -tuple může být libovolný dělitel z n , v závislosti na vstupy n-tice.

V počítačovém programování je bitová rotace , známá také jako kruhový posun, bitová operace, která posune všechny bity jejího operandu. Na rozdíl od aritmetického posunu kruhový posun nezachová znakový bit čísla ani nerozlišuje exponent čísla s plovoucí desetinnou čárkou od jeho významu . Na rozdíl od logického posunu nejsou prázdné pozice bitů vyplněny nulami, ale jsou vyplněny bity, které jsou posunuty mimo sekvenci.

Provádění kruhových směn

Kruhové posuny se často používají v kryptografii, aby se permutovaly bitové sekvence. Mnoho programovacích jazyků, včetně jazyka C , bohužel nemá operátory ani standardní funkce pro kruhové řazení, i když prakticky všechny procesory mají bitové provozní pokyny (např. Intel x86 má ROL a ROR). Někteří překladači však mohou poskytovat přístup k instrukcím procesoru pomocí vnitřních funkcí . Kromě toho mohou být některé konstrukce ve standardním kódu ANSI C optimalizovány kompilátorem podle instrukce jazyka „rotace“ v assembleru na procesorech, které takovou instrukci mají. Většina překladačů jazyka C rozpoznává následující idiom a kompiluje jej do jedné 32bitové instrukce pro otočení.

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

Tuto bezpečnou implementaci vhodnou pro kompilátory vyvinul John Regehr a dále ji vyleštil Peter Cordes.

Jednodušší verze je často vidět, když countje omezena na rozsah 1 až 31 bitů:

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

Tato verze je nebezpečná, protože pokud countmá hodnotu 0 nebo 32, požádá o 32bitový posun, což je nedefinované chování ve standardu jazyka C. value >> 32Má však tendenci stejně fungovat, protože většina mikroprocesorů implementuje buďto 32bitový posun (produkující 0) nebo 0bitový posun (produkující originál value), a každý z nich v této aplikaci vytvoří správný výsledek.

Příklad

Pokud by bitová sekvence 0001 0111 byla podrobena kruhovému posunu o jednu bitovou pozici ... (viz obrázky níže)

nalevo by přineslo: 0010 1110 Kruhový posun vlevo.

napravo by přineslo: 1 000 1011. Kruhový posun doprava.

Pokud byla bitová sekvence 1001 0110 podrobena následujícím operacím:

Aplikace

Cyklické kódy jsou druh blokového kódu s vlastností, že kruhový posun kódového slova vždy přinese další kódové slovo. To motivuje následující obecnou definici: Pro řetězec s nad abecedou Σ označme shift ( s ) množinu kruhových posunů s a pro množinu L řetězců nechme shift ( L ) označit množinu všech kruhových posunů strun v L . Pokud L je cyklický kód, pak shift ( L ) ⊆ L ; toto je nezbytná podmínka pro to, aby L byl cyklický jazyk . Operační posun ( L ) byl studován ve formální jazykové teorii . Například pokud L je jazyk bez kontextu , pak shift ( L ) je opět bez kontextu. Také, pokud je L popsán regulárním výrazem délky n , existuje regulární výraz délky O ( n ³ ) popisující posun ( L ).

Viz také

• Posuvník hlavně
• Bitový provoz
• Oběžník
• Lyndonské slovo
• Náhrdelník - objekt jako n-tice, ale u kterého jsou kruhové posuny považovány za ekvivalentní.

Reference