Najlepsze rozwiązania dotyczące operacji przesunięcia cyklicznego (obracania) w języku C ++

Operatory przesunięcia w lewo i w prawo (<< i >>) są już dostępne w C ++. Jednak nie mogłem dowiedzieć się, jak mogę wykonywać operacje przesuwania okrężnego lub obracania.

Jak można wykonywać operacje takie jak „Obróć w lewo” i „Obróć w prawo”?

Obracanie w prawo dwukrotnie tutaj

Initial --> 1000 0011 0100 0010

powinno skutkować:

Final   --> 1010 0000 1101 0000

Przykład byłby pomocny.

(Uwaga redaktora: Wiele typowych sposobów wyrażania rotacji w C cierpi z powodu niezdefiniowanego zachowania, jeśli liczba rotacji wynosi zero lub kompilacji do więcej niż jednej instrukcji maszyny rotacji. Odpowiedź na to pytanie powinna udokumentować najlepsze praktyki).

Zobacz także wcześniejszą wersję tej odpowiedzi na inne pytanie dotyczące rotacji, zawierającą więcej szczegółów na temat tego, co asm gcc / clang produkuje dla x86.

Najbardziej przyjaznym dla kompilatora sposobem wyrażenia rotacji w C i C ++, który pozwala uniknąć niezdefiniowanego zachowania, wydaje się być implementacja Johna Regehra . Dostosowałem go do obracania się o szerokość typu (używając typów o stałej szerokości, takich jak 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 ));
}

Działa dla każdego typu liczby całkowitej bez znaku, nie tylko uint32_t, więc możesz tworzyć wersje dla innych rozmiarów.

Zobacz także wersję szablonu C ++ 11 z wieloma sprawdzeniami bezpieczeństwa (w tym, static_assertże szerokość typu to potęga 2) , co nie ma miejsca na przykład w przypadku niektórych 24-bitowych DSP lub 36-bitowych komputerów mainframe.

Zalecam używanie szablonu tylko jako zaplecza dla opakowań z nazwami, które jawnie zawierają szerokość obrotu. Reguły promocji liczb całkowitych oznaczają, że rotl_template(u16 & 0x11UL, 7)obrót wykonywałby 32 lub 64-bitowy, a nie 16 (w zależności od szerokości unsigned long). Nawet uint16_t & uint16_tjest promowany signed intprzez reguły C ++ dotyczące promocji liczb całkowitych, z wyjątkiem platform, na których intnie jest szerszy niż uint16_t.

Na x86 , ta wersja jest wbudowana do pojedynczegorol r32, cl (lub rol r32, imm8) z kompilatorami, które go grokują, ponieważ kompilator wie, że instrukcje obrotu i przesunięcia x86 maskują liczbę przesunięć w taki sam sposób, jak robi to źródło C.

Obsługa kompilatora dla tego idiomu unikania UB na x86, dla uint32_t xi unsigned int ndla przesunięć o zmiennej liczbie:

• clang: rozpoznawany jako zmienna liczba obraca się od clang3.5, wiele zmian + lub insns przed tym.
• gcc: rozpoznawane jako zmienna-count obraca się od gcc4.9 , wiele przesunięć + lub insns przed tym. gcc5, a później optymalizuje gałąź i maskę również w wersji wikipedii, używając tylko instrukcji rorlub roldla liczby zmiennych.
• icc: obsługiwane dla rotacji o zmiennej liczbie od ICC13 lub wcześniejszej . Stałe liczenie obraca użycie, shld edi,edi,7które jest wolniejsze i zajmuje więcej bajtów niż rol edi,7na niektórych procesorach (zwłaszcza AMD, ale także niektórych Intel), gdy BMI2 nie jest dostępne rorx eax,edi,25do zapisania pliku MOV.
• MSVC: x86-64 CL19: rozpoznawany tylko w przypadku rotacji o stałej liczbie. (Rozpoznawany jest idiom Wikipedii, ale gałąź i AND nie są zoptymalizowane). Użyj _rotl/ _rotrintrinsics z <intrin.h>x86 (w tym x86-64).

gcc dla ARM używa and r1, r1, #31do obracania zmiennej count, ale nadal robi rzeczywistego obracają się z pojedynczej instrukcji : ror r0, r0, r1. Więc gcc nie zdaje sobie sprawy, że rotate-count są z natury modularne. Jak mówi dokumentacja ARM, „ROR z długością przesunięcia n, więcej niż 32 to to samo, co ROR z długością przesunięcia n-32” . Myślę, że gcc jest tu zdezorientowany, ponieważ przesunięcia w lewo / w prawo na ARM nasycają licznik, więc przesunięcie o 32 lub więcej wyczyści rejestr. (W przeciwieństwie do x86, gdzie przesunięcia maskują liczbę tak samo, jak obroty). Prawdopodobnie decyduje, że potrzebuje instrukcji AND przed rozpoznaniem idiomu rotacji, z powodu tego, jak przesunięcia niekołowe działają na ten cel.

