c++ - operaciones - operadores de desplazamiento en java

Mejores prácticas para operaciones de desplazamiento circular(rotación) en C++

Question

Los operadores de desplazamiento izquierdo y derecho (<< y >>) ya están disponibles en C ++. Sin embargo, no pude averiguar cómo podía realizar operaciones circulares de cambio o rotación.

¿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 adolecen de un comportamiento indefinido si el recuento de rotación es cero o compilan más que una sola instrucción de máquina rotativa. La respuesta de esta pregunta debe documentar las mejores prácticas).

Answer 1

¿Cómo puede ser 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,

Answer 2

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 que utilizan caracteres sin signo y valores largos no anotados. Varias notas:

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

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 la cantidad de bits en la expresión-cambio (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");
}

Answer 3

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;  
}

Answer 4

Como 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 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));
}

Answer 5

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

La forma más amigable con el compilador de expresar una rotación en C y C ++ que evita cualquier comportamiento indefinido parece ser la implementación de John Regehr . Lo he adaptado para rotar por el ancho del tipo (por ejemplo, suponiendo que uint32_t tiene exactamente 32 bits de ancho, aunque C / C ++ solo garantiza que sea al menos tan ancho. Intenté mantenerlo legible omitiendo los cheques para ese tipo de la cosa).

#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.

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

Yo recomendaría usar solo la plantilla como un back-end para envoltorios con nombres que incluyen el ancho de rotación explícitamente. 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 la unsigned long ). Incluso uint16_t & uint16_t se promueve a signed int por las reglas de promoción de C ++, excepto en plataformas donde int no es más ancho que uint16_t .

En x86 , esta versión se basa en un único rol r32, cl (o rol r32, imm8 ) con compiladores que lo asimilan, porque el compilador sabe que las instrucciones x86 de rotación y desplazamiento ocultan el recuento de cambios de la misma manera que la fuente C.

Compatibilidad con el compilador para esta expresión UB- uint32_t x en x86, para uint32_t x y unsigned int n para cambios de conteo de variables:

• clang: reconocido por conteo variable, rota desde clang3.5, cambios múltiples o insns antes de eso.
• gcc: reconocido por conteo variable gira desde gcc4.9 , cambios múltiples o insns antes de eso. gcc5 y posterior optimiza la bifurcación y la máscara en la versión de wikipedia, también, usando solo una instrucción ror o rol para conteos de variables.
• icc: compatible con rotaciones de conteo variable desde ICC13 o anterior . El conteo constante gira usa shld edi,edi,7 que es más lento y toma más bytes que rol edi,7 en algunas CPU (especialmente AMD, pero también algo de Intel), cuando BMI2 no está disponible para rorx eax,edi,25 a guardar un MOV
• MSVC: x86-64 CL19: solo se reconoce para conteo constante gira. (Se reconoce el modismo wikipedia, pero la rama y AND no se optimizan). Utilice los intrínsecos _rotl / _rotr desde <intrin.h> en x86 (incluyendo x86-64).

gcc para ARM usa an and r1, r1, #31 para conteo variable gira, pero aún hace la rotación real con una sola instrucción : ror r0, r0, r1 . Entonces, gcc no se da cuenta de que los recuentos de rotación son intrínsecamente modulares. Como dicen los ARM, "ROR con longitud de desplazamiento, n , más de 32 es lo mismo que ROR con longitud de desplazamiento n-32 " . Creo que gcc se confunde aquí porque los cambios de izquierda / derecha en ARM saturan el conteo, 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 rota). Probablemente decida que necesita una instrucción AND antes de reconocer el idioma de rotación, debido a cómo los cambios no circulares funcionan en ese objetivo.

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

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

Dato curioso: ARM realmente no tiene instrucciones dedicadas de cambio / rotación, solo es MOV con el operando fuente pasando por la palanca de cambios en el modo ROR : mov r0, r0, ror r1 . Por lo tanto, una rotación puede doblarse en un operando de fuente de registro para una instrucción EOR o algo así.

