Операторы сдвига влево и вправо (<< и >>) уже доступны в C ++. Однако я не мог понять, как я могу выполнять операции кругового сдвига или поворота.
Как можно выполнять такие операции, как «Повернуть влево» и «Повернуть вправо»?
Здесь дважды вращается вправо
Initial --> 1000 0011 0100 0010
должен привести к:
Final --> 1010 0000 1101 0000
Пример был бы полезен.
(Примечание редактора: многие распространенные способы выражения вращений в C страдают от неопределенного поведения, если счетчик вращений равен нулю или компилируется в более чем одну машинную команду вращения. В ответе на этот вопрос должны быть отражены лучшие практики.)
Ответы:
См. Также более раннюю версию этого ответа по другому вопросу о ротации с более подробной информацией о том, что 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что ширина типа является степенью двойки) , чего, например, нет в некоторых 24-битных DSP или 36-битных мэйнфреймах.Я бы рекомендовал использовать шаблон только как серверную часть для оболочек с именами, которые явно включают ширину поворота. Правила целочисленного продвижения означают,
rotl_template(u16 & 0x11UL, 7)что выполняется поворот на 32 или 64 бита, а не на 16 (в зависимости от шириныunsigned long). Дажеuint16_t & uint16_tповышен доsigned intпо правилам целочисленного продвижения С ++, за исключением того, на платформах , гдеintнет ширеuint16_t.На x86 эта версия встроена в одиночный
rol r32, cl(илиrol r32, imm8) с компиляторами, которые ее обрабатывают, потому что компилятор знает, что инструкции поворота и сдвига x86 маскируют счетчик сдвигов так же, как это делает источник C.Поддержка компилятором этой идиомы, избегающей UB на x86, для
uint32_t xиunsigned int nдля сдвигов количества переменных:rorилиrolдля подсчета переменных.shld edi,edi,7что медленнее и занимает больше байтов, чемrol edi,7на некоторых процессорах (особенно AMD, но также и некоторых Intel), когда BMI2 недоступен дляrorx eax,edi,25сохранения MOV._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 по соображениям производительности, потому что оно обрабатывает сдвиги итеративно, а не с постоянной задержкой, как современные процессоры.)
Кстати, предпочитайте поворот вправо для поворота с переменным счетчиком, чтобы компилятор не
32-nреализовал поворот влево на таких архитектурах, как ARM и MIPS, которые обеспечивают только поворот вправо. (Это оптимизирует счет за счет постоянных времени компиляции.)Забавный факт: 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:
<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)._rotr8и_rotr16.<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, потому что он заставляет вводные данные сохраняться / перезагружаться . Тщательно написанный GNU C inline-asm rotate позволит счетчику быть непосредственным операндом для счетчиков сдвига с постоянной времени компиляции, но он все равно не сможет полностью оптимизировать, если значение, которое должно быть сдвинуто, также является константой времени компиляции после встраивания. https://gcc.gnu.org/wiki/DontUseInlineAsm .
источник
bits = CHAR_BIT * sizeof(n);и нет,c &= bits - 1;иreturn ((n >> c) | (n << (bits - c))), что я бы использовал?bits - c=32 - 0. (Я не получил пинг из-за этого, потому что я только редактировал вики, а не писал ее вообще.)0 < count < bits- постоянное требование почти всех процессоров и языков программирования, реализующих ротацию (иногда0 ≤ count < bits, но сдвиг на точное количество битов практически всегда либо не определен, либо округляется до nop вместо того, чтобы очищать значение и вращать, ну.)Поскольку это 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)); }источник
INTэто целое число со знаком и знак установлен! Например,rol<std::int32_t>(1 << 31)проверьте, что должно перевернуться на 1, но на самом деле становится-1(потому что знак сохраняется).std::numeric_limits<INT>::digitsвместоCHAR_BIT * sizeof. Я забываю, разрешено ли беззнаковым типам иметь неиспользуемые отступы (например, 24-битные целые числа, хранящиеся в 32-битных), но если это так, тогдаdigitsбудет лучше. См. Также gist.github.com/pabigot/7550454 для версии с дополнительной проверкой сдвига количества переменных.У большинства компиляторов есть встроенные функции для этого. Visual Studio, например _rotr8, _rotr16
источник
C ++ 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прежнему не поддерживает его.В предложении говорится:
а также:
Также
std::popcountбыл добавлен A для подсчета количества 1 бит: Как подсчитать количество установленных битов в 32-битном целом числе?источник
Окончательно:
template<class T> T ror(T x, unsigned int moves) { return (x >> moves) | (x << sizeof(T)*8 - moves); }источник
8неправильное написаниеCHAR_BIT(которое не обязательно равно 8)?std::numeric_limits<T>::digits.Как примерно так, используя стандартный битовый набор ...
#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,
источник
m %= N;в учет смены>= N.Если x - 8-битное значение, вы можете использовать это:
x=(x>>1 | x<<7);источник
xбудет подписан.Детально вы можете применить следующую логику.
Если битовый шаблон равен 33602 в целочисленном
и вам нужно перевернуться с двумя правыми сдвигами, затем: сначала сделайте копию битового шаблона, а затем сдвиньте его влево: Length - RightShift, то есть длина равна 16, значение сдвига вправо равно 2 16-2 = 14
После 14-кратного переключения влево вы получите.
Теперь сдвиньте вправо значение 33602, 2 раза по мере необходимости. Вы получаете
Теперь возьмите ИЛИ между значением, сдвинутым влево в 14 раз, и значением, сдвинутым вправо в 2 раза.
И вы получите сдвинутую стоимость ролловера. Помните, что побитовые операции выполняются быстрее, и для этого даже не требуется никакого цикла.
источник
Предполагая, что вы хотите сдвинуть вправо по
Lбитам, а вводx- это число сNбитами:unsigned ror(unsigned x, int L, int N) { unsigned lsbs = x & ((1 << L) - 1); return (x >> L) | (lsbs << (N-L)); }источник
Правильный ответ следующий:
#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 ) ) ) )источник
valбудет подписан.Исходный код 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; }источник
другое предложение
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; }источник
Ниже представлена немного улучшенная версия ответа Дидака Переса с реализованными обоими направлениями, а также демонстрация использования этих функций с использованием значений unsigned char и unsigned long long. Несколько примечаний:
cout << +valueуловку для краткого числового вывода беззнакового символа, который я нашел здесь: qaru.site/questions/435 / ... / a / 28414758/1599699<put the type here>синтаксис для ясности и безопасности.Вот код, который я использую:
#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.источник
Перегрузить функцию:
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) )источник