Bewährte Verfahren für die zirkulare Verschiebung (Drehen) Operationen in C ++

https://stackoverflow.com/questions/776508

13-09-2019
|

Frage

Linke und rechte Shift-Operatoren (<< und >>) sind bereits in C ++. Allerdings konnte ich nicht herausfinden, wie ich zirkulare Verschiebung oder drehen Operationen durchführen können.

Wie können Operationen wie „Nach links drehen“ und „Nach rechts drehen“ durchgeführt werden?

Rotierende rechts zweimal hier

Initial --> 1000 0011 0100 0010

sollten führen:

Final   --> 1010 0000 1101 0000

Ein Beispiel wäre hilfreich.

(Anmerkung der Redaktion: Viele gängige Möglichkeiten, dreht sich in C exprimierenden leiden unter undefinierten Verhalten, wenn die drehen Zahl Null ist, oder kompilieren, um mehr als nur eine einzige drehen Maschinenbefehl diese Antwort auf die Frage sollte Best Practices dokumentieren.).

Lösung

Siehe auch eine frühere Version von diese Antwort auf eine andere Frage drehen mit etwas mehr Details über das, was asm gcc / Klappern erzeugen für x86.

Die meisten Compiler-freundliche Art und Weise ein Drehen in C und C ++, die jede nicht definiertes Verhalten vermeidet auszudrücken scheint zu sein, John Regehr Implementierung . Ich habe angepasst es durch die Breite des Typs zu drehen (mit fester Breite Typen wie uint32_t verwendet wird).

#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 unsigned Integer-Typen, nicht nur uint32_t, so dass Sie Versionen für andere Größen machen könnten.

finden Sie unter auch eine C ++ 11 Template Version mit vielen Sicherheitskontrollen ( ein static_assert einschließlich, dass die TYPOLOGIE eine Potenz von 2 ist) , die auf einigen 24-Bit-DSPs oder 36-Bit-Großrechnern, zum Beispiel nicht der Fall ist.

würde ich empfehlen, nur die Vorlage als Back-End verwenden für Wrapper mit Namen, die den Dreh Breite explizit enthalten. Integer-Förderung Regeln bedeuten, dass rotl_template(u16 & 0x11UL, 7) ein 32 oder tun würde, 64-Bit drehen, nicht 16 (abhängig von der Breite der unsigned long). Auch uint16_t & uint16_t wird gefördert durch C ++ 's integer-Förderung Regeln signed int, außer auf Plattformen, auf denen int nicht breiter als uint16_t sind.

Auf x86 , diese Version inlines zu einem einzigen rol r32, cl (oder rol r32, imm8) mit Compiler, die es grok, weil der Compiler, dass x86 drehen und Anweisungen verschieben funktioniert die C-Quelle auf die gleiche Weise die Maske Schalt zählen.

Compiler Unterstützung für dieses UB-Vermeidung Idiom auf x86, für uint32_t x und unsigned int n für variable Zählung Verschiebungen:

Klirren. Anerkannt für variabele Zahl dreht seit clang3.5, mehrschichtig + oder insns vor, dass
gcc: anerkannt für variable Zählung dreht seit gcc4.9 , mehrere Schichten + oder insns davor. gcc5 und später den Zweig und Maske in der Wikipedia Version optimieren weg auch mit nur einem ror oder rol Befehl für Variable zählt.
icc: für variabel unterstützt zählen dreht seit ICC13 oder früher . Constant-count Verwendung shld edi,edi,7 dreht, die langsamer ist und mehr Bytes als rol edi,7 nimmt bei einigen CPUs (vor allem AMD, aber auch einige Intel), wenn BMI2 ist nicht verfügbar für rorx eax,edi,25 eine MOV zu speichern.
MSVC: x86-64 CL19: Nur anerkannt für Konstantzahl dreht. (Die wikipedia Idiom wird erkannt, aber der Zweig und und ist nicht optimiert entfernt). Verwenden Sie die _rotl / _rotr Spezifika von <intrin.h> auf x86 (einschließlich x86-64).

gcc für ARM verwendet eine and r1, r1, #31 für variabele Zahl dreht, aber tut es immer noch die tatsächlichen mit einem einzigen Befehl drehen : ror r0, r0, r1. So gcc nicht erkennen, dass drehen Zählungen sind von Natur aus modular. Da der ARM-docs sagen, "ROR mit Verschiebungslänge, n, mehr als 32 ist die gleiche wie ROR mit Verschiebungslänge n-32 ". Ich denke, gcc wird hier verwirrt, weil links / rechts verschiebt sich auf ARM die Zählung sättigen, so eine Verschiebung um 32 oder mehr wird das Register löschen. (Im Gegensatz zu x86, wo Verschiebungen der Zählung der gleichen wie dreht Maske). Wahrscheinlich entscheidet es braucht eine UND-Anweisung, bevor Sie das Drehen Idiom zu erkennen, weil, wie unrunden Schichten arbeiten auf dieses Ziel.

Aktuelle x86-Compiler noch einen zusätzlichen Befehl verwenden, um eine variable Anzahl für 8 und 16-Bit dreht sich zu maskieren, wahrscheinlich aus dem gleichen Grund sie nicht vermeiden das UND auf ARM. Dies ist eine verpasste Optimierung, da die Leistung nicht auf dem Drehen Zahl auf jedem x86-64 CPU ab. (Maskierung von Zählungen mit 286 aus Leistungsgründen eingeführt wurde, weil es Verschiebungen iterativ behandelt, nicht mit konstanter Latenz wie moderne CPUs.)

BTW, bevorzugen dreht rechts für variabele Zahl dreht, um zu verhindern, den Compiler auszukommen 32-n links zu implementieren drehen auf Architekturen wie ARM und MIPS, die nur ein Dreh-Recht geben. (Dies optimiert mit c entferntompile Zeitkonstante zählt.)

Fun Tatsache: ARM nicht wirklich gewidmet haben Schiebe- / drehen Anweisungen, es ist nur MOV mit der Quelloperand gehen durch den Trommel- Verschiebe in ROR-Modus : mov r0, r0, ror r1. So ein drehen kann für einen EOR-Befehl oder etwas einen Register-Quelloperand faltet sich in.

Stellen Sie sicher, unsigned Typen für n und den Rückgabewert verwenden, sonst wird es kein drehen sein. (Gcc für x86 Ziele tut arithmetische Rechtsverschiebungen, Verschiebung in Kopien des Vorzeichenbitextrahierer eher als Nullen, zu einem Problem führt, wenn Sie OR die beide zusammen Werten verschoben. Rechtsverschiebungen von negativen Integer mit Vorzeichen ist die Implementierung definierte Verhalten in C. )

Auch sicherstellen, dass die Verschiebungszahl ist ein unsigned Typ , weil (-n)&31 mit einer signierten Art Ergänzung oder Zeichen / Größe der sein könnte, und nicht das gleiche wie die modularen 2 ^ n Sie erhalten mit unsigned oder zweier-Komplement. (Siehe Kommentare auf Regehr Blog-Post). unsigned int tut gut auf jedem Compiler, den ich angeschaut habe, für jede Breite von x. Einige andere Arten tatsächlich das Idiom-Anerkennung für einige Compiler besiegen, so verwenden Sie nicht nur den gleichen Typ wie x.

Einige Compiler bieten intrinsics für dreht , die als Inline-asm weit besser ist, wenn die portable Version nicht gut Code generiert auf der Compiler Sie Targeting. Es gibt keine Cross-Plattform-Spezifika für alle Compiler, die ich kenne. Dies sind einige der x86-Optionen:

Intel-Dokumente, die a href = " <immintrin.h> bietet _rotl und _rotl64 intrinsics und gleiche gilt für Rechtsverschiebung. MSVC erfordert <intrin.h>, während gcc <x86intrin.h> erfordern. Ein #ifdef kümmert sich um gcc vs. icc, aber Klappern scheint sie nicht überall zur Verfügung zu stellen, außer in MSVC Kompatibilitätsmodus mit -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . Und die asm es für sie aussendet saugt (extra Maskierung und eine CMOV).
MSVC: _rotr8 und _rotr16 .
gcc und ICC (nicht clang): <x86intrin.h> auch __rolb / __rorb für 8-Bit drehen nach links / rechts, __rolw / __rorw (16-Bit), __rold / __rord (32-Bit), __rolq / __rorq (64- liefert bit, nur für 64-Bit-Ziele definiert). Für schmale dreht, verwendet die Implementierung __builtin_ia32_rolhi oder ...qi, aber die 32 und 64-Bit dreht verwenden Verschiebung definiert / oder (ohne Schutz gegen UB, da der Code in ia32intrin.h nur auf gcc für x86 arbeiten muss). GNU C erscheint nicht plattformübergreifende __builtin_rotate Funktionen haben, wie es für __builtin_popcount tut (die auf der Zielplattform, was auch immer die optimalen erweitert, auch wenn es nicht eine einzige Anweisung). Die meiste Zeit erhalten Sie guten Code von Idiom-Anerkennung.

// 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 einige Nicht-x86-Compiler haben intrinsics auch, aber lassen Sie uns diese Community-Wiki Antwort nicht erweitern, sie alle umfassen. (Vielleicht tun, dass in die bestehende Antwort über intrinsics ).

(Die alte Version dieser Antwort suggested MSVC-spezifischen Inline-asm (die für 32-Bit-x86-Code funktioniert nur) oder http: // www. devx.com/tips/Tip/14043 für eine C-Version. Die Kommentare werden, dass die Beantwortung.)

Inline-asm besiegt viele Optimierungen besonders MSVC-Stil, weil es Eingaben zwingt gespeichert / neu geladen werden. Ein sorgfältig geschriebenes GNU C Inline-asm drehen würde die Zählung erlaubt ein unmittelbarer Operand für Compile-Zeit-Konstante Verschiebung zählt zu sein, aber es könnte noch nicht optimiert weg vollständig, wenn der Wert verschoben werden soll auch eine Kompilierung-Konstante nach inlining. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Andere Tipps

Da es C ++ ist, verwenden Sie eine Inline-Funktion:

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 intrinsics dafür. 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);
}

Wie abt so etwas wie diese, 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,

Im Detail können Sie die folgende Logik anwenden.

Wenn Bitmuster 33602 in Integer

1000 0011 0100 0010

und Sie müssen dann mit 2 rechts shifs rollen: zunächst eine Kopie Bitmuster machen und dann nach links verschieben sie: Länge - RightShift d.h. Länge 16 Rechtsverschiebungswert ist 2 16-2 = 14

Nach 14 mal Verschiebung nach links Sie erhalten.

1000 0000 0000 0000

Jetzt rechts verschieben, um den Wert 33602, 2 mal je nach Bedarf. Sie erhalten

0010 0000 1101 0000

Jetzt ein ODER zwischen 14 Zeit in Anspruch nimmt links verschoben Wert und 2 mal rechts Wert verschoben.

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

Und Sie verschoben Roll Wert. Denken Sie daran, bitweise Operationen sind schneller und dies erforderlich ist nicht einmal eine Schleife.

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

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

Unter der Annahme, dass Sie sich von L Bits verschoben werden sollen, und der Eingang x eine Zahl mit N Bits:

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

Die richtige Antwort ist folgende:

#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 und std::rotr

Es ist da! http: //www.open-std. org / JTC1 / SC22 / WG21 / docs / paper / 2019 / p0553r4.html und soll es den <bit> Header hinzuzufügen.

cppreference sagt, dass die Nutzung aussehen 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';
}

geben Ausgang:

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

ich es werde einen Versuch geben, wenn Unterstützung für GCC kommt, GCC 9.1.0 mit g++-9 -std=c++2a noch nicht unterstützt wird.

Der Vorschlag sagt:

Rubrik:

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

In den folgenden Beschreibungen lassen N std::numeric_limits<T>::digits bezeichnen.
template<class T>
  [[nodiscard]] constexpr T rotl(T x, int s) noexcept;
Constraints:. T ist eine ganze Zahl ohne Vorzeichen-Typ (3.9.1 [basic.fundamental])

Sei R s% N.

Rückkehr: Wenn r 0, 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;
Constraints: T ist eine ganze Zahl ohne Vorzeichen-Typ (3.9.1 [basic.fundamental]).   Sei R s% N.

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

Ein std::popcount wurde auch hinzugefügt, um die Anzahl von 1-Bits zu zählen: Wie die Anzahl der gesetzten Bits in einem 32-Bit-integer zählen?

Source Code x-Bit-Zahl

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 von Dídac Pérez Antwort , mit beiden Richtungen implementiert, zusammen mit einem Demo dieser unsigned char und unsigned long long-Werte mit Nutzungen Funktionen. Mehrere Hinweise:

Die Funktionen sind inlined für Compiler-Optimierungen
Ich benutzte einen Trick cout << +value für lapidar ein unsigned char Ausgeben numerisch, dass ich hier gefunden: https://stackoverflow.com/a/ 28414758/1599699
Ich empfehle die explizite <put the type here> Syntax für Klarheit und Sicherheit verwendet wird.
Ich habe unsigned char für den shiftNum Parameter aufgrund dessen, was ich in den weiteren Abschnitt Details gefunden hier :

Das Ergebnis eines Schichtbetriebes wird nicht definiert, wenn additiv Ausdruck ist negativ ist oder wenn additiv Ausdruck ist größer als oder gleich der Anzahl der Bits in der (geförderten) Shift-Ausdruck .

Hier ist der Code verwende ich:

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

Überlast eine Funktion:

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

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow