Mejores prácticas para operaciones de cambio circular (rotar) en C ++

Los operadores de desplazamiento a la izquierda y a la derecha (<< y >>) ya están disponibles en C ++. Sin embargo, no pude averiguar cómo podría realizar operaciones de rotación o desplazamiento circular.

¿Cómo se pueden realizar operaciones como "Girar a la izquierda" y "Girar a la derecha"?

Girando a la derecha dos veces aquí

Initial --> 1000 0011 0100 0010

debería resultar en:

Final   --> 1010 0000 1101 0000

Un ejemplo sería útil.

(Nota del editor: muchas formas comunes de expresar rotaciones en C sufren un comportamiento indefinido si el recuento de rotaciones es cero o se compilan en más de una sola instrucción de máquina de rotación. La respuesta de esta pregunta debe documentar las mejores prácticas).

Consulte también una versión anterior de esta respuesta en otra pregunta rotativa con algunos detalles más sobre lo que produce asm gcc / clang para x86.

La forma más fácil de compilar de expresar una rotación en C y C ++ que evita cualquier comportamiento indefinido parece ser la implementación de John Regehr . Lo adapté para rotar por el ancho del tipo (usando tipos de ancho fijo como uint32_t).

#include <stdint.h>   // for uint32_t
#include <limits.h>   // for CHAR_BIT
// #define NDEBUG
#include <assert.h>

static inline uint32_t rotl32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);  // assumes width is a power of 2.

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n<<c) | (n>>( (-c)&mask ));
}

static inline uint32_t rotr32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n>>c) | (n<<( (-c)&mask ));
}

Funciona para cualquier tipo de entero sin signo, no solo uint32_t, por lo que podría hacer versiones para otros tamaños.

Consulte también una versión de plantilla de C ++ 11 con muchas comprobaciones de seguridad (incluida la de static_assertque el ancho del tipo es una potencia de 2) , que no es el caso en algunos DSP de 24 bits o mainframes de 36 bits, por ejemplo.

Recomendaría usar solo la plantilla como back-end para contenedores con nombres que incluyan explícitamente el ancho de rotación. Las reglas de promoción de enteros significan que rotl_template(u16 & 0x11UL, 7)haría una rotación de 32 o 64 bits, no 16 (dependiendo del ancho de unsigned long). Even uint16_t & uint16_tes promovido signed intpor las reglas de promoción de enteros de C ++, excepto en plataformas donde intno es más ancho que uint16_t.

En x86 , esta versión se integra en un solorol r32, cl (o rol r32, imm8) con compiladores que lo asimilan, porque el compilador sabe que las instrucciones de rotación y desplazamiento x86 enmascaran el recuento de turnos de la misma manera que lo hace la fuente C.

Soporte del compilador para este modismo que evita UB en x86, para uint32_t xy unsigned int npara cambios de conteo variable:

• clang: reconocido por rotaciones de conteo variable desde clang3.5, múltiples turnos + o insns antes de eso.
• gcc: reconocido para rotaciones de conteo variable desde gcc4.9 , múltiples turnos + o insns antes de eso. gcc5 y posteriores también optimizan la rama y la máscara en la versión de wikipedia, usando solo una instrucción roro rolpara recuentos de variables.
• icc: compatible con rotaciones de conteo variable desde ICC13 o antes . El conteo constante rota el uso, shld edi,edi,7que es más lento y ocupa más bytes que rol edi,7en algunas CPU (especialmente AMD, pero también algunas Intel), cuando BMI2 no está disponible para rorx eax,edi,25guardar un MOV.
• MSVC: x86-64 CL19: solo se reconoce para rotaciones de conteo constante. (Se reconoce el idioma de wikipedia, pero la rama y Y no están optimizados). Utilice _rotl/ _rotrintrinsics desde <intrin.h>x86 (incluido x86-64).

