Kruhový posun - Circular shift

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Kruhový posun"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Prosince 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

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

v kombinační matematika, a kruhový posun je operace přeskupení záznamů v a n-tice, buď přesunutím posledního vstupu do první polohy, zatímco posunete všechny ostatní vstupy do další polohy, nebo provedením inverzní operace. Kruhový posun je zvláštní druh cyklická permutace, což je zase zvláštní druh permutace. Formálně je kruhový posun a permutace σ z n položky 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é směny 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šak všechny n- n-tice mají n výrazné kruhové posuny. 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 jakýkoli dělitel z n, v závislosti na položkách n-tice.

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

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

Kruhové směny se často používají v kryptografie za účelem permutace bitových sekvencí. Bohužel mnoho programovacích jazyků, včetně C, nemají operátory ani standardní funkce pro kruhové řazení, i když prakticky všechny procesory mít bitový provoz pokyny k tomu (např. Intel x86 má ROL a ROR). Někteří překladatelé však mohou poskytnout přístup k instrukcím procesoru pomocí vnitřní funkce. Kromě toho mohou být některé konstrukty ve standardním kódu ANSI C optimalizovány kompilátorem podle instrukce jazyka „rotace“ v assembleru na CPU, 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í.^[1][2]

/* * Operace posunu v C jsou definovány pouze pro hodnoty posunu, které jsou * není záporné a menší než sizeof (hodnota) * CHAR_BIT. * Maska, použitá s bitovými a (&), brání nedefinovanému chování * když je počet posunů 0 nebo> = šířka nepodepsaného int. */#zahrnout  // pro uint32_t, chcete-li získat 32bitové otáčky, bez ohledu na velikost int.#zahrnout  // pro CHAR_BITuint32_t rotl32 (uint32_t hodnota, nepodepsaný int počet) {    konst nepodepsaný int maska = CHAR_BIT * velikost(hodnota) - 1;    počet &= maska;    vrátit se (hodnota << počet) | (hodnota >> (-počet & maska));}uint32_t rotr32 (uint32_t hodnota, nepodepsaný int počet) {    konst nepodepsaný int maska = CHAR_BIT * velikost(hodnota) - 1;    počet &= maska;    vrátit se (hodnota >> počet) | (hodnota << (-počet & maska));}

Tuto bezpečnou implementaci vhodnou pro kompilátory vyvinul John Regehr,^[3] a dále leštěn Peterem Cordesem.^[4][5]

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

uint32_t rotl32 (uint32_t hodnota, nepodepsaný int počet) {    vrátit se hodnota << počet | hodnota >> (32 - počet);}

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

Příklad

Pokud by bitová sekvence 0001 0111 byla vystavena 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 jakési blokovat kód 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 a tětiva s přes abecedu Σ, nechť posun(s) označují soubor kruhových posunů o sa pro sadu L strun, nechť posun(L) označuje množinu všech kruhových posunů řetězců dovnitř L. Li L je tedy cyklický kód posun(L) ⊆ L; toto je nezbytná podmínka pro L být cyklický jazyk. Operace posun(L) byl studován v teorie formálního jazyka. Například pokud L je bezkontextový jazyk, pak posun(L) je opět bezkontextový.^[6][7] Také pokud L je popsán a regulární výraz délky n, existuje regulární výraz délky Ó (n³) popisující posun(L).^[8]

Viz také

• Posuvník hlavně
• Bitová operace
• Oběžník
• Lyndonské slovo
• Náhrdelník - předmět jako a n-tice ale pro které jsou kruhové posuny považovány za rovnocenné.

Reference