Meilleures pratiques pour les opérations de décalage circulaire (rotation) en C ++

Les opérateurs de décalage gauche et droit (<< et >>) sont déjà disponibles en C ++. Cependant, je ne savais pas comment effectuer des opérations de décalage circulaire ou de rotation.

Comment effectuer des opérations telles que «Rotation à gauche» et «Rotation à droite»?

Rotation à droite deux fois ici

Initial --> 1000 0011 0100 0010

devrait aboutir à:

Final   --> 1010 0000 1101 0000

Un exemple serait utile.

(Note de l'éditeur: de nombreuses façons courantes d'exprimer les rotations en C souffrent d'un comportement indéfini si le nombre de rotations est égal à zéro, ou compilent plus qu'une seule instruction de rotation de la machine. La réponse à cette question doit documenter les meilleures pratiques.)

Voir également une version antérieure de cette réponse sur une autre question de rotation avec quelques détails supplémentaires sur ce que produit asm gcc / clang pour x86.

Le moyen le plus convivial pour le compilateur d'exprimer une rotation en C et C ++ qui évite tout comportement indéfini semble être l'implémentation de John Regehr . Je l'ai adapté pour qu'il tourne selon la largeur du type (en utilisant des types à largeur fixe comme 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 ));
}

Fonctionne pour tout type entier non signé, pas seulement uint32_t, vous pouvez donc créer des versions pour d'autres tailles.

Voir aussi une version de modèle C ++ 11 avec de nombreuses vérifications de sécurité (y compris un fait static_assertque la largeur du type est une puissance de 2) , ce qui n'est pas le cas sur certains DSP 24 bits ou mainframes 36 bits, par exemple.

Je recommanderais uniquement d'utiliser le modèle comme back-end pour les wrappers avec des noms qui incluent explicitement la largeur de rotation. Les règles de promotion d'entiers signifient que rotl_template(u16 & 0x11UL, 7)cela ferait une rotation 32 ou 64 bits, et non 16 (selon la largeur de unsigned long). Even uint16_t & uint16_test promu signed intpar les règles de promotion d'entiers de C ++, sauf sur les plates-formes où intn'est pas plus large que uint16_t.

Sur x86 , cette version s'aligne sur un seulrol r32, cl (ou rol r32, imm8) avec des compilateurs qui le grokent, car le compilateur sait que les instructions de rotation et de décalage x86 masquent le nombre de décalage de la même manière que la source C.

Prise en charge du compilateur pour cet idiome évitant UB sur x86, pour uint32_t xet unsigned int npour les décalages à nombre variable:

• clang: reconnu pour les rotations à nombre variable depuis clang3.5, plusieurs décalages + ou insns avant cela.
• gcc: reconnu pour la rotation du nombre de variables depuis gcc4.9 , plusieurs décalages + ou insns avant cela. gcc5 et les versions ultérieures optimisent également la branche et le masque dans la version wikipedia, en utilisant simplement une instruction rorou rolpour le nombre de variables.
• icc: pris en charge pour les rotations à nombre variable depuis ICC13 ou antérieur . Le nombre constant tourne l'utilisationshld edi,edi,7 qui est plus lente et prend plus d'octets que rol edi,7sur certains processeurs (en particulier AMD, mais aussi certains Intel), lorsque BMI2 n'est pas disponible pour rorx eax,edi,25enregistrer un MOV.
• MSVC: x86-64 CL19: reconnu uniquement pour les rotations à comptage constant. (L'idiome wikipedia est reconnu, mais la branche et AND ne sont pas optimisés). Utilisez les _rotl/ _rotrintrinsèques de<intrin.h> de x86 (y compris x86-64).

gcc pour ARM utilise un and r1, r1, #31pour tourne-count variable, mais fait encore la rotation réelle avec une seule instruction : ror r0, r0, r1. Donc gcc ne se rend pas compte que le nombre de tours est intrinsèquement modulaire. Comme le dit ARM, "ROR avec longueur de décalage n, plus de 32 est identique à ROR avec longueur de décalage n-32" . Je pense que gcc est confus ici parce que les décalages gauche / droite sur ARM saturent le compte, donc un décalage de 32 ou plus effacera le registre. (Contrairement à x86, où les décalages masquent le nombre de la même manière que les rotations). Il décide probablement qu'il a besoin d'une instruction AND avant de reconnaître l'idiome de rotation, en raison de la façon dont les décalages non circulaires fonctionnent sur cette cible.

Les compilateurs x86 actuels utilisent toujours une instruction supplémentaire pour masquer un nombre de variables pour les rotations 8 et 16 bits, probablement pour la même raison qu'ils n'évitent pas le AND sur ARM. Il s'agit d'une optimisation manquée, car les performances ne dépendent pas du nombre de rotations sur n'importe quel processeur x86-64. (Le masquage des décomptes a été introduit avec 286 pour des raisons de performances car il gérait les changements de manière itérative, pas avec une latence constante comme les processeurs modernes.)

BTW, préférez la rotation à droite pour les rotations à nombre variable, pour éviter de forcer le compilateur 32-nà implémenter une rotation à gauche sur des architectures comme ARM et MIPS qui ne fournissent qu'une rotation à droite. (Cela s'optimise avec des comptages constants de temps de compilation.)

Fait amusant: ARM n'a pas vraiment d'instructions de changement / rotation dédiées, c'est juste MOV avec le Opérande source en passant par le canon-levier de vitesses en mode ROR : mov r0, r0, ror r1. Ainsi, une rotation peut se plier en un opérande source de registre pour une instruction EOR ou quelque chose.

Assurez-vous d'utiliser des types non signés pour n et la valeur de retour, sinon ce ne sera pas une rotation . (gcc pour les cibles x86 effectue des décalages arithmétiques vers la droite, se déplaçant en copies du bit de signe plutôt que des zéros, ce qui entraîne un problème lorsque vous ORdéplacez les deux valeurs ensemble. Les décalages à droite des entiers signés négatifs sont un comportement défini par l'implémentation en C.)

Assurez-vous également que le nombre de décalages est un type non signé , car (-n)&31avec un type signé peut être le complément à un ou le signe / la magnitude, et pas le même que le 2 ^ n modulaire que vous obtenez avec un complément non signé ou à deux. (Voir les commentaires sur le billet de blog de Regehr). unsigned intfonctionne bien sur tous les compilateurs que j'ai consultés, pour chaque largeur dex . Certains autres types détruisent la reconnaissance d'idiomes pour certains compilateurs, alors n'utilisez pas simplement le même type que x.

Certains compilateurs fournissent des éléments intrinsèques pour les rotations , ce qui est bien meilleur que inline-asm si la version portable ne génère pas un bon code sur le compilateur que vous ciblez. Il n'y a pas d'intrinsèques multiplateformes pour les compilateurs que je connaisse. Voici quelques-unes des options x86:

• Documents Intel qui <immintrin.h>fournissent _rotlet _rotl64intrinsèques , et même pour le décalage à droite. MSVC nécessite <intrin.h>, tandis que gcc nécessite <x86intrin.h>. An #ifdefs'occupe de gcc contre icc, mais clang ne semble pas les fournir nulle part, sauf en mode de compatibilité MSVC avec-fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . Et l'asm qu'il émet pour eux est nul (masquage supplémentaire et CMOV).
• MSVC: _rotr8et_rotr16 .
• gcc et icc (not clang): <x86intrin.h>fournit également __rolb/ __rorbpour une rotation 8 bits gauche / droite, __rolw/ __rorw(16 bits), __rold/ __rord(32 bits), __rolq/ __rorq(64 bits, défini uniquement pour les cibles 64 bits). Pour les rotations étroites, l'implémentation utilise __builtin_ia32_rolhiou ...qi, mais les rotations 32 et 64 bits sont définies à l'aide de shift / or (sans protection contre UB, car le code ia32intrin.hne doit fonctionner que sur gcc pour x86). GNU C semble ne pas avoir de __builtin_rotatefonctions multiplateformes comme il le fait __builtin_popcount(qui s'étend à ce qui est optimal sur la plate-forme cible, même si ce n'est pas une seule instruction). La plupart du temps, vous obtenez un bon code grâce à la reconnaissance d'idiomes.

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

Vraisemblablement, certains compilateurs non-x86 ont aussi des éléments intrinsèques, mais n'élargissons pas cette réponse de communauté-wiki pour les inclure tous. (Peut-être faites-le dans la réponse existante sur les intrinsèques ).