GCC para ARM utiliza una and r1, r1, #31para gira variable de conteo, pero todavía lo hace la rotación real con una sola instrucción : ror r0, r0, r1. Entonces, gcc no se da cuenta de que los conteos rotativos son inherentemente modulares. Como dicen los documentos de ARM, "ROR con longitud de turno n, más de 32 es lo mismo que ROR con longitud de turno n-32" . Creo que gcc se confunde aquí porque los cambios de izquierda a derecha en ARM saturan el recuento, por lo que un cambio de 32 o más borrará el registro. (A diferencia de x86, donde los cambios enmascaran el recuento de la misma manera que los giros). Probablemente decida que necesita una instrucción AND antes de reconocer el idioma de rotación, debido a cómo funcionan los turnos no circulares en ese objetivo.

Los compiladores x86 actuales todavía usan una instrucción adicional para enmascarar un recuento de variables para rotaciones de 8 y 16 bits, probablemente por la misma razón por la que no evitan el AND en ARM. Esta es una optimización perdida, porque el rendimiento no depende del recuento de rotaciones en ninguna CPU x86-64. (El enmascaramiento de recuentos se introdujo con 286 por razones de rendimiento porque manejaba los cambios de forma iterativa, no con latencia constante como las CPU modernas).

Por cierto, prefiera rotar a la derecha para rotaciones de recuento variable, para evitar que el compilador 32-nimplemente una rotación a la izquierda en arquitecturas como ARM y MIPS que solo proporcionan una rotación a la derecha. (Esto se optimiza con conteos de constantes de tiempo de compilación).

Dato curioso: ARM no tiene realmente turno dedicada / instrucciones de rotación, es sólo MOV con la fuente de operando de pasar por el cañón-palanca de cambios en el modo de ROR : mov r0, r0, ror r1. Entonces, una rotación puede plegarse en un operando de fuente de registro para una instrucción EOR o algo así.

Asegúrese de usar tipos sin firmar para ny el valor de retorno, o de lo contrario no será una rotación . (gcc para destinos x86 hace cambios aritméticos a la derecha, cambiando copias del bit de signo en lugar de ceros, lo que genera un problema cuando se ORcambian los dos valores juntos. Los cambios a la derecha de enteros con signo negativo es un comportamiento definido por la implementación en C.)

Además, asegúrese de que el recuento de turnos sea un tipo sin signo , porque (-n)&31con un tipo con signo podría ser el complemento de uno o el signo / magnitud, y no el mismo que el 2 ^ n modular que obtiene con el complemento de dos o sin signo. (Ver comentarios en la publicación del blog de Regehr). unsigned intfunciona bien en todos los compiladores que he visto, para cada ancho de x. Algunos otros tipos en realidad anulan el reconocimiento idiomático de algunos compiladores, así que no use simplemente el mismo tipo que x.

Algunos compiladores proporcionan elementos intrínsecos para rotaciones , que es mucho mejor que inline-asm si la versión portátil no genera un buen código en el compilador al que se dirige. No hay elementos intrínsecos multiplataforma para ningún compilador que yo conozca. Estas son algunas de las opciones de x86:

• Intel <immintrin.h>proporciona_rotl_rotl64 documentos e intrínsecos , y lo mismo para el turno correcto. MSVC requiere <intrin.h>, mientras que gcc requiere <x86intrin.h>. An #ifdefse encarga de gcc frente a icc, pero clang no parece proporcionarlos en ninguna parte, excepto en el modo de compatibilidad MSVC con-fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . Y el conjunto que emite para ellos apesta (enmascaramiento extra y un CMOV).
• MSVC: _rotr8y_rotr16 .
• gcc y icc (no clang): <x86intrin.h>también proporciona __rolb/ __rorbpara rotación izquierda / derecha de 8 bits, __rolw/ __rorw(16 bits), __rold/ __rord(32 bits), __rolq/ __rorq(64 bits, solo definido para destinos de 64 bits). Para rotaciones estrechas, la implementación usa __builtin_ia32_rolhio ...qi, pero las rotaciones de 32 y 64 bits se definen usando shift / o (sin protección contra UB, porque el código ia32intrin.hsolo tiene que funcionar en gcc para x86). GNU C parece no tener ninguna __builtin_rotatefunción multiplataforma de la forma en que lo hace __builtin_popcount(lo que se expande a lo que sea óptimo en la plataforma de destino, incluso si no es una sola instrucción). La mayoría de las veces se obtiene un buen código del reconocimiento de idiomas.

