Desplazamiento circular en c

¿Cómo funciona el siguiente código y qué significan las variables?

y = (x <> (sizeof(x)*CHAR_BIT - shift)); 

Lo encontré en un artículo de turno circular pero sin explicación sobre cómo funciona esto.

CHAR_BIT es el número de bits por byte, debe ser 8 siempre.

shift es el número de bits que desea desplazar a la izquierda de forma circular, por lo que los bits que se desplazan hacia la izquierda regresan a la derecha.

  1110 0000 << 2 results in: 1000 0011 

Código para el ejemplo:

  y = (x << 2) | (x >> (8 - 2)); 

Este es un método de hacer un cambio circular. Supongamos que x es 8 bits.

 + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- +
 |  x1 x2 x3 x4 x5 x6 x7 x8 |
 + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- +

Luego, al desplazarlo a la izquierda por 3 nos da:

 + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- +
 |  x4 x5 x6 x7 x8 0 0 0 |
 + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- +

Ahora, CHAR_BIT*sizeof(x) es el mismo que el ancho de x en bits, 8. Entonces, al desplazar x a la derecha por 8 - 3 nos da:

 + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- +
 |  0 0 0 0 0 x1 x2 x3 |
 + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- +

Y tomando el OR obtienes:

 + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- +
 |  x4 x5 x6 x7 x8 x1 x2 x3 |
 + ---- + ---- + ---- + ---- + ---- + ---- + ---- + ---- +

Esto es técnicamente no portátil porque no es portátil desplazarse en una cantidad igual al ancho del tipo, por lo que si el desplazamiento es 8, entonces el desplazamiento a la izquierda es incorrecto y si el desplazamiento es 0, entonces el desplazamiento a la derecha Está Mal. Sin embargo, esto funciona en la práctica en los tres comportamientos comunes cuando se desplaza por el ancho de tipo. (En la práctica, la cantidad de desplazamiento se reduce en algún módulo, ya sea el ancho de bits del tipo o un número mayor).

Se denomina cambio circular o “rotación” porque los bits que se desplazan hacia la izquierda se vuelven a desplazar hacia la derecha.

Los comstackdores sofisticados comstackrán el código en una instrucción de rotación de hardware.

 (x << shift) 

Desplaza el número de bits de 'desplazamiento' hacia la izquierda, devuelve los bits desplazados

 (x >> (sizeof(x)*CHAR_BIT - shift)); 

Hace espacio para acomodar esos bits

CHAR_BIT es el número de bits en char, así que es 8 en su mayoría. En C, no maneja un bit a la vez, pero como mínimo, el número de bits de char. Así que esa es la granularidad que obtienes.

En general,

Para un char, cuando haces una rotación de bits, lo harías en un campo de 8 bits (1 byte)

Para un int, cuando haces una rotación, lo harías en un campo de 32 bits (4 bytes)


Ejemplo con 8 bits:

 x = 11010101 shift = 2 x << (2) = 01010100 //shifted right by 2 bits = x >> ((1 * CHAR_BIT) - 2) = x >> (6) = 00000011 //shifted left by 6bits 

OR estos poco a poco para dar

 01010101 00000011 ________ 01010111 

Ese es el valor circular desplazado por 2 bits.

Esto funciona solo con tipos sin firmar. En el caso de un número negativo con signo, la mayoría de los bits a la izquierda se sustituirán por el valor del bit más significativo (con 1-s) por el operador de desplazamiento a la derecha (“>>”)

Yo lo escribiría así:

 y = (x << shift) | ( (x >> (sizeof(x)*CHAR_BIT - shift)) & (0x7F >> (sizeof(x)*CHAR_BIT - shift) ); 

Aquí antes de “|” el operador confirmamos que los primeros n bits (n = sizeof (x) * CHAR_BIT – shift) se ponen a cero. También asumimos que x es corto (2 bytes de longitud). Por lo tanto, también es de tipo dependiente.