Melhores práticas para a mudança circular (rodar) operações em C ++

https://stackoverflow.com/questions/776508

13-09-2019
|

Pergunta

Esquerda e operadores de deslocamento para a direita (<< e >>) já estão disponíveis em C ++. No entanto, eu não conseguia saber como eu poderia executar a deslocação circular ou operações de rotação.

Como pode operações como "Girar para a esquerda" e "Rotate Right" ser realizada?

Rotação direita duas vezes aqui

Initial --> 1000 0011 0100 0010

deve resultar em:

Final   --> 1010 0000 1101 0000

Um exemplo seria útil.

(Nota do editor:.. Muitas formas comuns de expressar gira em C sofrem de comportamento indefinido se a contagem de rotação é zero, ou compilação de mais do que apenas uma única instrução de máquina girar resposta deste pergunta deve documentar as melhores práticas)

Solução

Veja também uma versão anterior do esta resposta em outro questão girar com mais alguns detalhes sobre o que asm gcc / clang produtos para x86. |

A forma mais-compiler amigável para expressar uma rotação em C e C ++ que evita qualquer comportamento indefinido parece estar implementação de John Regehr. Eu adaptado para rotação 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 inteiro sem sinal, não apenas uint32_t, então você poderia fazer versões para outros tamanhos. |

Veja também um C ++ 11 modelo da versão com muitas verificações de segurança ( incluindo um static_assert que o tipo de largura é uma potência de 2) , que não é o caso em algumas DSP de 24 bits ou 36 bits minicomputadores, por exemplo.

Eu recomendo usar apenas o modelo como um back-end para invólucros com nomes que incluem a largura de rotação de forma explícita. regras Integer-promoção significa que rotl_template(u16 & 0x11UL, 7) faria uma rotação de 32 ou 64 bits, não 16 (dependendo da largura de unsigned long). Mesmo uint16_t & uint16_t é promovido a signed int pelo C ++ 's regras inteiro de promoção, exceto em plataformas onde int não é mais vasto do que uint16_t.

Em x86 , esta versão inlines para um único rol r32, cl (ou rol r32, imm8) com compiladores que Grok-lo, porque o compilador sabe que x86 rotação e deslocamento instruções mascarar o deslocamento contar da mesma maneira a fonte C faz.

suporte Compiler para este-UB evitando idioma em x86, para uint32_t x e unsigned int n para mudanças variável de contagem:

clang:. Reconhecido por gira variável de contagem desde clang3.5, vários turnos + ou insns antes que

gcc: reconhecido por gira variável de contagem desde gcc4.9 , vários turnos + ou insns antes disso. gcc5 e depois otimizar afastado do ramo e máscara na versão wikipedia, também, usando apenas um ror ou instrução rol para a contagem de variáveis.

ICC: suportado para Variável contar gira desde ICC13 ou anterior . gira constante de contagem usar shld edi,edi,7 que é mais lento e leva mais bytes do que rol edi,7 em algumas CPUs (especialmente AMD, mas também alguns Intel), quando BMI2 não está disponível para rorx eax,edi,25 para salvar um MOV.

MSVC: CL19 x86-64: Apenas reconhecido por gira constante de contagem. (O idioma wikipedia é reconhecido, mas o ramo e E não são otimizados de distância). Use os intrínsecos _rotl / _rotr de <intrin.h> em x86 (incluindo x86-64).

gcc para ARM utiliza um and r1, r1, #31 para gira variável de contagem, mas ainda faz a rotação real com uma única instrução : ror r0, r0, r1. Então gcc não percebe que giram contagens são inerentemente modular. Como os docs ARM dizer: "ROR com um comprimento de deslocamento, n, mais do que 32 é a mesma como ROR com comprimento mudança n-32 ". Acho gcc fica confuso aqui porque esquerda / direita turnos no braço saturar a contagem, então uma mudança por 32 ou mais irá limpar o registo. (Ao contrário x86, em que mudanças de mascarar a contagem o mesmo que roda). Provavelmente decide que precisa de uma instrução AND antes de reconhecer o idioma rotação, por causa de como as mudanças não circular trabalhar nisso alvo.

compiladores x86 atuais ainda usam uma instrução extra para mascarar uma contagem variável para rodar 8 e 16 bits, provavelmente pela mesma razão que não evitar o E em ARM. Esta é uma otimização perdeu, porque o desempenho não depende da contagem de rotação em qualquer CPU x86-64. (Mascaramento de contagens foi introduzido com 286 por motivos de desempenho porque tratado turnos de forma iterativa, não com constante latência como processadores modernos.)

BTW, prefiro rodar para a direita para rodar variável de contagem, para evitar que o compilador fazer 32-n para implementar uma rotação esquerda em arquiteturas como ARM e MIPS que apenas fornecem um rodar para a direita. (Isto optimiza distância com ccontagem ompile-constante de tempo.)

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

Certifique-se de usar tipos não assinados para n eo valor de retorno, ou então não será uma rotação . (Gcc para x86 alvos faz mudanças certas aritméticas, mudando em cópias do sinal de bits em vez de zeros, levando a um problema quando você OR os dois deslocou valores juntos. Botão direito do mudanças de inteiros negativos assinado é um comportamento definido pela implementação em C. )

