Лучшие практики для операций кругового сдвига (поворота) в C++
Операторы сдвига влево и вправо (<< и >>) уже доступны в C++. Тем не менее, я не мог выяснить, как я мог выполнять операции кругового сдвига или поворота.
Как можно выполнять такие операции, как "Поворот влево" и "Поворот вправо"?
Вращается прямо здесь дважды
Initial --> 1000 0011 0100 0010
должно привести к:
Final --> 1010 0000 1101 0000
Пример будет полезен.
(примечание редактора: многие распространенные способы выражения поворотов в C страдают от неопределенного поведения, если счетчик поворотов равен нулю или компилируется не только в одну машинную инструкцию поворота. Ответ на этот вопрос должен задокументировать лучшие практики.)
15 ответов
Смотрите также более раннюю версию этого ответа на другой вопрос поворота с некоторыми подробностями о том, что 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 Msgstr " Я думаю, что gcc запутывается здесь, потому что сдвиги влево / вправо на ARM насыщают счет, поэтому сдвиг на 32 или более очистит регистр. (В отличие от x86, где сдвиги маскируют счет так же, как и вращение). Вероятно, он решает это нужна инструкция AND перед распознаванием идиомы поворота, из-за того, как некруглые сдвиги работают на этой цели.
Текущие x86-компиляторы все еще используют дополнительную инструкцию для маскирования счетчика переменных для 8- и 16-битных поворотов, вероятно, по той же причине, по которой они не избегают AND на ARM. Это пропущенная оптимизация, поскольку производительность не зависит от числа оборотов на любом процессоре x86-64. (Маскирование счетчиков было введено с 286 по соображениям производительности, потому что оно обрабатывало сдвиги итеративно, а не с постоянной задержкой, как современные процессоры.)
Кстати, предпочитайте rotate-right для вращений с переменным счетом, чтобы компилятор не делал 32-n реализовать левый поворот на архитектурах, таких как ARM и MIPS, которые обеспечивают только поворот вправо. (Это оптимизирует счет с постоянными времени компиляции.)
Интересный факт: 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>,#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-компиляторы тоже имеют встроенные функции, но давайте не будем расширять этот вики-ответ сообщества, чтобы включить их все. (Может быть, сделать это в существующем ответе о внутренностях).
(В старой версии этого ответа предлагался встроенный asm для MSVC (который работает только для 32-битного кода x86), или http://www.devx.com/tips/Tip/14043 для версии C. Ответы на этот комментарий.)
Встроенный asm побеждает многие оптимизации, особенно в стиле MSVC, потому что он заставляет входные данные быть сохраненными / перезагруженными. Тщательно написанное вращение in-asm в GNU C позволило бы счету быть непосредственным операндом для счетчиков смещения во время компиляции, но он все равно не мог оптимизировать полностью, если значение, которое должно быть смещено, также является константой времени компиляции после встраивания. https://gcc.gnu.org/wiki/DontUseInlineAsm.
C++20 std::rotl and std::rotr
It has arrived! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html and should add it to the <bit> header.
cppreference says that the usage will be like:
#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';
}
giving output:
i = 00011101
rotl(i,0) = 00011101
rotl(i,1) = 00111010
rotl(i,4) = 11010001
rotl(i,9) = 00111010
rotl(i,-1) = 10001110
I'll give it a try when support arrives to GCC, GCC 9.1.0 with g++-9 -std=c++2a still doesn't support it.
The proposal says:
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;
and:
25.5.5 Rotating [bitops.rot]
In the following descriptions, let N denote
std::numeric_limits<T>::digits.template<class T> [[nodiscard]] constexpr T rotl(T x, int s) noexcept;Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).
Let r be 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;Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]). Let r be s % N.
Returns: If r is 0, x; if r is positive,
(x >> r) | (x << (N - r)); if r is negative,rotl(x, -r).
A std::popcount was also added to count the number of 1 bits: How to count the number of set bits in a 32-bit integer?
Поскольку это 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));
}
Большинство компиляторов имеют встроенные функции для этого. Visual Studio, например _rotr8, _rotr16
Определённо:
template<class T>
T ror(T x, unsigned int moves)
{
return (x >> moves) | (x << sizeof(T)*8 - moves);
}
Если x является 8-битным значением, вы можете использовать это:
x=(x>>1 | x<<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;
}
НТН,
В деталях вы можете применить следующую логику.
Если битовый массив равен 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 ===================
И вы получите свое смещенное значение ролловера. Помните, что побитовые операции выполняются быстрее, и для этого даже не требуется никакого цикла.
Предполагая, что вы хотите сдвинуть вправо 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 ) ) ) )
Другое предложение
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;
}
Исходный код х бит номер
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;
}
Ниже приведен слегка улучшенный вариант ответа Дидака Переса, в котором реализованы оба направления, а также демонстрация использования этих функций с использованием беззнакового символа и беззнаковых длинных длинных значений. Несколько заметок:
- Функции встроены для оптимизации компилятора
- Я использовал
cout << +valueхитрость для краткого вывода числового знака без знака, который я нашел здесь: /questions/45183338/kak-vyivesti-simvol-v-vide-tselogo-chisla-cherez-cout/45183362#45183362 - Я рекомендую использовать явное
<put the type here>синтаксис для ясности и безопасности. - Я использовал 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");
}
Перегрузить функцию:
unsigned int rotate_right(unsigned int x)
{
return (x>>1 | (x&1?0x80000000:0))
}
unsigned short rotate_right(unsigned short x) { /* etc. */ }
--- 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.