Рекомендации по выполнению операций кругового сдвига (поворота) в C++

операторы сдвига влево и вправо (>) уже доступны в C++. Однако я не мог узнать, как я могу выполнять операции кругового сдвига или поворота.

Как можно выполнять такие операции, как" поворот влево "и" поворот вправо"?

поворот вправо дважды здесь

Initial --> 1000 0011 0100 0010

в результате:

Final   --> 1010 0000 1101 0000

пример был бы полезен.

(Примечание редактора: многие распространенные способы выражения вращается в C страдать от неопределенное поведение, если число поворотов равно нулю или компилируется до более чем одной инструкции rotate machine. Ответ на этот вопрос должен документировать лучшие практики.)

15 72

javascript c++ rotation c++-faq bit-manipulation

15 ответов:

Так как это C++, используйте встроенную функцию:

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

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

33

большинство компиляторов имеют встроенные функции для этого. Например, Visual Studio _rotr8, _rotr16

18

окончательно:

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

16

Как насчет чего-то подобного, используя стандартный битсет ...

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

7

в деталях вы можете применить следующую логику.

если битовый шаблон 33602 в Integer
1000 0011 0100 0010
и вам нужно перевернуться с 2 правыми сдвигами, то: сначала сделайте копию битового шаблона, а затем сдвиньте его влево: Length-RightShift т. е. длина 16 значение сдвига вправо равно 2 16 - 2 = 14

после 14 раз левого сдвига вы получаете.
1000 0000 0000 0000
теперь вправо сдвиньте значение 33602, 2 раза по мере необходимости. Вы получите
0010 0000 1101 0000
теперь взять Или между 14 раз левым смещенным значением и 2 раза правым смещенным значением.
1000 0000 0000 0000
0010 0000 1101 0000
===================
1010 0000 1101 0000
===================
и вы получаете свое смещенное значение опрокидывания. Помните, что немного мудрые операции выполняются быстрее, и это даже не требует какого-либо цикла.

6

Если x является 8-битным значением, вы можете использовать это:
x=(x>>1 | x<<7);

5

предполагая, что вы хотите сдвинуть вправо L бит, а вход x - это число с N биты:
unsigned ror(unsigned x, int L, int N) 
{
    unsigned lsbs = x & ((1 << L) - 1);
    return (x >> L) | (lsbs << (N-L));
}

4

правильный ответ следующий:

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

3

Исходный Код х разрядное число

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

0

еще одно предложение

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

0

ниже немного улучшенная версия ответ Дидака Переса, С реализованными обоими направлениями, а также демонстрацией использования этих функций с использованием unsigned char и unsigned long long значений. Несколько нот:

функции встроены для оптимизации компилятора

я использовал cout << +value трюк для краткого вывода беззнакового символа численно, который я нашел здесь: https://stackoverflow.com/a/28414758/1599699

я рекомендую использовать явные <put the type here> синтаксис для ясности и безопасности.

я использовал unsigned char для параметра shiftNum из-за того, что я нашел в разделе дополнительных сведений здесь:

результат операции сдвига не определен, если аддитивное-выражение is отрицательный или если аддитивное-выражение больше или равна количество битов в (продвинутом)shift-expression.

вот код, который я использую:
#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");
}

0

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

0

перегрузка функции:

unsigned int rotate_right(unsigned int x)
{
 return (x>>1 | (x&1?0x80000000:0))
}

unsigned short rotate_right(unsigned short x) { /* etc. */ }

-1

#define ROTATE_RIGHT(x) ( (x>>1) | (x&1?0x8000:0) )

-1

Peter Cordes · Accepted Answer · 2017-06-08 04:46:18

см. Также более раннюю версию это ответ на другой вращающийся вопрос С некоторыми более подробными сведениями о том, что ASM gcc/clang производят для x86.

самый удобный для компилятора способ выразить поворот в C и C++, который позволяет избежать любого неопределенного поведения, кажется,реализация Джона Регера. Я адаптировал его для поворота по ширине типа (например, предполагая, что uint32_t ровно 32 бита в ширину, хотя C/C++ только гарантирует, что это по крайней мере вот так широко. Я попытался сохранить его читаемым, оставив чеки для такого рода вещей).
#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 ));
}
работает для любого целочисленного типа без знака, а не только uint32_t, Так что вы можете сделать версии для других размеров.

посмотреть также версия шаблона C++11 С большим количеством проверок безопасности (в том числе static_assert что ширина типа является силой 2), что не относится к некоторым 24-битным DSPs или 36-битным мэйнфреймам, для образец.

я бы рекомендовал использовать шаблон только в качестве бэк-энда для оболочек с именами, которые явно включают ширину поворота. целочисленные правила продвижения означают, что rotl_template(u16 & 0x11UL, 7) будет делать 32 или 64-битный поворот, а не 16 (в зависимости от ширины unsigned long). Даже uint16_t & uint16_t превращается в signed int по целочисленным правилам продвижения C++, за исключением платформ, где int не шире, чем uint16_t.

на x86 эта версия inlines to a single rol r32, cl (или rol r32, imm8) с компиляторами, которые Грок его, потому что компилятор знает, что x86 поворот и сдвиг инструкции маскируйте счетчик сдвига так же, как это делает источник C.

поддержка компилятора для этой UB-избегающей идиомы на x86, для uint32_t x и unsigned int n для сдвигов с переменным числом:

clang: распознается для переменной-количество вращается с clang3. 5, несколько сдвигов+или insns до что.

gcc:распознается для переменной-количество вращается с gcc4. 9, несколько сдвигов+или insns до этого. gcc5 и позже оптимизируют ветку и маску в версии Википедии, тоже используя только ror или rol инструкция по переменным статьям.