// For real use, probably use a rotate intrinsic for MSVC, or this idiom for other compilers.  This pattern of #ifdefs may be helpful
#if defined(__x86_64__) || defined(__i386__)

#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>  // Not just <immintrin.h> for compilers other than icc
#endif

uint32_t rotl32_x86_intrinsic(rotwidth_t x, unsigned n) {
  //return __builtin_ia32_rorhi(x, 7);  // 16-bit rotate, GNU C
  return _rotl(x, n);  // gcc, icc, msvc.  Intel-defined.
  //return __rold(x, n);  // gcc, icc.
  // can't find anything for clang
}
#endif

Es de suponer que algunos compiladores que no son x86 también tienen elementos intrínsecos, pero no ampliemos esta respuesta de la wiki comunitaria para incluirlos a todos. (Tal vez haga eso en la respuesta existente sobre intrínsecos ).

(La versión anterior de esta respuesta sugería un conjunto en línea específico de MSVC (que solo funciona para código x86 de 32 bits), o http://www.devx.com/tips/Tip/14043 para una versión C. Los comentarios responden a eso .)

Asm en línea derrota muchas optimizaciones , especialmente el estilo MSVC porque obliga a que las entradas se almacenen / recarguen . Una rotación de ensamblaje en línea de GNU C cuidadosamente escrita permitiría que el recuento sea un operando inmediato para los recuentos de cambios constantes en tiempo de compilación, pero aún así no se podría optimizar por completo si el valor que se va a cambiar es también una constante en tiempo de compilación después de la alineación. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Dado que es C ++, use una función en línea:

template <typename INT> 
INT rol(INT val) {
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

Variante de C ++ 11:

template <typename INT> 
constexpr INT rol(INT val) {
    static_assert(std::is_unsigned<INT>::value,
                  "Rotate Left only makes sense for unsigned types");
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

La mayoría de los compiladores tienen elementos intrínsecos para eso. Visual Studio, por ejemplo _rotr8, _rotr16

Definitivamente:

template<class T>
T ror(T x, unsigned int moves)
{
  return (x >> moves) | (x << sizeof(T)*8 - moves);
}

C ++ 20 std::rotlystd::rotr

¡Ha llegado! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html y debería agregarlo al <bit>encabezado.

cppreference dice que el uso será como:

#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t i = 0b00011101;
    std::cout << "i          = " << std::bitset<8>(i) << '\n';
    std::cout << "rotl(i,0)  = " << std::bitset<8>(std::rotl(i,0)) << '\n';
    std::cout << "rotl(i,1)  = " << std::bitset<8>(std::rotl(i,1)) << '\n';
    std::cout << "rotl(i,4)  = " << std::bitset<8>(std::rotl(i,4)) << '\n';
    std::cout << "rotl(i,9)  = " << std::bitset<8>(std::rotl(i,9)) << '\n';
    std::cout << "rotl(i,-1) = " << std::bitset<8>(std::rotl(i,-1)) << '\n';
}

dando salida:

i          = 00011101
rotl(i,0)  = 00011101
rotl(i,1)  = 00111010
rotl(i,4)  = 11010001
rotl(i,9)  = 00111010
rotl(i,-1) = 10001110

Lo intentaré cuando llegue el soporte a GCC, GCC 9.1.0 g++-9 -std=c++2aaún no lo admite.

La propuesta dice:

Encabezamiento:

namespace std {
  // 25.5.5, rotating   
  template<class T>
    [[nodiscard]] constexpr T rotl(T x, int s) noexcept;
  template<class T>
    [[nodiscard]] constexpr T rotr(T x, int s) noexcept;

y:

25.5.5 Rotación [bitops.rot]

En las siguientes descripciones, denote n std::numeric_limits<T>::digits.

template<class T>
  [[nodiscard]] constexpr T rotl(T x, int s) noexcept;

Restricciones: T es un tipo entero sin signo (3.9.1 [básico.fundamental]).

Sea r s% N.

Devuelve: Si r es 0, x; si r es positivo (x << r) | (x >> (N - r)); si r es negativo, rotr(x, -r).

template<class T>
  [[nodiscard]] constexpr T rotr(T x, int s) noexcept;

Restricciones: T es un tipo entero sin signo (3.9.1 [básico.fundamental]). Sea r s% N.

Devuelve: Si r es 0, x; si r es positivo (x >> r) | (x << (N - r)); si r es negativo, rotl(x, -r).

También std::popcountse agregó A para contar el número de 1 bits: ¿Cómo contar el número de bits establecidos en un entero de 32 bits?

Qué tal algo como esto, usando el conjunto de bits estándar ...

#include <bitset> 
#include <iostream> 

template <std::size_t N> 
inline void 
rotate(std::bitset<N>& b, unsigned m) 
{ 
   b = b << m | b >> (N-m); 
} 

int main() 
{ 
   std::bitset<8> b(15); 
   std::cout << b << '\n'; 
   rotate(b, 2); 
   std::cout << b << '\n'; 

   return 0;
}

HTH,

Si x es un valor de 8 bits, puede usar esto:

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

En detalle, puede aplicar la siguiente lógica.

Si el patrón de bits es 33602 en entero

1000 0011 0100 0010

y necesita pasar con 2 cambios a la derecha y luego: primero haga una copia del patrón de bits y luego a la izquierda: Longitud - Cambio a la derecha, es decir, la longitud es 16 El valor de cambio a la derecha es 2 16 - 2 = 14

Después de 14 cambios a la izquierda, obtienes.

1000 0000 0000 0000

Ahora cambie a la derecha el valor 33602, 2 veces según sea necesario. Usted obtiene

0010 0000 1101 0000

Ahora tome un OR entre 14 veces el valor desplazado a la izquierda y 2 veces el valor desplazado a la derecha.

1000 0000 0000 0000
0010 0000 1101 0000
===================
1010 0000 1101 0000
===================

Y obtiene su valor de rollover cambiado. Recuerde que las operaciones de bits son más rápidas y esto ni siquiera requiere ningún bucle.

Suponiendo que desea desplazarse a la derecha en Lbits, y la entrada xes un número con Nbits:

unsigned ror(unsigned x, int L, int N) 
{
    unsigned lsbs = x & ((1 << L) - 1);
    return (x >> L) | (lsbs << (N-L));
}

La respuesta correcta es la siguiente:

#define BitsCount( val ) ( sizeof( val ) * CHAR_BIT )
#define Shift( val, steps ) ( steps % BitsCount( val ) )
#define ROL( val, steps ) ( ( val << Shift( val, steps ) ) | ( val >> ( BitsCount( val ) - Shift( val, steps ) ) ) )
#define ROR( val, steps ) ( ( val >> Shift( val, steps ) ) | ( val << ( BitsCount( val ) - Shift( val, steps ) ) ) )

Código fuente x número de bit

int x =8;
data =15; //input
unsigned char tmp;
for(int i =0;i<x;i++)
{
printf("Data & 1    %d\n",data&1);
printf("Data Shifted value %d\n",data>>1^(data&1)<<(x-1));
tmp = data>>1|(data&1)<<(x-1);
data = tmp;  
}

otra sugerencia

template<class T>
inline T rotl(T x, unsigned char moves){
    unsigned char temp;
    __asm{
        mov temp, CL
        mov CL, moves
        rol x, CL
        mov CL, temp
    };
    return x;
}

A continuación se muestra una versión ligeramente mejorada de la respuesta de Dídac Pérez , con ambas direcciones implementadas, junto con una demostración de los usos de estas funciones utilizando valores largos sin firmar y sin firmar. Varias notas:

1. Las funciones están integradas para optimizaciones del compilador
2. cout << +valueUsé un truco para generar concisamente un carácter sin firmar numéricamente que encontré aquí: https://stackoverflow.com/a/28414758/1599699
3. Recomiendo usar la <put the type here>sintaxis explícita para mayor claridad y seguridad.
4. Usé char sin firmar para el parámetro shiftNum debido a lo que encontré en la sección Detalles adicionales aquí :

El resultado de una operación de desplazamiento no está definido si la expresión-aditiva es negativa o si la expresión-aditiva es mayor o igual que el número de bits en la expresión-desplazamiento (promovida) .

Aquí está el código que estoy usando:

#include <iostream>

using namespace std;

template <typename T>
inline T rotateAndCarryLeft(T rotateMe, unsigned char shiftNum)
{
    static const unsigned char TBitCount = sizeof(T) * 8U;

    return (rotateMe << shiftNum) | (rotateMe >> (TBitCount - shiftNum));
}

template <typename T>
inline T rotateAndCarryRight(T rotateMe, unsigned char shiftNum)
{
    static const unsigned char TBitCount = sizeof(T) * 8U;

    return (rotateMe >> shiftNum) | (rotateMe << (TBitCount - shiftNum));
}

void main()
{
    //00010100 == (unsigned char)20U
    //00000101 == (unsigned char)5U == rotateAndCarryLeft(20U, 6U)
    //01010000 == (unsigned char)80U == rotateAndCarryRight(20U, 6U)

    cout << "unsigned char " << 20U << " rotated left by 6 bits == " << +rotateAndCarryLeft<unsigned char>(20U, 6U) << "\n";
    cout << "unsigned char " << 20U << " rotated right by 6 bits == " << +rotateAndCarryRight<unsigned char>(20U, 6U) << "\n";

    cout << "\n";


    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
    {
        cout << "unsigned char " << 21U << " rotated left by " << +shiftNum << " bit(s) == " << +rotateAndCarryLeft<unsigned char>(21U, shiftNum) << "\n";
    }

    cout << "\n";

    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
    {
        cout << "unsigned char " << 21U << " rotated right by " << +shiftNum << " bit(s) == " << +rotateAndCarryRight<unsigned char>(21U, shiftNum) << "\n";
    }


    cout << "\n";

    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
    {
        cout << "unsigned long long " << 3457347ULL << " rotated left by " << +shiftNum << " bit(s) == " << rotateAndCarryLeft<unsigned long long>(3457347ULL, shiftNum) << "\n";
    }

    cout << "\n";

    for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
    {
        cout << "unsigned long long " << 3457347ULL << " rotated right by " << +shiftNum << " bit(s) == " << rotateAndCarryRight<unsigned long long>(3457347ULL, shiftNum) << "\n";
    }

    cout << "\n\n";
    system("pause");
}

--- Substituting RLC in 8051 C for speed --- Rotate left carry
Here is an example using RLC to update a serial 8 bit DAC msb first:
                               (r=DACVAL, P1.4= SDO, P1.5= SCLK)
MOV     A, r
?1:
MOV     B, #8
RLC     A
MOV     P1.4, C
CLR     P1.5
SETB    P1.5
DJNZ    B, ?1

Here is the code in 8051 C at its fastest:
sbit ACC_7  = ACC ^ 7 ; //define this at the top to access bit 7 of ACC
ACC     =   r;
B       =   8;  
do  {
P1_4    =   ACC_7;  // this assembles into mov c, acc.7  mov P1.4, c 
ACC     <<= 1;
P1_5    =   0;
P1_5    =   1;
B       --  ; 
    } while ( B!=0 );
The keil compiler will use DJNZ when a loop is written this way.
I am cheating here by using registers ACC and B in c code.
If you cannot cheat then substitute with:
P1_4    =   ( r & 128 ) ? 1 : 0 ;
r     <<=   1;
This only takes a few extra instructions.
Also, changing B for a local var char n is the same.
Keil does rotate ACC left by ADD A, ACC which is the same as multiply 2.
It only takes one extra opcode i think.
Keeping code entirely in C keeps things simpler sometimes.

Sobrecargar una función:

unsigned int rotate_right(unsigned int x)
{
 return (x>>1 | (x&1?0x80000000:0))
}

unsigned short rotate_right(unsigned short x) { /* etc. */ }

#define ROTATE_RIGHT(x) ( (x>>1) | (x&1?0x8000:0) )