Best Practices für Circular Shift (Rotation) -Operationen in C ++

Links- und Rechtsverschiebungsoperatoren (<< und >>) sind in C ++ bereits verfügbar. Ich konnte jedoch nicht herausfinden, wie ich Kreisverschiebungs- oder Rotationsvorgänge ausführen konnte.

Wie können Operationen wie "Nach links drehen" und "Nach rechts drehen" ausgeführt werden?

Hier zweimal nach rechts drehen

Initial --> 1000 0011 0100 0010

sollte führen zu:

Final   --> 1010 0000 1101 0000

Ein Beispiel wäre hilfreich.

(Anmerkung des Herausgebers: Viele gängige Methoden zum Ausdrücken von Rotationen in C weisen ein undefiniertes Verhalten auf, wenn die Rotationszahl Null ist oder zu mehr als nur einer einzelnen Rotationsmaschinenanweisung kompiliert wird. Die Antwort dieser Frage sollte Best Practices dokumentieren.)

Siehe auch eine frühere Version dieser Antwort zu einer anderen Rotationsfrage mit einigen weiteren Details darüber, was asm gcc / clang für x86 produziert.

Die compilerfreundlichste Art, eine Rotation in C und C ++ auszudrücken, die undefiniertes Verhalten vermeidet, scheint die Implementierung von John Regehr zu sein . Ich habe es so angepasst, dass es sich um die Breite des Typs dreht (unter Verwendung von Typen mit fester Breite wie 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 ));
}

Funktioniert für jeden vorzeichenlosen Integer-Typ, nicht nur uint32_t, sodass Sie Versionen für andere Größen erstellen können.

Siehe auch eine C ++ 11-Vorlagenversion mit vielen Sicherheitsüberprüfungen (einschließlich der Tatsache, static_assertdass die Typbreite eine Potenz von 2 ist) , was beispielsweise bei einigen 24-Bit-DSPs oder 36-Bit-Mainframes nicht der Fall ist.

Ich würde empfehlen, die Vorlage nur als Back-End für Wrapper mit Namen zu verwenden, die die Drehbreite explizit enthalten. Integer-Promotion-Regeln bedeuten, dass rotl_template(u16 & 0x11UL, 7)eine 32- oder 64-Bit-Drehung durchgeführt wird, nicht 16 (abhängig von der Breite von unsigned long). Even uint16_t & uint16_twird signed intdurch die Ganzzahl-Heraufstufungsregeln von C ++ hochgestuft, außer auf Plattformen, auf denen intnicht breiter als ist uint16_t.

Unter x86 wird diese Version in eine einzelnerol r32, cl (oder rol r32, imm8) Version mit Compilern eingefügt, die sie bearbeiten, da der Compiler weiß, dass x86-Anweisungen zum Drehen und Verschieben die Anzahl der Verschiebungen genauso maskieren wie die C-Quelle.

Compiler-Unterstützung für diese UB-vermeidende Redewendung auf x86 für uint32_t xund unsigned int nfür Verschiebungen mit variabler Anzahl:

• clang: erkannt für variable Anzahl dreht sich seit clang3.5, mehrere Verschiebungen + oder insns davor.
• gcc: erkannt für variable Anzahl dreht sich seit gcc4.9 , mehrere Verschiebungen + oder insns davor. gcc5 und später optimieren Sie den Zweig und die Maske auch in der Wikipedia-Version, indem Sie nur eine roroder- rolAnweisung für die Anzahl der Variablen verwenden.
• icc: unterstützt für Rotationen mit variabler Anzahl seit ICC13 oder früher . Die konstante Anzahl dreht die Verwendung, shld edi,edi,7was langsamer ist und mehr Bytes benötigt als rol edi,7bei einigen CPUs (insbesondere AMD, aber auch bei einigen Intel), wenn BMI2 nicht rorx eax,edi,25zum Speichern eines MOV verfügbar ist .
• MSVC: x86-64 CL19: Nur für Rotationen mit konstanter Anzahl erkannt. (Die Wikipedia-Sprache wird erkannt, aber der Zweig und AND werden nicht optimiert). Verwenden Sie die _rotl/ _rotrintrinsics von <intrin.h>x86 (einschließlich x86-64).

gcc for ARM verwendet eine and r1, r1, #31Rotation für variable Anzahl, führt jedoch die eigentliche Rotation mit einer einzigen Anweisung aus : ror r0, r0, r1. Gcc erkennt also nicht, dass Rotationszählungen von Natur aus modular sind. In den ARM-Dokumenten heißt es: "ROR mit Schichtlänge n, mehr als 32 sind gleich ROR mit Schichtlänge n-32" . Ich denke, gcc wird hier verwirrt, weil Links- / Rechtsverschiebungen auf ARM die Anzahl sättigen, sodass eine Verschiebung um 32 oder mehr das Register löscht. (Im Gegensatz zu x86, bei dem Verschiebungen die Anzahl genauso maskieren wie beim Drehen). Es entscheidet wahrscheinlich, dass es eine UND-Anweisung benötigt, bevor es die Rotationssprache erkennt, da nicht kreisförmige Verschiebungen auf dieses Ziel wirken.