Obecne kompilatory x86 nadal używają dodatkowej instrukcji do maskowania zmiennej liczby obrotów dla 8 i 16-bitowych obrotów, prawdopodobnie z tego samego powodu, dla którego nie unikają AND na ARM. Jest to pominięta optymalizacja, ponieważ wydajność nie zależy od liczby obrotów na żadnym procesorze x86-64. (Maskowanie zliczeń zostało wprowadzone w 286 ze względu na wydajność, ponieważ obsługiwało zmiany iteracyjnie, a nie ze stałym opóźnieniem, jak w przypadku nowoczesnych procesorów).

Przy okazji, preferuj rotację w prawo dla rotacji ze zmienną liczbą, aby uniknąć zmuszania kompilatora 32-ndo zaimplementowania rotacji w lewo na architekturach takich jak ARM i MIPS, które zapewniają tylko rotację w prawo. (Optymalizuje to zliczaniem stałych czasu kompilacji).

Ciekawostka: ARM tak naprawdę nie ma dedykowanego shift / obracanie wskazówek, to tylko MOV ze źródła argumentu przechodzi beczki-shifter w trybie ROR : mov r0, r0, ror r1. Więc rotate może złożyć w operand rejestru źródłowego dla instrukcji EOR lub czegoś podobnego.

Upewnij się, że używasz typów bez znaku dla ni wartości zwracanej, w przeciwnym razie nie będzie to rotacja . (gcc dla celów x86 wykonuje arytmetyczne przesunięcia w prawo, przesuwając kopie bitu znaku zamiast zer, co prowadzi do problemu, gdy ORte dwie wartości są przesunięte razem. Przesunięcia w prawo ujemnych liczb całkowitych ze znakiem to zachowanie zdefiniowane przez implementację w języku C.)

Upewnij się również, że liczba przesunięć jest typem bez znaku , ponieważ (-n)&31w przypadku typu ze znakiem może to być uzupełnienie lub znak / wielkość, a nie to samo, co modularne 2 ^ n, które otrzymujesz z uzupełnieniem bez znaku lub do dwóch. (Zobacz komentarze do wpisu na blogu Regehr). unsigned intdziała dobrze na każdym kompilatorze, który oglądałem, dla każdej szerokości x. Niektóre inne typy faktycznie pokonują rozpoznawanie idiomów dla niektórych kompilatorów, więc nie używaj tylko tego samego typu, co x.

Niektóre kompilatory zapewniają funkcje wewnętrzne dla rotacji , co jest znacznie lepsze niż inline-asm, jeśli wersja przenośna nie generuje dobrego kodu w kompilatorze, na który jest przeznaczona. Nie ma elementów wewnętrznych dla wielu platform dla żadnych znanych mi kompilatorów. Oto niektóre z opcji x86:

• Dokumenty firmy Intel, które <immintrin.h>zapewniają _rotli _rotl64wewnętrzne , i to samo dla prawego przesunięcia. MSVC wymaga <intrin.h>, podczas gdy gcc wymaga <x86intrin.h>. An #ifdefzajmuje się gcc vs. icc, ale clang nie wydaje się ich dostarczać nigdzie, z wyjątkiem trybu zgodności MSVC z-fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . A asm, który dla nich emituje, jest do bani (dodatkowe maskowanie i CMOV).
• MSVC: _rotr8i_rotr16 .
• gcc i icc (nie clang): <x86intrin.h>zapewnia również __rolb/ __rorbdla 8-bitowego obrotu w lewo / w prawo, __rolw/ __rorw(16-bitowy), __rold/ __rord(32-bitowy), __rolq/ __rorq(64-bitowy, zdefiniowany tylko dla 64-bitowych celów). W przypadku wąskich obrotów implementacja używa __builtin_ia32_rolhilub ...qi, ale obroty 32 i 64-bitowe są definiowane za pomocą shift / lub (bez ochrony przed UB, ponieważ kod ia32intrin.hmusi działać tylko na gcc dla x86). Wydaje się, że GNU C nie ma żadnych __builtin_rotatefunkcji wieloplatformowych, jak to ma miejsce __builtin_popcount(co rozszerza się na wszystko, co jest optymalne na platformie docelowej, nawet jeśli nie jest to pojedyncza instrukcja). W większości przypadków dobry kod uzyskuje się dzięki rozpoznawaniu idiomów.

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

Prawdopodobnie niektóre kompilatory inne niż x86 również mają wewnętrzne elementy, ale nie rozszerzajmy tej odpowiedzi społeczności wiki, aby uwzględnić je wszystkie. (Może zrób to w istniejącej odpowiedzi na temat wewnętrznych elementów ).

(Stara wersja tej odpowiedzi sugerowała wbudowany asm specyficzny dla MSVC (który działa tylko dla 32-bitowego kodu x86) lub http://www.devx.com/tips/Tip/14043 dla wersji C. Komentarze odpowiadają na to .)

Asm inline pokonuje wiele optymalizacji , zwłaszcza w stylu MSVC, ponieważ wymusza przechowywanie / ponowne ładowanie danych wejściowych . Starannie napisana rotacja inline-asm GNU C pozwoliłaby licznikowi być natychmiastowym operandem dla zliczeń przesunięć stałych w czasie kompilacji, ale nadal nie można było całkowicie zoptymalizować, jeśli wartość, która ma zostać przesunięta, jest również stałą czasu kompilacji po inliningu. https://gcc.gnu.org/wiki/DontUseInlineAsm .

Ponieważ jest to C ++, użyj funkcji inline:

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

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

Większość kompilatorów ma do tego wewnętrzne cechy. Visual Studio, na przykład _rotr8, _rotr16

C ++ 20 std::rotlistd::rotr

Przybył! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html i należy dodać go do <bit>nagłówka.

cppreference mówi, że użycie będzie wyglądać następująco:

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

dając wynik:

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

Spróbuję, gdy wsparcie dotrze do GCC, GCC 9.1.0 g++-9 -std=c++2anadal go nie obsługuje.

Propozycja mówi:

Nagłówek:

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;

i:

25.5.5 Obracanie [bitops.rot]

W poniższych opisach niech N oznacza std::numeric_limits<T>::digits.

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

Ograniczenia: T jest typem liczby całkowitej bez znaku (3.9.1 [basic.fundamental]).

Niech r będzie% N.

Zwroty: Jeśli r wynosi 0, x; jeśli r jest dodatnie (x << r) | (x >> (N - r)),; gdy R jest negatywna rotr(x, -r).

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

Ograniczenia: T jest typem liczby całkowitej bez znaku (3.9.1 [basic.fundamental]). Niech r będzie% N.

Zwroty: Jeśli r wynosi 0, x; jeśli r jest dodatnie (x >> r) | (x << (N - r)),; gdy R jest negatywna rotl(x, -r).

Dodano std::popcountrównież A, aby policzyć liczbę 1 bitów: Jak policzyć liczbę ustawionych bitów w 32-bitowej liczbie całkowitej?

Ostatecznie:

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

Jak coś takiego, używając standardowego zestawu bitów ...

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

Jeśli x jest wartością 8-bitową, możesz użyć tego:

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

W szczegółach możesz zastosować następującą logikę.

Jeśli wzorzec bitowy to 33602 w liczbie całkowitej

1000 0011 0100 0010

i musisz przewrócić z 2 prawymi przesunięciami, a następnie: najpierw wykonaj kopię wzoru bitowego, a następnie przesuń go w lewo: Długość - RightShift tj. długość wynosi 16, wartość przesunięcia w prawo wynosi 2 16 - 2 = 14

Po 14-krotnej zmianie przełożeń otrzymujesz.

1000 0000 0000 0000

Teraz przesuń w prawo wartość 33602, 2 razy zgodnie z wymaganiami. Dostajesz

0010 0000 1101 0000

Teraz weź OR pomiędzy 14 razy przesuniętą wartością w lewo i 2 razy przesuniętą w prawo wartością.

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

I otrzymujesz przesuniętą wartość kumulacji. Pamiętaj, że operacje bitowe są szybsze, a to nawet nie wymaga żadnej pętli.

Zakładając, że chcesz przesunąć się w prawo o Lbity, a dane wejściowe xto liczba z Nbitami:

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

Prawidłowa odpowiedź brzmi:

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

Kod źródłowy x liczba bitów

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

kolejna sugestia

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

Poniżej znajduje się nieco ulepszona wersja odpowiedzi Dídaca Péreza , z zaimplementowanymi dwoma kierunkami, wraz z demonstracją użycia tych funkcji przy użyciu wartości unsigned char i unsigned long long. Kilka uwag:

1. Funkcje są wbudowane w celu optymalizacji kompilatora
2. Użyłem cout << +valuesztuczki do zwięzłego wyprowadzania liczbowego znaku bez znaku, którą znalazłem tutaj: https://stackoverflow.com/a/28414758/1599699
3. Zalecam użycie jawnej <put the type here>składni dla jasności i bezpieczeństwa.
4. Użyłem unsigned char dla parametru shiftNum z powodu tego, co znalazłem w sekcji Dodatkowe szczegóły tutaj :

Wynik operacji przesunięcia jest niezdefiniowany, jeśli wyrażenie-addytywne jest ujemne lub jeśli wyrażenie-addytywne jest większe lub równe liczbie bitów w (promowanym) wyrażeniu przesuwającym .

Oto kod, którego używam:

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

Przeciąż funkcję:

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