(L'ancienne version de cette réponse suggérait un asm en ligne spécifique à MSVC (qui ne fonctionne que pour le code x86 32 bits), ou http://www.devx.com/tips/Tip/14043 pour une version C. Les commentaires répondent à cela .)

Inline asm défait de nombreuses optimisations , en particulier de style MSVC car il force les entrées à être stockées / rechargées . Une rotation en ligne-asm GNU C soigneusement écrite permettrait au compte d'être un opérande immédiat pour les décomptes de décalage à constante de temps de compilation, mais il ne pourrait toujours pas s'optimiser entièrement si la valeur à déplacer est également une constante de temps de compilation après l'inlining. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Puisqu'il s'agit de C ++, utilisez une fonction en ligne:

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

La plupart des compilateurs ont des éléments intrinsèques pour cela. Visual Studio par exemple _rotr8, _rotr16

Définitivement:

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

C ++ 20 std::rotletstd::rotr

C'est arrivé! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html et doit l'ajouter à l'en- <bit>tête.

cppreference dit que l'utilisation sera comme:

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

donnant la sortie:

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

Je vais essayer lorsque le support arrivera à GCC, GCC 9.1.0 avec g++-9 -std=c++2a ne le supporte toujours pas.

La proposition dit:

Entête:

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;

et:

25.5.5 Rotation de [bitops.rot]

Dans les descriptions suivantes, Soit n std::numeric_limits<T>::digits.

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

Contraintes: T est un type entier non signé (3.9.1 [basic.fundamental]).

Soit r s% N.

Renvoie: Si r vaut 0, x; si r est positif (x << r) | (x >> (N - r)),; si r est négatif, rotr(x, -r).

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

Contraintes: T est un type entier non signé (3.9.1 [basic.fundamental]). Soit r s% N.

Renvoie: Si r vaut 0, x; si r est positif (x >> r) | (x << (N - r)),; si r est négatif, rotl(x, -r).

Un std::popcounta également été ajouté pour compter le nombre de 1 bits: Comment compter le nombre de bits définis dans un entier de 32 bits?

Comment quelque chose comme ça, en utilisant l'ensemble de bits standard ...

#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 est une valeur de 8 bits, vous pouvez utiliser ceci:

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

Dans les détails, vous pouvez appliquer la logique suivante.

Si le motif de bits est 33602 en nombre entier

1000 0011 0100 0010

et vous devez Roll over avec 2 décalages vers la droite, puis: faites d'abord une copie du motif de bits, puis décalez-le à gauche: Longueur - Décalage à droite c.-à-d. que la longueur est de 16 La valeur de décalage à droite est de 2 16 - 2 = 14

Après 14 passages à gauche, vous obtenez.

1000 0000 0000 0000

Maintenant, décalez à droite la valeur 33602, 2 fois au besoin. Vous obtenez

0010 0000 1101 0000

Maintenant, prenez un OU entre 14 fois la valeur décalée à gauche et 2 fois la valeur décalée à droite.

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

Et vous obtenez votre valeur de roulement décalée. Rappelez-vous que les opérations par bit sont plus rapides et cela ne nécessite même aucune boucle.

En supposant que vous vouliez décaler vers la droite de Lbits, et que l'entrée xsoit un nombre avec des Nbits:

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

La bonne réponse est la suivante:

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

Code source x numéro 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;  
}

une autre suggestion

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

Vous trouverez ci-dessous une version légèrement améliorée de la réponse de Dídac Pérez , avec les deux directions implémentées, ainsi qu'une démonstration de l'utilisation de ces fonctions utilisant des caractères non signés et des valeurs longues longues non signées. Plusieurs remarques:

1. Les fonctions sont intégrées pour les optimisations du compilateur
2. J'ai utilisé une cout << +valueastuce pour générer de manière laconique un caractère non signé que j'ai trouvé ici: https://stackoverflow.com/a/28414758/1599699
3. Je recommande d'utiliser l'explicite <put the type here> syntaxe pour plus de clarté et de sécurité.
4. J'ai utilisé un caractère non signé pour le paramètre shiftNum à cause de ce que j'ai trouvé dans la section Détails supplémentaires ici :

Le résultat d'une opération de décalage n'est pas défini si l' expression additive est négative ou si l' expression additive est supérieure ou égale au nombre de bits dans l' expression de décalage (promue) .

Voici le code que j'utilise:

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

Surcharger une fonction:

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