icc:поддерживается для переменных-количество вращается с ICC13 или ранее. Константа-граф поворачивает использовать shld edi,edi,7 который медленнее и занимает больше байтов, чем rol edi,7 на некоторых процессорах (особенно AMD, но и некоторые Intel), когда BMI2 не доступен для rorx eax,edi,25 чтобы сохранить MOV.

MSVC: x86-64 CL19: распознается только для вращения с постоянным числом. (Идиома Википедии распознана, но ветвь и и не оптимизированы). Используйте _rotl/_rotr встроенные функции из <intrin.h> на x86 (включая x86-64).

gcc для ARM использует and r1, r1, #31 для переменной-count вращается, но все еще делает фактический поворот с одним инструкция:ror r0, r0, r1. Таким образом, gcc не понимает, что поворотные счетчики по своей сути являются модульными. Как говорят врачи ARM, " ROR с длиной сдвига,n, больше чем 32 это же как ROR с длиной переноса n-32". Я думаю, что gcc запутывается здесь, потому что левые / правые сдвиги на руке насыщают счет, поэтому сдвиг на 32 или более очистит регистр. (В отличие от x86, где сдвиги маскируют счетчик так же, как и вращается). Вероятно, он решает, что ему нужна инструкция и раньше распознавание идиомы поворота из-за того, как некруглые сдвиги работают на этой цели.

текущие компиляторы x86 по-прежнему используют дополнительную инструкцию для маскировки количества переменных для 8 и 16-битных вращений, вероятно, по той же причине, по которой они не избегают и на ARM. Это пропущенная оптимизация, потому что производительность не зависит от количества вращений на любом процессоре x86-64. (Маскировка подсчетов была введена с 286 по соображениям производительности, потому что она обрабатывала сдвиги итеративно, а не с помощью постоянная задержка, как современные процессоры.)

кстати, предпочитаю вращать-право для переменных-количество вращается, чтобы избежать компилятора сделать 32-n чтобы реализовать поворот влево на архитектурах, таких как ARM и MIPS, которые обеспечивают только поворот вправо. (Это оптимизирует отсчет констант времени компиляции.)

забавный факт: ARM на самом деле не имеет специальных инструкций shift/rotate, это просто MOV с исходный операнд, проходящий через ствол-переключатель в режиме ROR: mov r0, r0, ror r1. Таким образом, поворот может складываться в операнд источника регистра для инструкции EOR или чего-то еще.

убедитесь, что вы используете неподписанные типы для n и возвращаемое значение, иначе это не будет поворот. (gcc для целей x86 выполняет арифметические сдвиги вправо, сдвигая копии знакового бита, а не нули, что приводит к проблеме, когда вы OR два сдвинутых значения вместе. Правые сдвиги отрицательных целых чисел со знаком определяются реализацией поведение В С.)

и убедитесь, что счетчик сдвига является беззнаковым типом, потому что (-n)&31 со знаковым типом может быть дополнением или знаком/величиной, а не то же самое, что модульный 2^n, который вы получаете с дополнением без знака или двух. (См. комментарии к сообщению в блоге Регера). unsigned int хорошо работает на каждом компиляторе, на который я смотрел, для каждой ширины x. Некоторые другие типы фактически побеждают идиому-распознавание для некоторых компиляторов, поэтому не просто используйте то же самое типа как x.

некоторые компиляторы предоставляют встроенные функции для проворачивается, что намного лучше, чем inline-asm, если портативная версия не генерирует хороший код на компиляторе, на который вы нацелены. Нет кросс-платформенных встроенных компонентов для любых компиляторов, о которых я знаю. Вот некоторые из вариантов x86:

документы Intel, что <immintrin.h> предоставляет _rotl и _rotl64 встроенные функции, и то же самое для правой смены. MSVC требует <intrin.h>, в то время как gcc требует <x86intrin.h>. Ан #ifdef заботится о gcc против icc, но clang, похоже, не предоставляет их нигде, за исключением режима совместимости MSVC с -fms-extensions -fms-compatibility -fms-compatibility-version=17.00. И asm он испускает для них отстой (дополнительная маскировка и CMOV).

MSVC:_rotr8 и _rotr16.

gcc и icc (не лязг):<x86intrin.h> предоставляет __rolb/__rorb для 8-битного поворота влево / вправо,__rolw/__rorw (16-бит), __rold/__rord (32-бит), __rolq/__rorq (64-разрядный, только для 64-разрядных целей). Для узких поворотов реализация использует __builtin_ia32_rolhi или ...qi, но 32 и 64-разрядные повороты определяются с помощью shift/or (без защиты от UB, потому что код в ia32intrin.h только должен работать на gcc для x86). GNU C, похоже, не имеет никакой кросс-платформенной __builtin_rotate функционирует так же, как и для __builtin_popcount (который расширяется до оптимального, что на целевой платформе, даже если это не одна инструкция). Большую часть времени вы получаете хороший код от идиомы-распознавания.
// 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
предположительно, некоторые компиляторы, отличные от x86, также имеют встроенные функции, но давайте не будем расширять этот ответ сообщества-wiki, чтобы включить их все. (Может быть, сделать это в существующий ответ о свойствах).

(старая версия этого ответа предложила MSVC-specific inline asm (который работает только для 32bit x86 код), или http://www.devx.com/tips/Tip/14043 для версии C. Комментарии отвечают на это.)

встроенный asm побеждает многие оптимизации,особенно MSVC-стиль, потому что он заставляет входы храниться/перезагружаться. Тщательно написанный GNU C inline-asm rotate позволит count быть непосредственным операндом для подсчетов сдвига постоянной времени компиляции, но он все еще не может полностью оптимизировать, если значение, которое должно быть сдвинуто также константа времени компиляции после встраивания. https://gcc.gnu.org/wiki/DontUseInlineAsm.