Asegúrese de utilizar tipos sin firmar para n el valor de retorno, de lo contrario no será una rotación . (gcc para objetivos x86 realiza desplazamientos aritméticos a la derecha, desplazando copias del bit de signo en lugar de ceros, lo que genera un problema cuando OR los dos valores desplazados juntos. Los desplazamientos a la derecha de enteros con signo negativo son comportamientos definidos por la implementación en C. )

Además, asegúrese de que el recuento de turnos sea un tipo sin signo , porque (-n)&31 con un tipo firmado puede ser complemento o signo / magnitud de uno, y no el mismo que el 2 ^ n modular que obtiene con el complemento sin signo o dos. (Ver comentarios en la publicación de blog de Regehr). unsigned int funciona bien en cada compilador que he analizado, para cada ancho de x . Algunos otros tipos realmente vencieron el reconocimiento idiomático de algunos compiladores, así que no uses el mismo tipo que x .

Algunos compiladores proporcionan intrínsecos para las rotaciones , lo que es mucho mejor que el asalto en línea si la versión portátil no genera un buen código en el compilador al que se dirige. No existen intrínsecos multiplataforma para compiladores que yo sepa. Estas son algunas de las opciones x86:

• Intel documenta que <immintrin.h> proporciona _rotl y _rotl64 intrinsics , y lo mismo para right shift. MSVC requiere <intrin.h> , mientras que gcc requiere <x86intrin.h> . Un #ifdef se ocupa de gcc vs. icc, pero clang no parece proporcionarlos en ningún lado, excepto en el modo de compatibilidad -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 con -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . Y el asm que emite para ellos aspira (enmascaramiento adicional y un CMOV).
• _rotr8 : _rotr8 y _rotr16 .
• gcc e icc (no clang): <x86intrin.h> también proporciona __rolb / __rorb para __rorb de 8 bits hacia la izquierda / derecha, __rolw / __rorw (16-bit), __rold / __rord (32-bit), __rolq / __rorq (64 -bit, solo definido para objetivos de 64 bits). Para __builtin_ia32_rolhi estrechas, la implementación usa __builtin_ia32_rolhi o ...qi , pero las __builtin_ia32_rolhi 32 y 64 bits se definen usando shift / or (sin protección contra UB, porque el código en ia32intrin.h solo tiene que funcionar en gcc para x86 ) Parece que GNU C no tiene ninguna función __builtin_rotate multiplataforma de la misma forma que lo hace para __builtin_popcount (que se expande a lo que sea óptimo en la plataforma de destino, incluso si no es una instrucción única). La mayoría de las veces obtienes un buen código de reconocimiento idiomático.

// 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 sean x86 también tienen intrínsecos, pero no ampliemos esta respuesta wiki de comunidad para incluirlos a todos. (Tal vez hacer eso en la respuesta existente sobre intrínsecos ).

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

El asm en línea derrota muchas optimizaciones , especialmente el estilo MSVC porque obliga a las entradas a ser almacenadas / recargadas . Una rotación de GNU C inline-asm cuidadosamente escrita permitiría que el recuento sea un operando inmediato para recuentos de turnos constantes de tiempo de compilación, pero aún no podría optimizarse completamente si el valor que se va a desplazar también es una constante de tiempo de compilación después de la línea. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Answer 6

Definitivamente:

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

Answer 7

En detalles puede aplicar la siguiente lógica.

Si el patrón de bits es 33602 en entero

1000 0011 0100 0010

y necesita volcar con 2 cambios a la derecha y luego: primero hacer una copia del patrón de bits y luego desplazarlo a la izquierda: Longitud - Desplazamiento a la derecha, es decir, la longitud es 16 El valor de desplazamiento a la derecha es 2 16 - 2 = 14

Después de 14 vueltas 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 obtienes tu valor de transferencia desplazado. Recuerde que las operaciones de bits son más rápidas y esto ni siquiera requiere ningún ciclo.

Answer 8

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

Answer 9

La respuesta correcta es 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 ) ) ) )

Answer 10

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

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

Answer 11

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. */ }

Answer 12

Suponiendo que desea desplazar a la derecha en L bits, y la entrada x es un número con N bits:

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

Answer 13

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;
}

Answer 14

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

Answer 15

--- 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.