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

Question

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

Лучше не создавать объекты постоянно, используя renderUI, вместо этого мы можем просто обновить виджет:

library(shiny)

data <- c(111,222,333)
ui <- fluidPage(
  selectInput('p_id','ID:', data),
  selectInput('days','Days:', choices = NULL)
)

server = function(input, output, session) {

  observeEvent(input$p_id,{
    mseq <- seq(1,which(data %in% input$p_id))
    updateSelectInput(session,"days","Days:",choices = mseq)
  })

}
runApp(shinyApp(ui = ui, server = server))

[115 ]

84

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

задан 7 revs, 3 users 63% 18 November 2015 в 08:24

9 ответов

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

-1

ответ дан 24 November 2019 в 08:31

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

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

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

-1

ответ дан 24 November 2019 в 08:31

Подробно вы можете применить следующую логику:

Если битовая комбинация равна 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
===================

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

6

ответ дан 24 November 2019 в 08:31

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

#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

ответ дан 24 November 2019 в 08:31

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

20

ответ дан 24 November 2019 в 08:31

Так как это 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

ответ дан 24 November 2019 в 08:31

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

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

4

ответ дан 24 November 2019 в 08:31

Если x - 8-битное значение, вы можете использовать следующее:

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

5

ответ дан 24 November 2019 в 08:31

Другие вопросы по тегам:

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

Похожие вопросы:

score 93 · Accepted Answer

См. Также более раннюю версию этого ответа на другой вопрос поворота с некоторыми более подробными сведениями о том, что 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-битных мэйнфреймах.

I ' рекомендую использовать шаблон только в качестве внутреннего интерфейса для упаковщиков с именами, в которых явно указана ширина поворота. Правила целочисленного продвижения означают, что rotl_template (u16 & 0x11UL, 7) будет выполнять 32- или 64-битное вращение, а не 16 (в зависимости от ширины unsigned long ). Даже uint16_t & uint16_t повышен до со знаком 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 ISN» t доступно для rorx eax, edi, 25 для сохранения MOV.
MSVC: x86-64 CL19: распознается только для вращений с постоянным счетом. (Идиома википедии распознается, но ветвь и AND не оптимизированы). Используйте встроенные функции _rotl / _rotr из в x86 (включая x86-64).

gcc для ARM использует и 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, которые обеспечивают только вращение вправо. (Это оптимизирует счет с постоянными времени компиляции.)

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

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

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

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

Intel документирует, что предоставляет внутренние _rotl и _rotl64 , и то же самое для права сдвиг. MSVC требует , а gcc требует . #ifdef заботится о gcc против icc, но кажется, что clang их нигде не предоставляет, , за исключением режима совместимости MSVC с -fms-extensions -fms-compatibility -fms -compatibility-версия = 17.00 . И asm, который он испускает для них, отстой (дополнительная маскировка и CMOV).
MSVC: _rotr8 и _rotr16 .
gcc и icc (не clang): также предоставляет __ 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 не имеет кроссплатформенных функций __buildin_rotate так, как для __buildin_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, также имеют встроенные функции, но давайте не будем расширять этот ответ вики-сообщества, чтобы включить их все. (Возможно, сделайте это в существующем ответе о встроенных функциях ).

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

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