Além disso, certifique-se a contagem de mudança é um tipo não assinado , porque (-n)&31 com um tipo assinado poderia ser um complemento ou sinal / magnitude, e não o mesmo que o modular 2 ^ n você começa com não assinado ou complemento de dois. (Veja comentários sobre post no blog do Regehr). unsigned int faz bem em cada compilador Eu olhei, para cada largura de x. Alguns outros tipos realmente derrotar o idioma de reconhecimento para alguns compiladores, por isso não basta usar o mesmo tipo como x.

Alguns compiladores fornecem intrínsecos para rodar que é muito melhor do que inline-asm se a versão portáteis não gera um bom código no compilador segmentados. Não há intrínsecos cross-plataforma para qualquer compiladores que eu conheço. Estas são algumas das opções x86

documentos Intel que <immintrin.h> fornece _rotl e _rotl64 intrínsecos , e igual para deslocamento para a direita. MSVC requer <intrin.h>, enquanto gcc exigem <x86intrin.h>. Um #ifdef cuida de gcc vs. ICC, mas clang não parece dar-lhes em qualquer lugar, exceto em modo de compatibilidade MSVC com -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . E o asm ele emite para eles suga (máscara extra e um CMOV).

MSVC: _rotr8 e _rotr16 .

gcc e ICC (não tinido): <x86intrin.h> também fornece __rolb / __rorb para 8 bits rodar para a esquerda / para a direita, __rolw / __rorw (16 bits), __rold / __rord (32 bits), __rolq / __rorq (64- pouco, definido apenas para objectivos de 64 bits). Para gira estreitas, as utilizações implementação __builtin_ia32_rolhi ou ...qi, mas a rotação de 32 e 64 bits são definidos usando deslocamento / e (sem protecção contra UB, porque o código em ia32intrin.h só tem de trabalhar no gcc para x86). GNU C parece não ter quaisquer funções __builtin_rotate de plataforma cruzada da maneira que faz para __builtin_popcount (que se expande para o que quer que ideal na plataforma de destino, mesmo se não é uma única instrução). A maioria do tempo que você obter um bom código de idioma-de reconhecimento.

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

Provavelmente, alguns compiladores não-x86 têm intrínsecos, também, mas não vamos expandir esta resposta comunidade wiki de incluir todos eles. (Talvez fazer isso em a resposta existente sobre intrínsecos ).

(A versão antiga de esta resposta suggested específicos do MSVC linha asm (que só funciona para código x86 de 32 bits), ou http: // www. devx.com/tips/Tip/14043 por uma versão C. Os comentários são de responder a isso.)

inline asm derrotas muitas otimizações , especialmente MSVC de estilo porque força entradas para ser armazenado / Reloaded . Um cuidadosamente escrito GNU C inline-asm rotação permitiria a contagem para ser um operando imediato para a contagem Shift-compilação em tempo constante, mas ele ainda não poderia otimizar afastado por completo, se o valor a ser deslocado também é uma constante de tempo de compilação após inlining. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Outras dicas

Uma vez que o C ++, use uma função inline:

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

C ++ 11 variante:

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 têm 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); }

Como abt 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,

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

Se o padrão de bits é 33602 em Integer

1000 0011 0100 0010

e você precisa rolar com 2 shifs direita então: primeiro fazer uma cópia do padrão de bits e mudança, em seguida, deixou-o: Comprimento - RightShift isto é, o comprimento é 16 valor de deslocamento para a direita é 2 16 - 2 = 14

Depois de 14 vezes deixada deslocando você começa.

1000 0000 0000 0000

Agora direita mudar o valor 33602, 2 vezes forem necessárias. Você começa

0010 0000 1101 0000

Agora, dê um OR entre 14 tempo restante valor mudou e 2 vezes o valor direito deslocado.

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

E você obter o seu valor rollover mudou. Lembre-bit operações sábios são mais rápidos e este nem sequer necessário qualquer loop.

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

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

Assumindo que você quer mudar direita por bits L eo x de entrada é um número com pedaços N:

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

A resposta correta é o 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 ++ 20 std::rotl e std::rotr

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

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

Eu vou dar-lhe uma tentativa, quando o apoio chega para GCC, GCC com 9.1.0 g++-9 -std=c++2a ainda não apoiá-lo.

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 Rotating [bitops.rot]

Nas seguintes descrições, deixe N denotam std::numeric_limits<T>::digits.

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

restrições:. T é um número inteiro tipo sem sinal (3.9.1 [basic.fundamental])

seja R s% N.

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

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

restrições: t é um número inteiro tipo não assinado (3.9.1 [basic.fundamental]). Seja R s% N.

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

A std::popcount també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?

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

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

A seguir é uma versão ligeiramente melhorada do do Dídac Pérez resposta , com ambas as direções implementadas, juntamente com uma demonstração de usos destas funções usando unsigned char e valores longos longos não assinados. Várias notas:

As funções são inlined para compilador otimizações

Eu usei um truque cout << +value para laconicamente produzir um unsigned char numericamente que eu encontrei aqui: https://stackoverflow.com/a/ 28414758/1599699

Eu recomendo usar a sintaxe <put the type here> explícita para maior clareza e segurança.

Eu costumava unsigned char para o parâmetro shiftNum por causa do que eu encontrei na seção Detalhes adicionais aqui

O resultado de uma operação de deslocamento é indefinido se aditivo-expressão é negativo ou se aditivo-expressão é maior ou igual ao número de bits na (promovido) shift-expressão .

Aqui está 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.

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

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow