¿Cuál será el algoritmo de rotación correcto en C?

Uno de los problemas (o “características” si prefiere 🙂 en C es que hay ciertas operaciones que puede expresar en el lenguaje, pero cuyos resultados son, según el estándar C, indefinidos o dependientes de la implementación. significa que el estándar no lo menciona en absoluto o que no hay ningún requisito de que el resultado sea consistente. Si algo depende de la implementación , el diseñador del compilador y la biblioteca en tiempo de ejecución puede hacer que funcione como él o ella lo prefiera, pero al menos debería funcionar siempre de la misma manera en la misma situación.

Una de estas características es el desplazamiento a la derecha de un número firmado. Tradicionalmente, ha habido dos formas de hacer esto (suponiendo que el bit más a la izquierda es el bit de signo): un desplazamiento lógico a la derecha se desplaza en un bit cero. Un desplazamiento aritmético a la derecha duplica el bit de signo. Muchos compiladores de C están diseñados para que el tipo de cambio que se use dependa de si la variable se declara como firmada o no (recuerde que los ints están firmados por defecto, pero los caracteres pueden no estarlo).

¿Qué tipo de cambio quieres si necesitas hacer una rotación correcta, correctamente? Aquí hay una manera de asegurarse de que funciona, independientemente del compilador y qué tipo de desplazamiento a la derecha utiliza:

1. Use una máscara para aislar solo el bit más a la derecha del original y guárdelo en algún lugar.
2. Desplaza el valor original un bit a la derecha.
3. Use una máscara para forzar que el bit más a la izquierda del resultado sea un cero.
4. Tome el bit guardado y muévalo hacia la izquierda hasta que esté en la posición más a la izquierda.
5. Use un OR bit a bit para fusionar esos dos resultados.

Desafortunadamente, conducirá a un comportamiento indefinido si no especificó el tipo de datos.

Por ejemplo: 0x43 => 0100 0011

• Si la variable es char , el resultado será 1010 0001
• Si la variable es short , el resultado será 1000 0000 0010 0001

Vea una versión de plantilla C ++ con muchas comprobaciones de seguridad: Github – Función de plantilla C ++ 11 para realizar rotaciones de enteros sin invocar un comportamiento indefinido

Ni siquiera estoy seguro de lo que esto significa, ¿quieres decir rotar los bits de datos a la derecha? Si x es un personaje

x = (x >> 1) | (x << 7);

Funciona para un tipo de datos de 8 bits. Reemplace el 7 con 15 para un número de 2 bytes, 31 para 4 bytes, etc.