Рекомендации по циклическим сдвигам (поворот) в С++

Ответ 1

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

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

Работает для любого целого типа без знака, не только uint32_t, поэтому вы можете создавать версии для других размеров.

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

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

В x86 эта версия встроена в один 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: распознается только при поворотах с постоянным счетом. (Идиома википедии распознается, но ветвь и AND не оптимизированы). Используйте встроенные функции _rotl/_rotr из <intrin.h> в x86 (включая x86-64).

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

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

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

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

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

Кроме того, убедитесь, что счетчик сдвига относится к типу без знака, потому что (-n)&31 со типом со знаком может быть одним дополнением или знаком/величиной, а не тем же модульным 2 ^ n, который вы получаете с помощью без знака или два дополнения. (См. комментарии к сообщению в блоге Regehr). 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 (не clang): <x86intrin.h> также предоставляет __rolb/__rorb для 8-битного поворота влево/вправо, __rolw/__rorw (16-бит), __rold/__rord ( 32-битный), __rolq/__rorq (64-битный, определен только для 64-битных целей). Для узких поворотов реализация использует __builtin_ia32_rolhi или ...qi, но 32- и 64-разрядные повороты определяются с помощью shift/или (без защиты от 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-компиляторы тоже имеют встроенные функции, но давайте не будем расширять этот вики-ответ сообщества, чтобы включить их все. (Возможно, сделайте это в существующем ответе о встроенных функциях).

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

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

Ответ 2

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

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

Вариант С++ 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));
}

Ответ 3

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

Ответ 4

Определённо:

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

Ответ 5

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

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

НТН,

Ответ 6

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

Если бит-шаблон равен 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

Теперь возьмите OR между 14-секундным сдвинутым влево значением и 2-кратным сдвинутым вправо значением.

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

И вы получите переменное значение опрокидывания. Помните, что бит мудрый операции быстрее, и это даже не требует никакого цикла.

Ответ 7

Если x является 8-битным значением, вы можете использовать это:

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

Ответ 8

Предполагая, что вы хотите сдвинуть право на бит L, а вход x - это число с битами N:

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

Ответ 9

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

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

Ответ 10

С++ 20 std::rotl и std::rotr

Это прибыло! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html и должен добавить его в заголовок <bit>.

cppreference говорит, что использование будет таким:

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

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

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

Я попробую, когда поддержка придет в GCC, GCC 9.1.0 с g++-9 -std=c++2a все еще не поддерживает его.

Предложение гласит:

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;

и:

25.5.5 Rotating [bitops.rot]

В следующих описаниях пусть N обозначает std::numeric_limits<T>::digits.

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

Ограничения: T - целочисленный тип без знака (3.9.1 [basic.fundamental]).

Пусть r будет s% N.

Returns: If r is 0, x; if r is positive, (x << r) | (x >> (N - r)); if r is negative, rotr(x, -r).

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

Ограничения: T - целочисленный тип без знака (3.9.1 [basic.fundamental]). Пусть r будет s% N.

Returns: If r is 0, x; if r is positive, (x >> r) | (x << (N - r)); if r is negative, rotl(x, -r).

std::popcount также был добавлен для подсчета числа 1 бит: Как подсчитать количество установленных бит в 32-битном целом числе?

Ответ 11

Исходный код  x бит номер

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

Ответ 12

другое предложение

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

Ответ 13

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

• Функции встроены в оптимизацию компилятора
• Я использовал трюк cout << +value для численного вывода беззнакового char численно, который я нашел здесь: fooobar.com/questions/4602/...
• Я рекомендую использовать явный синтаксис <put the type here> для ясности и безопасности.
• Я использовал unsigned char для параметра shiftNum из-за того, что я нашел в разделе дополнительных сведений здесь:

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

Вот код, который я использую:

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

Ответ 14

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

Ответ 15

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

Ответ 16

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

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

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