En matemáticas combinatorias , un desplazamiento circular es la operación de reorganizar las entradas de una tupla , ya sea moviendo la entrada final 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 de manera que
o
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ádruple ( a , b , c , d ) se obtiene sucesivamente
y luego la secuencia se repite; por lo tanto, esta cuadruple-tupla tiene cuatro desplazamientos circulares distintos. Sin embargo, no todas las n -tuplas tienen n desplazamientos circulares distintos. Por ejemplo, la cuadruple-tupla ( a , b , a , b ) solo tiene 2 desplazamientos circulares distintos. El número de desplazamientos circulares distintos de una n -tupla es , donde k es un divisor de n , lo 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 bit a bit que desplaza todos los bits de su operando. A diferencia de un desplazamiento aritmético , un desplazamiento circular no conserva el bit de signo de un número ni distingue el exponente de un número de punto flotante de su mantisa . A diferencia de un desplazamiento lógico , las posiciones de bits vacantes no se rellenan con ceros, sino con los bits que se desplazan fuera de la secuencia.
Los desplazamientos circulares se utilizan a menudo en criptografía para permutar secuencias de bits. Desafortunadamente, muchos lenguajes de programación, incluido C , no tienen operadores o funciones estándar para el desplazamiento circular, aunque prácticamente todos los procesadores tienen instrucciones de operación bit a bit para ello (por ejemplo, Intel x86 tiene ROL y ROR). Sin embargo, algunos compiladores pueden proporcionar acceso a las instrucciones del procesador por medio de funciones intrínsecas . Además, algunas construcciones en el código ANSI C estándar pueden ser optimizadas por un compilador para la instrucción de lenguaje ensamblador "rotar" en CPU que tienen dicha instrucción. La mayoría de los compiladores de C reconocen el siguiente modismo y lo compilan en una única instrucción de rotación de 32 bits. [1] [2]
/* * Las operaciones de desplazamiento en C sólo se definen para valores de desplazamiento que * no sean negativos y menores que sizeof(value) * CHAR_BIT. * La máscara, utilizada con bit a bit y (&), evita un comportamiento indefinido * cuando el conteo de desplazamiento es 0 o >= el ancho de un int sin signo. */#include <stdint.h> // para uint32_t, para obtener rotaciones de 32 bits de ancho, independientemente del tamaño de int. #include <limits.h> // para CHAR_BIT uint32_t rotl32 ( uint32_t valor , entero sin signo recuento ) { const entero sin signo máscara = CHAR_BIT * sizeof ( valor ) - 1 ; recuento & = máscara ; return ( valor << recuento ) | ( valor >> ( - recuento & máscara )); } uint32_t rotr32 ( uint32_t valor , entero sin signo recuento ) { const entero sin signo máscara = CHAR_BIT * sizeof ( valor ) - 1 ; recuento &= máscara ; return ( valor >> recuento ) | ( valor << ( - recuento & máscara )); } Esta implementación segura y fácil de compilar fue desarrollada por John Regehr , [3] y perfeccionada por Peter Cordes. [4] [5]
A menudo se ve una versión más simple cuando countestá limitada al rango de 1 a 31 bits:
uint32_t rotl32 ( uint32_t valor , int sin signo recuento ) { return ( valor << recuento ) | ( valor >> ( 32 - recuento )); } Esta versión es peligrosa porque si 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, tiende a funcionar de todos modos, porque 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 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 bloque con la propiedad de que el desplazamiento circular de una palabra de código siempre producirá otra palabra de código. 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 ) ha sido estudiada en la teoría del lenguaje formal . Por ejemplo, si L es un lenguaje libre de contexto , entonces shift ( L ) es nuevamente 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 3 ) que describe shift ( L ). [8]