En matemática combinatoria , un cambio circular es la operación de reorganizar las entradas en una tupla , ya sea moviendo la entrada final a la primera posición, mientras se cambian 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 en la tupla tal que
- módulo n , para todas las entradas i = 1, ..., n
o
- módulo n , para todas las entradas i = 1, ..., n .
El resultado de aplicar repetidamente cambios circulares a una tupla determinada también se denomina cambios circulares de la tupla.
Por ejemplo, la aplicación repetida de cambios circulares a la tupla de cuatro ( a , b , c , d ) da sucesivamente
- ( d , a , b , c ),
- ( c , d , a , b ),
- ( b , c , d , a ),
- ( a , b , c , d ) (las cuatro tuplas originales),
y luego la secuencia se repite; esta cuatro tupla, por tanto, tiene cuatro cambios circulares distintos. Sin embargo, no todas las n tuplas tienen n cambios circulares distintos. Por ejemplo, la tupla de 4 ( a , b , a , b ) solo tiene 2 cambios circulares distintos. En general, el número de cambios circulares de una n- tupla podría ser cualquier divisor de n , dependiendo de las entradas de la tupla.
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 signo de un número de bits o distinguir un número de coma flotante 's exponente de su mantisa . A diferencia de un desplazamiento lógico , las posiciones de bits vacantes no se rellenan con ceros, sino que se rellenan con los bits que se desplazan fuera de la secuencia.
Implementando turnos circulares
Los cambios 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 (por ejemplo, Intel x86 tiene ROL y ROR). Sin embargo, algunos compiladores pueden proporcionar acceso a las instrucciones del procesador mediante 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 en lenguaje ensamblador "rotar" en CPU que tienen tal instrucción. La mayoría de los compiladores de C reconocen el siguiente idioma y lo compilan en una sola instrucción de rotación de 32 bits. [1] [2]
/ * * Las operaciones de cambio en C solo se definen para valores de cambio que * no son negativos y son más pequeños que sizeof (valor) * CHAR_BIT. * La máscara, utilizada con bit a bit y (&), evita un comportamiento indefinido * cuando el recuento de cambios es 0 o> = el ancho de unsigned int. * /#include // para uint32_t, para obtener rotaciones de 32 bits de ancho, independientemente del tamaño de int.#include // para CHAR_BITuint32_t rotl32 ( valor uint32_t , recuento int sin signo ) { máscara int sin signo constante = CHAR_BIT * sizeof ( valor ) - 1 ; contar & = máscara ; return ( valor << recuento ) | ( valor >> ( - recuento y máscara )); } uint32_t rotr32 ( valor uint32_t , recuento int sin signo ) { máscara int sin signo constante = CHAR_BIT * sizeof ( valor ) - 1 ; contar & = máscara ; retorno ( valor >> recuento ) | ( valor << ( - recuento y máscara )); }
Esta implementación segura y amigable para el compilador fue desarrollada por John Regehr , [3] y más pulida por Peter Cordes. [4] [5]
A menudo se ve una versión más simple cuando count
se limita al rango de 1 a 31 bits:
uint32_t rotl32 ( valor uint32_t , recuento int sin signo ) { valor de retorno << recuento | valor >> ( 32 - recuento ); }
Esta versión es peligrosa porque si count
es 0 o 32, solicita un cambio de 32 bits, que es un comportamiento indefinido en el estándar del lenguaje C. Sin embargo, tiende a funcionar de todos modos, porque la mayoría de los microprocesadores implementan value >> 32
un desplazamiento de 32 bits (produciendo 0) o un desplazamiento de 0 bits (produciendo el original value
), y cualquiera de los dos produce el resultado correcto en esta aplicación.
Ejemplo
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 sometió a las siguientes operaciones:
desplazamiento circular a la izquierda en 1 posición: | 0010 1101 |
desplazamiento circular a la izquierda en 2 posiciones: | 0101 1010 |
desplazamiento circular a la izquierda en 3 posiciones: | 1011 0100 |
desplazamiento circular a la izquierda en 4 posiciones: | 0110 1001 |
desplazamiento circular a la izquierda en 5 posiciones: | 1101 0010 |
desplazamiento circular a la izquierda en 6 posiciones: | 1010 0101 |
desplazamiento circular a la izquierda en 7 posiciones: | 0100 1011 |
desplazamiento circular a la izquierda en 8 posiciones: | 1001 0110 |
desplazamiento circular a la derecha en 1 posición: | 0100 1011 |
desplazamiento circular a la derecha en 2 posiciones: | 1010 0101 |
desplazamiento circular a la derecha en 3 posiciones: | 1101 0010 |
desplazamiento circular a la derecha en 4 posiciones: | 0110 1001 |
desplazamiento circular a la derecha en 5 posiciones: | 1011 0100 |
desplazamiento circular a la derecha en 6 posiciones: | 0101 1010 |
desplazamiento circular a la derecha en 7 posiciones: | 0010 1101 |
desplazamiento circular a la derecha en 8 posiciones: | 1001 0110 |
Aplicaciones
Los códigos cíclicos son una especie 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 Σ , dejemos que shift ( s ) denote el conjunto de cambios circulares de s , y para un conjunto L de cadenas, que shift ( L ) denote el conjunto de todos los cambios circulares de cadenas en L . Si L es un código cíclico, entonces desplaza ( L ) ⊆ L ; esta es una condición necesaria para que L sea un lenguaje cíclico . El cambio de operación ( L ) se ha estudiado en la teoría del lenguaje formal . Por ejemplo, si L es un lenguaje libre de contexto , entonces shift ( L ) es de nuevo libre de contexto. [6] [7] Además, si L se describe mediante una expresión regular de longitud n , hay una expresión regular de longitud O ( n 3 ) que describe el desplazamiento ( L ). [8]
Ver también
- Cambiador de barril
- Operación bit a bit
- Circulante
- Palabra Lyndon
- Collar : un objeto como una tupla, pero para el que los cambios circulares se consideran equivalentes.
Referencias
- ^ GCC: "Optimizar construcciones de rotación comunes"
- ^ "Limpiezas en el código del combinador ROTL / ROTR DAG" menciona que este código admite la instrucción "rotar" en el CellSPU
- ^ Rotación segura, eficiente y portátil en C / C ++
- ^ Stackoverflow: mejores prácticas para rotaciones en C / C ++
- ^ Rotación de tiempo casi constante que no viola los estándares
- ^ T. Oshiba, "Propiedad de cierre de la familia de lenguajes libres de contexto bajo la operación de cambio cíclico", Transacciones de IECE, 55D : 119-122, 1972.
- ^ AN Maslov, "Operación de cambio cíclico para idiomas", Problemas de transmisión de información 9 : 333–338, 1973.
- ^ Gruber, Hermann; Holzer, Markus (2009). "Operaciones de lenguaje con expresiones regulares de tamaño polinomial" (PDF) . Informática Teórica . 410 (35): 3281–3289. doi : 10.1016 / j.tcs.2009.04.009 . Zbl 1176.68105 . Archivado desde el original (PDF) el 29 de agosto de 2017 . Consultado el 6 de septiembre de 2012 ..