Desplazamiento circular

Matrices de desplazamientos circulares de 8 elementos hacia la izquierda y hacia la derecha.

En matemáticas combinatorias , un desplazamiento circular es la operación de reorganizar las entradas de una tupla , ya sea moviendo la última entrada a la primera posición, mientras se desplazan todas las demás entradas a la siguiente posición, o realizando la operación inversa. Un desplazamiento circular es un tipo especial de permutación cíclica , que a su vez es un tipo especial de permutación . Formalmente, un desplazamiento circular es una permutación σ de las n entradas de la tupla tal que

${\displaystyle \sigma (i)\equiv (i+1)}$módulo n , para todas las entradas i = 1, ..., n

o

${\displaystyle \sigma (i)\equiv (i-1)}$módulo n , para todas las entradas i = 1, ..., n .

El resultado de aplicar repetidamente desplazamientos circulares a una tupla dada también se denomina desplazamientos circulares de la tupla.

Por ejemplo, al aplicar repetidamente desplazamientos circulares a la cuádrupla ( a , b , c , d ) sucesivamente se obtiene

• ( d , a , b , c ),
• ( c , d , a , b ),
• ( b , c , d , a ),
• ( a , b , c , d ) (la cuádrupla original),

y luego la secuencia se repite; por lo tanto, esta cuádrupla tiene cuatro desplazamientos circulares distintos. Sin embargo, no todas las n- tuplas tienen n desplazamientos circulares distintos. Por ejemplo, la cuádrupla ( a , b , a , b ) solo tiene 2 desplazamientos circulares distintos. El número de desplazamientos circulares distintos de una n -tupla es${\displaystyle {\frac {n}{k}}}$, donde k es un divisor de n , que indica el número máximo de repeticiones en todos los subpatrones.

En programación informática , una rotación bit a bit , también conocida como desplazamiento circular, es una operación que desplaza todos los bits de su operando. A diferencia de un desplazamiento aritmético , un desplazamiento circular no conserva el bit de signo ni distingue el exponente de un número de coma flotante de su mantisa . A diferencia de un desplazamiento lógico , las posiciones de bits vacías no se rellenan con ceros, sino con los bits que se desplazan fuera de la secuencia.

Los desplazamientos circulares se utilizan con frecuencia en criptografía para permutar secuencias de bits. Desafortunadamente, muchos lenguajes de programación, incluido C++ , no cuentan con operadores ni funciones estándar para el desplazamiento circular, a pesar de que prácticamente todos los procesadores disponen de instrucciones de operación bit a bit para ello (por ejemplo, Intel x86 tiene ROL (Rotar a la izquierda) y ROR (Rotar a la derecha)). Sin embargo, algunos compiladores pueden proporcionar acceso a las instrucciones del procesador mediante funciones intrínsecas . Además, algunas construcciones del código C++ estándar ANSI pueden ser optimizadas por un compilador a la instrucción de lenguaje ensamblador "rotar" en las CPU que disponen de dicha instrucción. La mayoría de los compiladores de C++ reconocen el siguiente patrón y lo compilan a una única instrucción de rotación de 32 bits. ^{[ 1 ] [ 2 ]}

/* * Las operaciones de desplazamiento en C solo están definidas para valores de desplazamiento que no sean negativos y sean menores que sizeof(value) * CHAR_BIT. * La máscara, utilizada con la operación AND bit a bit (&), evita un comportamiento indefinido * cuando el contador de desplazamiento es 0 o >= el ancho de un entero sin signo. */#include <stdint.h>  // para uint32_t, para obtener rotaciones de 32 bits, independientemente del tamaño de int. #include <limits.h>  // para CHAR_BITuint32_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 )); }

Esta implementación segura y compatible con el compilador fue desarrollada por John Regehr , ^{[ 3 ]} y perfeccionada posteriormente por Peter Cordes. ^{[ 4 ] [ 5 ]}

Una versión más sencilla se suele ver cuando countse limita al rango de 1 a 31 bits:

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

Esta versión es peligrosa porque si el valor countes 0 o 32, solicita un desplazamiento de 32 bits, lo cual es un comportamiento no definido en el estándar del lenguaje C. Sin embargo, suele funcionar de todos modos, ya que la mayoría de los microprocesadores implementan value >> 32un desplazamiento de 32 bits (que produce 0) o un desplazamiento de 0 bits (que produce el valor original value), y cualquiera de los dos produce el resultado correcto en esta aplicación.

Si la secuencia de bits 0001 0111 se sometiera a un desplazamiento circular de una posición de bit... (ver imágenes a continuación)

Si la secuencia de bits 1001 0110 se sometiera a las siguientes operaciones:

Los códigos cíclicos son un tipo de código de bloques con la propiedad de que el desplazamiento circular de una palabra clave siempre produce otra palabra clave. Esto motiva la siguiente definición general: Para una cadena s sobre un alfabeto Σ , sea shift ( s ) el conjunto de desplazamientos circulares de s , y para un conjunto L de cadenas, sea shift ( L ) el conjunto de todos los desplazamientos circulares de cadenas en L. Si L es un código cíclico, entonces shift ( L ) ⊆ L ; esta es una condición necesaria para que L sea un lenguaje cíclico . La operación shift ( L ) se ha estudiado en la teoría de lenguajes formales . Por ejemplo, si L es un lenguaje libre de contexto , entonces shift ( L ) también es libre de contexto. ^{[ 6 ] [ 7 ]} Además, si L se describe mediante una expresión regular de longitud n , existe una expresión regular de longitud O ( n³ ⁾ que describe shift ( L ). ^{[ 8 ]}

• Desplazador de barril
• Circulante
• Lyndon palabra
• Collar : un objeto similar a una tupla , pero para el cual los desplazamientos circulares se consideran equivalentes.