Лучшие практики для операций кругового сдвига (поворота) в C ++

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

99881 просмотра

16 ответа

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

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

Вращается прямо здесь дважды

Initial --> 1000 0011 0100 0010

должно привести к:

Final   --> 1010 0000 1101 0000

Пример будет полезен.

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

Автор: Elroy Источник Размещён: 11.11.2019 03:26

Ответы (16)


93 плюса

Решение

Смотрите также более раннюю версию этого ответа на другой вопрос поворота с некоторыми подробностями о том, что 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 и более поздние версии также оптимизируют ветку и маску в версии википедии, используя только инструкцию a 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/ _rotrintrinsics с <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, которое вы получаете с дополнением без знака или два. (См. Комментарии к сообщению в блоге Регера). unsigned intхорошо работает на каждом компиляторе, на который я смотрел, для любой ширины x. Некоторые другие типы на самом деле побеждают распознавание идиомы для некоторых компиляторов, поэтому не просто используйте тот же тип, что и x.


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

  • Документы Intel, которые <immintrin.h>предоставляют _rotlи _rotl64встроенные , и то же самое для правого смещения. MSVC требует <intrin.h>, а gcc требует <x86intrin.h>. An #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-разрядные повороты определяются с помощью сдвига / или (без защиты от 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 .

Автор: AndreasT Размещён: 22.04.2009 10:28

33 плюса

Поскольку это 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));
}
Автор: MSalters Размещён: 22.04.2009 10:35

20 плюса

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

Автор: VolkerK Размещён: 22.04.2009 10:42

16 плюса

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

template<class T>
T ror(T x, unsigned int moves)
{
  return (x >> moves) | (x << sizeof(T)*8 - moves);
}
Автор: Didac Perez Parera Размещён: 05.12.2012 08:50

7 плюса

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

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

НТН,

Автор: Abhay Размещён: 22.04.2009 11:01

6 плюса

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

Если битовый массив равен 33602 в целых числах

1000 0011 0100 0010

и вам нужно перевернуться с двумя сдвигами вправо, затем: сначала сделайте копию битового шаблона, а затем сдвиньте его влево: длина - сдвиг вправо, т.е. длина равна 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
===================

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

Автор: S M Kamran Размещён: 22.04.2009 11:40

5 плюса

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

x=(x>>1 | x<<7);
Автор: Farhadix Размещён: 27.04.2010 11:55

4 плюса

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

unsigned ror(unsigned x, int L, int N) 
{
    unsigned lsbs = x & ((1 << L) - 1);
    return (x >> L) | (lsbs << (N-L));
}
Автор: nimrodm Размещён: 22.04.2009 10:36

4 плюса

С ++ 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все еще не поддерживает его.

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

Заголовок:

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. Вращающийся [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.

Возвращает: если r равно 0, x; если r положительно (x << r) | (x >> (N - r)),; если г является отрицательным, rotr(x, -r).

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

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

Возвращает: если r равно 0, x; если r положительно (x >> r) | (x << (N - r)),; если г является отрицательным, rotl(x, -r).

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

Автор: Ciro Santilli 新疆改造中心法轮功六四事件 Размещён: 31.07.2019 07:56

3 плюса

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

#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 ) ) ) )
Автор: user3102555 Размещён: 30.05.2014 03:20

0 плюса

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

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;  
}
Автор: kjk Размещён: 31.10.2013 05:24

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;
}
Автор: SalemD Размещён: 16.11.2013 02:13

0 плюса

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

  1. Функции встроены для оптимизации компилятора
  2. Я использовал cout << +valueтрюк для краткого вывода числового знака без знака, который я нашел здесь: https://stackoverflow.com/a/28414758/1599699
  3. Я рекомендую использовать явный <put the type here>синтаксис для ясности и безопасности.
  4. Я использовал unsigned char для параметра shiftNum из-за того, что я нашел в разделе «Дополнительные сведения» здесь :

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

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

#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");
}
Автор: Andrew Размещён: 13.06.2015 09:23

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.
Автор: MikeZ Размещён: 14.08.2015 09:12

-1 плюса

Перегрузить функцию:

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

unsigned short rotate_right(unsigned short x) { /* etc. */ }
Автор: graham.reeds Размещён: 22.04.2009 10:38

-1 плюса

#define ROTATE_RIGHT(x) ( (x>>1) | (x&1?0x8000:0) )
Автор: Dan Byström Размещён: 22.04.2009 10:26
Вопросы из категории :
32x32