Aktuelle x86-Compiler verwenden immer noch einen zusätzlichen Befehl, um eine Variablenanzahl für 8- und 16-Bit-Rotationen zu maskieren, wahrscheinlich aus dem gleichen Grund, aus dem sie das UND auf ARM nicht vermeiden. Dies ist eine verpasste Optimierung, da die Leistung nicht von der Anzahl der Rotationen auf einer x86-64-CPU abhängt. (Die Maskierung von Zählungen wurde aus Leistungsgründen mit 286 eingeführt, da Verschiebungen iterativ und nicht wie bei modernen CPUs mit konstanter Latenz behandelt wurden.)

Übrigens, bevorzugen Sie Rotation nach rechts für Rotationen mit variabler Anzahl, um zu vermeiden, dass der Compiler 32-nbei Architekturen wie ARM und MIPS, die nur eine Rotation nach rechts bereitstellen, eine Rotation nach links implementiert. (Dies optimiert die Anzahl der Kompilierungszeitkonstanten.)

Unterhaltsame Tatsache: ARM verfügt nicht über spezielle Shift / Rotate-Anweisungen, sondern nur über MOV, wobei der Quelloperand im ROR-Modus durch den Barrel-Shifter läuft : mov r0, r0, ror r1. So kann eine Drehung für einen EOR-Befehl oder etwas in einen Registerquellenoperanden gefaltet werden.

Stellen Sie sicher, dass Sie vorzeichenlose Typen für nund den Rückgabewert verwenden, da dies sonst keine Drehung ist . (gcc für x86-Ziele führt arithmetische Rechtsverschiebungen durch, wobei Kopien des Vorzeichenbits anstelle von Nullen ORverschoben werden , was zu einem Problem führt, wenn Sie die beiden Werte zusammen verschieben. Rechtsverschiebungen von Ganzzahlen mit negativem Vorzeichen sind ein implementierungsdefiniertes Verhalten in C.)

Auch stellen Sie sicher , die Verschiebungszahl ein Typ ohne Vorzeichen ist , weil (-n)&31mit einem signierten Typ könnte Einerkomplement oder Zeichen / Größe, und nicht das gleiche wie die modularen 2 ^ n Sie mit unsigned oder Zweier-Komplement zu bekommen sein. (Siehe Kommentare zu Regehrs Blogbeitrag). unsigned intfunktioniert gut auf jedem Compiler, den ich mir angesehen habe, für jede Breite von x. Einige andere Typen besiegen tatsächlich die Redewendungserkennung für einige Compiler. Verwenden Sie also nicht einfach den gleichen Typ wie x.

Einige Compiler bieten Intrinsics für Rotationen , was weitaus besser ist als Inline-Asm, wenn die tragbare Version keinen guten Code auf dem Compiler generiert, auf den Sie abzielen. Es gibt keine plattformübergreifenden Eigenschaften für Compiler, die mir bekannt sind. Dies sind einige der x86-Optionen:

• Intel-Dokumente, <immintrin.h>die _rotlund _rotl64intrinsics bereitstellen , und dasselbe für die Rechtsverschiebung. MSVC erfordert <intrin.h>, während gcc erfordern <x86intrin.h>. A #ifdefkümmert sich um gcc vs. icc, aber clang scheint sie nirgendwo zu bieten, außer im MSVC-Kompatibilitätsmodus mit-fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . Und der Asm, den es für sie ausstrahlt, ist zum Kotzen (zusätzliche Maskierung und ein CMOV).
• MSVC: _rotr8und_rotr16 .
• gcc und icc (nicht klirrend): <x86intrin.h>Bietet auch __rolb/ __rorbfür 8-Bit-Drehung nach links / rechts, __rolw/ __rorw(16-Bit), __rold/ __rord(32-Bit), __rolq/ __rorq(64-Bit, nur für 64-Bit-Ziele definiert). Für enge Drehungen verwendet die Implementierung __builtin_ia32_rolhioder ...qi, aber die 32- und 64-Bit-Drehungen werden mit shift / oder definiert (ohne Schutz gegen UB, da der Code in ia32intrin.hnur für x86 auf gcc funktionieren muss). GNU C scheint keine plattformübergreifenden __builtin_rotateFunktionen zu haben, wie es funktioniert __builtin_popcount(was sich auf das ausdehnt, was auf der Zielplattform optimal ist, auch wenn es sich nicht um eine einzelne Anweisung handelt). Meistens erhalten Sie guten Code durch die Erkennung von Redewendungen.

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

Vermutlich haben auch einige Nicht-x86-Compiler Eigenschaften, aber erweitern wir diese Community-Wiki-Antwort nicht, um sie alle einzuschließen. (Vielleicht tun Sie das in der vorhandenen Antwort über Intrinsics ).

(Die alte Version dieser Antwort schlug MSVC-spezifischen Inline-Asm vor (der nur für 32-Bit-x86-Code funktioniert) oder http://www.devx.com/tips/Tip/14043 für eine C-Version. Die Kommentare antworten darauf .)

Inline-ASM besiegt viele Optimierungen , insbesondere im MSVC-Stil, da Eingaben gespeichert / neu geladen werden müssen . Eine sorgfältig geschriebene GNU C-Inline-Asm-Drehung würde es dem Zähler ermöglichen, ein sofortiger Operand für Verschiebungszählungen zur Kompilierungszeitkonstante zu sein, aber es könnte immer noch nicht vollständig optimiert werden, wenn der zu verschiebende Wert auch eine Kompilierungszeitkonstante ist nach dem Inlining. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Verwenden Sie eine Inline-Funktion, da es sich um C ++ handelt:

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

Die meisten Compiler haben dafür Eigenheiten. Visual Studio zum Beispiel _rotr8, _rotr16

Endgültig:

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

C ++ 20 std::rotlundstd::rotr

Es ist angekommen! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html und sollte es dem <bit>Header hinzufügen .

cppreference sagt, dass die Verwendung wie folgt sein wird:

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

Ausgabe geben:

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

Ich werde es versuchen, wenn der Support bei GCC eintrifft. GCC 9.1.0 g++-9 -std=c++2aunterstützt ihn immer noch nicht.

Der Vorschlag lautet:

Header:

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;

und:

25.5.5 Drehen von [bitops.rot]

In den folgenden Beschreibungen sei N bezeichnet std::numeric_limits<T>::digits.

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

Einschränkungen: T ist ein vorzeichenloser Integer-Typ (3.9.1 [basic.fundamental]).

Sei r s% N.

Rückgabe: Wenn r 0 ist, x; wenn r positiv ist (x << r) | (x >> (N - r)); wenn r negativ ist , rotr(x, -r).

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

Einschränkungen: T ist ein vorzeichenloser Integer-Typ (3.9.1 [basic.fundamental]). Sei r s% N.

Rückgabe: Wenn r 0 ist, x; wenn r positiv ist (x >> r) | (x << (N - r)); wenn r negativ ist , rotl(x, -r).

A std::popcountwurde ebenfalls hinzugefügt, um die Anzahl der 1 Bits zu zählen : Wie wird die Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl gezählt?

Wie wäre es mit so etwas mit dem Standard-Bitset ...

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

Wenn x ein 8-Bit-Wert ist, können Sie Folgendes verwenden:

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

Im Detail können Sie die folgende Logik anwenden.

Wenn das Bitmuster 33602 in Integer ist

1000 0011 0100 0010

und Sie müssen dann mit 2 rechten Shifs rollen: Erstellen Sie zuerst eine Kopie des Bitmusters und verschieben Sie es dann nach links: Länge - Rechtsverschiebung, dh Länge ist 16, Rechtsverschiebungswert ist 2 16 - 2 = 14

Nach 14 mal Linksschaltung bekommst du.

1000 0000 0000 0000

Verschieben Sie nun den Wert 33602 nach Bedarf zweimal nach rechts. Du erhältst

0010 0000 1101 0000

Nehmen Sie nun ein ODER zwischen dem 14-mal nach links verschobenen Wert und dem 2-mal nach rechts verschobenen Wert.

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

Und Sie erhalten Ihren verschobenen Rollover-Wert. Denken Sie daran, dass bitweise Operationen schneller sind und dies nicht einmal eine Schleife erfordert.

Angenommen, Sie möchten um LBits nach rechts verschieben , und die Eingabe xist eine Zahl mit NBits:

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

Die richtige Antwort lautet wie folgt:

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

Quellcode x Bitnummer

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

ein weiterer Vorschlag

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

Im Folgenden finden Sie eine leicht verbesserte Version der Antwort von Dídac Pérez , in der beide Richtungen implementiert sind, sowie eine Demo der Verwendung dieser Funktionen unter Verwendung von vorzeichenlosen Zeichen und vorzeichenlosen langen langen Werten. Mehrere Anmerkungen:

1. Die Funktionen sind für Compiler-Optimierungen vorgesehen
2. Ich habe einen cout << +valueTrick verwendet, um ein vorzeichenloses Zeichen, das ich hier gefunden habe, knapp numerisch auszugeben: https://stackoverflow.com/a/28414758/1599699
3. Ich empfehle die Verwendung der expliziten <put the type here>Syntax für Klarheit und Sicherheit.
4. Ich habe vorzeichenloses Zeichen für den Parameter shiftNum verwendet, weil ich hier im Abschnitt "Zusätzliche Details" Folgendes gefunden habe :

Das Ergebnis einer Verschiebungsoperation ist undefiniert, wenn der additive Ausdruck negativ ist oder wenn der additive Ausdruck größer oder gleich der Anzahl der Bits im (heraufgestuften) Verschiebungsausdruck ist .

Hier ist der Code, den ich verwende:

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

Funktion überladen:

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