Melhores práticas para operações de deslocamento circular (girar) em C ++

Operadores shift para a esquerda e direita (<< e >>) já estão disponíveis em C ++. No entanto, não consegui descobrir como realizar operações de deslocamento circular ou rotação.

Como operações como "Girar para a esquerda" e "Girar para a direita" podem ser realizadas?

Girando bem duas vezes aqui

Initial --> 1000 0011 0100 0010

deve resultar em:

Final   --> 1010 0000 1101 0000

Um exemplo seria útil.

(nota do editor: muitas maneiras comuns de expressar rotações em C sofrem de comportamento indefinido se a contagem de rotação for zero ou compilar para mais do que apenas uma única instrução de rotação da máquina. A resposta desta pergunta deve documentar as melhores práticas.)

Veja também uma versão anterior desta resposta em outra pergunta rotativa com mais alguns detalhes sobre o que o asm gcc / clang produz para x86.

A maneira mais amigável do compilador de expressar uma rotação em C e C ++ que evita qualquer comportamento indefinido parece ser a implementação de John Regehr . Eu o adaptei para girar pela largura do tipo (usando tipos de largura fixa 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 qualquer tipo de inteiro sem sinal, não apenas uint32_t, para que você possa fazer versões para outros tamanhos.

Veja também uma versão do modelo C ++ 11 com muitas verificações de segurança (incluindo a de static_assertque a largura do tipo é uma potência de 2) , o que não é o caso em alguns DSPs de 24 bits ou mainframes de 36 bits, por exemplo.

Eu recomendo usar apenas o modelo como back-end para wrappers com nomes que incluem a largura de rotação explicitamente. As regras de promoção de inteiros significam que rotl_template(u16 & 0x11UL, 7)faria uma rotação de 32 ou 64 bits, não 16 (dependendo da largura de unsigned long). Even uint16_t & uint16_té promovido signed intpelas regras de promoção de inteiros do C ++, exceto em plataformas onde intnão é mais largo que uint16_t.

No x86 , esta versão se alinha a um únicorol r32, cl (ou rol r32, imm8) com compiladores que o agrupam, porque o compilador sabe que as instruções de rotação e deslocamento do x86 mascaram a contagem de deslocamento da mesma forma que o código-fonte C faz.

Suporte de compilador para este idioma que evita UB em x86, para uint32_t xe unsigned int npara mudanças de contagem de variável:

• clang: reconhecido por rotação de contagem variável desde clang3.5, vários turnos + ou insns antes disso.
• gcc: reconhecido por rotação de contagem variável desde gcc4.9 , múltiplos turnos + ou insns antes disso. O gcc5 e posteriores otimizam o branch e a máscara na versão wikipedia também, usando apenas uma instrução rorou rolpara contagens de variáveis.
• icc: compatível com rotações de contagem variável desde ICC13 ou anterior . A contagem constante gira o uso shld edi,edi,7que é mais lento e leva mais bytes do que rol edi,7em alguns processadores (especialmente AMD, mas também alguns Intel), quando o BMI2 não está disponível para rorx eax,edi,25salvar um MOV.
• MSVC: x86-64 CL19: reconhecido apenas para rotações de contagem constante. (O idioma da Wikipédia é reconhecido, mas o branch e o AND não são otimizados). Use o _rotl/ _rotrintrinsics do <intrin.h>x86 (incluindo x86-64).

gcc para ARM utiliza um and r1, r1, #31para rodar variável de contagem, mas ainda faz a rotação real com uma única instrução : ror r0, r0, r1. Portanto, o gcc não percebe que as contagens de rotação são inerentemente modulares. Como os documentos do ARM dizem, "ROR com comprimento de deslocamento n, mais de 32 é o mesmo que ROR com comprimento de deslocamento n-32" . Acho que o gcc fica confuso aqui porque os deslocamentos para a esquerda / direita no ARM saturam a contagem, portanto, um deslocamento de 32 ou mais limpará o registro. (Ao contrário do x86, em que as mudanças mascaram a contagem da mesma forma que as rotações). Ele provavelmente decide que precisa de uma instrução AND antes de reconhecer o idioma de rotação, por causa de como as mudanças não circulares funcionam naquele destino.

Os compiladores x86 atuais ainda usam uma instrução extra para mascarar uma contagem de variável para rotações de 8 e 16 bits, provavelmente pela mesma razão que eles não evitam o AND no ARM. Esta é uma otimização perdida, porque o desempenho não depende da contagem de rotação em qualquer CPU x86-64. (O mascaramento de contagens foi introduzido no 286 por motivos de desempenho, porque ele lida com os turnos de forma iterativa, não com latência constante como as CPUs modernas.)

BTW, prefira girar para a direita para rotações de contagem variável, para evitar que o compilador 32-nimplemente uma rotação para a esquerda em arquiteturas como ARM e MIPS que fornecem apenas uma rotação para a direita. (Isso otimiza com contagens de constantes de tempo de compilação.)

Curiosidade: ARM realmente não tem mudança dedicado / instruções de rotação, é apenas MOV com a fonte operando a atravessar o cano-shifter em modo ROR : mov r0, r0, ror r1. Portanto, um rotate pode dobrar em um operando de fonte de registro para uma instrução EOR ou algo assim.

Certifique-se de usar tipos não assinados para ne o valor de retorno, ou então não será uma rotação . (gcc para x86 alvos faz deslocamentos aritméticos para a direita, deslocando as cópias do bit de sinal em vez de zeros, levando a um problema quando você ORos dois valores deslocados juntos. Deslocamentos para a direita de inteiros com sinal negativo é um comportamento definido pela implementação em C.)

Além disso, certifique-se de que a contagem de deslocamento seja um tipo sem sinal , porque (-n)&31um tipo com sinal pode ser o complemento ou sinal / magnitude de um, e não o mesmo que o 2 ^ n modular que você obtém com o complemento sem sinal ou de dois. (Veja os comentários na postagem do blog de Regehr). unsigned intfunciona bem em todos os compiladores que eu examinei, para cada largura de x. Alguns outros tipos realmente derrotam o reconhecimento de idioma para alguns compiladores, portanto, não use apenas o mesmo tipo que x.

Alguns compiladores fornecem intrínsecos para rotações , o que é muito melhor do que inline-asm se a versão portátil não gerar um bom código no compilador que você está almejando. Não há intrínsecos de plataforma cruzada para nenhum compilador que eu conheça. Estas são algumas das opções do x86:

• Documentos da Intel que <immintrin.h>fornecem _rotle _rotl64intrínsecos , e o mesmo para o turno certo. MSVC requer <intrin.h>, enquanto gcc requer <x86intrin.h>. An #ifdefcuida do gcc vs. icc, mas o clang não parece fornecê-los em lugar nenhum, exceto no modo de compatibilidade MSVC com-fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . E o conjunto que emite para eles é uma merda (máscara extra e um CMOV).
• MSVC: _rotr8e_rotr16 .
• gcc e icc (não clang): <x86intrin.h>também fornece __rolb/ __rorbpara rotação de 8 bits para a esquerda / direita, __rolw/ __rorw(16 bits), __rold/ __rord(32 bits), __rolq/ __rorq(64 bits, definido apenas para destinos de 64 bits). Para rotações estreitas, a implementação usa __builtin_ia32_rolhiou ...qi, mas as rotações de 32 e 64 bits são definidas usando shift / ou (sem proteção contra UB, porque o código ia32intrin.hsó precisa funcionar no gcc para x86). GNU C parece não ter nenhuma __builtin_rotatefunção de plataforma cruzada da maneira que tem __builtin_popcount(o que se expande para o que for ideal na plataforma de destino, mesmo se não for uma única instrução). Na maioria das vezes, você obtém um bom código de reconhecimento de idioma.

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

Presumivelmente, alguns compiladores não x86 também possuem intrínsecos, mas não vamos expandir esta resposta wiki da comunidade para incluir todos eles. (Talvez faça isso na resposta existente sobre intrínsecos ).

(A versão antiga desta resposta sugeria asm embutidas específicas do MSVC (que funciona apenas para código x86 de 32 bits) ou http://www.devx.com/tips/Tip/14043 para uma versão C. Os comentários estão respondendo a isso .)

O conjunto embutido derrota muitas otimizações , especialmente no estilo MSVC, porque força as entradas a serem armazenadas / recarregadas . Uma rotação embutida asm do GNU C cuidadosamente escrita permitiria que a contagem fosse um operando imediato para contagens de deslocamento da constante de tempo de compilação, mas ainda não poderia otimizar totalmente se o valor a ser deslocado também fosse uma constante de tempo de compilação após inlining. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Por ser C ++, use uma função embutida:

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

A maioria dos compiladores tem intrínsecos para isso. Visual Studio por exemplo _rotr8, _rotr16

Definitivamente:

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

C ++ 20 std::rotlestd::rotr

Chegou! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html e deve adicioná-lo ao <bit>cabeçalho.

cppreference diz que o 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 saída:

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

Vou tentar quando o suporte chegar ao GCC, o GCC 9.1.0 g++-9 -std=c++2aainda não oferece suporte.

A proposta diz:

Cabeçalho:

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;

e:

25.5.5 Rotação [bitops.rot]

Nas descrições a seguir, deixe N denotar std::numeric_limits<T>::digits.

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

Restrições: T é um tipo inteiro sem sinal (3.9.1 [basic.fundamental]).

Seja r s% N.

Retorna: Se r for 0, x; se r for positivo (x << r) | (x >> (N - r)),; se r for negativo rotr(x, -r),.

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

Restrições: T é um tipo inteiro sem sinal (3.9.1 [basic.fundamental]). Seja r s% N.

Retorna: Se r for 0, x; se r for positivo (x >> r) | (x << (N - r)),; se r for negativo rotl(x, -r),.

A std::popcounttambém foi adicionado para contar o número de bits 1: Como contar o número de bits definidos em um inteiro de 32 bits?

Que tal algo assim, usando o bitset padrão ...

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

Se x for um valor de 8 bits, você pode usar isto:

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

Em detalhes, você pode aplicar a seguinte lógica.

Se o padrão de bits for 33602 em número inteiro

1000 0011 0100 0010

e você precisa rolar com 2 deslocamentos para a direita então: primeiro faça uma cópia do padrão de bits e depois desloque para a esquerda: Comprimento - Deslocamento para a direita, ou seja, o comprimento é 16, o valor do deslocamento para a direita é 2 16 - 2 = 14

Depois de 14 vezes à esquerda, você consegue.

1000 0000 0000 0000

Agora mude para a direita o valor 33602, 2 vezes conforme necessário. Você consegue

0010 0000 1101 0000

Agora tome um OR entre 14 vezes o valor deslocado para a esquerda e 2 vezes o valor deslocado para a direita.

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

E você obtém seu valor de rollover alterado. Lembre-se de que as operações bit wise são mais rápidas e isso nem mesmo requer nenhum loop.

Supondo que você deseja mudar os Lbits à direita e a entrada xé um número com Nbits:

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

A resposta correta é a seguinte:

#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 fonte x número de bits

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

outra sugestão

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

Abaixo está uma versão ligeiramente melhorada da resposta de Dídac Pérez , com ambas as direções implementadas, junto com uma demonstração dos usos dessas funções usando unsigned char e unsigned long long values. Várias notas:

1. As funções são embutidas para otimizações do compilador
2. Eu usei um cout << +valuetruque para gerar um caractere sem sinal numericamente que encontrei aqui: https://stackoverflow.com/a/28414758/1599699
3. Eu recomendo usar a <put the type here>sintaxe explícita para clareza e segurança.
4. Usei unsigned char para o parâmetro shiftNum por causa do que encontrei na seção de detalhes adicionais aqui :

O resultado de uma operação de deslocamento é indefinido se a expressão aditiva for negativa ou se a expressão aditiva for maior ou igual ao número de bits na expressão de deslocamento (promovida) .

Este é o código que estou 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.

Sobrecarregar uma função:

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