Как сделать циклический сдвиг строки

Добавил пользователь Валентин П.
Обновлено: 18.09.2024

Битовые сдвиги в C++ как и в других языках программирования относят к логическим операциям, эти операции обычно выполняются над беззнаковыми целыми числами, позволяя быстро поделить на 2 (сдвиг >>) или умножить на 2 (сдвиг

Вообще, здесь нужно вспомнить, что любое целое число представляется в двоичной системе счисления

здесь a₀, a₁, a₂. a_n - числа 0 и 1; b - знаковый бит: -1 или 1.

В ячейки памяти ЭВМ 0 и 1 из представления числа записываются в следующем порядке:

Существуют также беззнаковые типы данных (unsigned)

В этом случае знаковый бит не пишется и порядок записи такой:

142 = 0*1 + 1*2 + 1*2 2 + 1*2 3 + 0*2 4 + 0*2 5 + 0*2 6 + 1*2 7 = 10001110

Количество битов выделяемых на целое число определяется его типом (short - короткие, long - длинные и т.д.) и конкретной реализацией языка.

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

Направление зависит от вида сдвига, которых всего два: сдвиг вправо - “>>” и сдвиг влево - “

Значение b будет равно 512. То есть сдвиг вправо эквивалентен делению на 2, а сдвиг влево умножению на 2. Сдвиговые операции быстрее умножения и деления на 2 обычным способом.

При сдвигах вопрос вызывают крайние биты, для которых нет сдвигаемого значения или места в переменной. Например, если мы сдвинем влево переменную a на 6, мы получим что число 1024, а точнее 0000010000000000, выйдет из пределов unsigned short, а так же появятся биты, которые займут места первых 6 сдвинутых битов. На этот счет в C++ есть правило: если сдвигаемый бит нечем заменить, замена производится на 0. Так, же если сдвигаемый бит есть, а места под него нет, то есть выходит за границы типа, то возникает переполнение. Результат такой функции сильно зависит от используемой платформы, и применять такой подход не рекомендуется.

Аналогично и с числами со знаками. Использует ли их как еще 1 бит или просто откинет зависит от платформы.

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

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

Наиболее удобным для компилятора способом выражения поворота в C и C++, позволяющим избежать любого неопределенного поведения, является реализация Джона Рейгера. Я адаптировал его для поворота по ширине шрифта (используя типы с фиксированной шириной, такие как uint32_t ).

Работает для любого целого типа без знака, не только 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 из в x86 (включая x86-64).

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

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

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

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

Предположительно, некоторые не x86-компиляторы тоже имеют встроенные функции, но давайте не будем расширять этот вики-ответ сообщества, чтобы включить их все. (Возможно, сделайте это в существующем ответе о встроенных функциях).

Ответ 2

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

Ответ 3

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

k-й циклический сдвиг строки – это строка, полученная перестановкой первых k символов строки в её конец. В частности, 0-й циклический сдвиг строки – это сама строка.

И он написал программу, которая умеет перемещать первый символ строки в её конец k раз, получая таким образом k-й циклический сдвиг строки.

Сегодня Васе нужно реализовать разворот строки. Но у Васи тренировка. Ему некогда писать новые сложные программы. Поэтому он задался вопросом:

Можно ли циклическими сдвигами развернуть строку?

Благодаря своим друзьям Вася узнал, на какой строке (да, всего одной) будет тестировать его программу учитель, у которого нет времени рецензировать код каждого ученика. Поэтому вопрос упростился:

Можно ли циклическими сдвигами развернуть строку s?

Помогите ему ответить на этот вопрос.

Формат входных данных

Первая строка содержит одно целое число n (1≤n≤3⋅105) – длина строки s.

Во второй строке – сама строка s, на которой будет тестировать программу Васи учитель. Состоит строка s только из строчных латинских букв.

Формат выходных данных

Если строку нельзя развернуть циклическими сдвигами, то выведите число −1. В противном случае выведите такое целое число k (0≤k
Пояснение к примеру

0-й циклический сдвиг строки s равен abac.

1-й циклический сдвиг строки s равен baca.

2-й циклический сдвиг строки s равен acab.

3-й циклический сдвиг строки s равен caba.

Развёрнутая строка s равна caba.

Единственное подходящее k равно трём.

4
abac
Sample Output:

\u00a0 \u00a0while slovo!=slovo2:\n

\u00a0 \u00a0 \u00a0 \u00a0if count>=a:\n

\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0count=-1\n

\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0break\n

\u00a0 \u00a0 \u00a0 \u00a0word=slovo[:1]\n

\u00a0 \u00a0 \u00a0 \u00a0slovo=slovo[1:]\n

\u00a0 \u00a0 \u00a0 \u00a0slovo+=word\n

\u00a0 \u00a0 \u00a0 \u00a0count+=1\n

\u041e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435:\u043d\u0430 \u04151 \u0438 \u04152 \u043f\u043e\u0434\u043e\u0439\u0434\u0435\u0442, \u043d\u0430 \u04353 \u043d\u0435\u0442

Ответ:

Объяснение:на Е1 и Е2 подойдет, на е3 нет

Новые вопросы в Информатика

Дано: Коэффициенты рождаемости и смертности — n=10 и m=9. Численность населения — 9898000 человек. Количество лет — 8. Численность населения составит … . человек.

Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она ч … ётна, то в начало цепочки символов добавляется символ А, а если нечётна, то последний символ цепочки удаляется. В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А — на Б, Б — на В и т. д., а Я — на А). Получившаяся таким образом цепочка является результатом работы алгоритма. Например, если исходной была цепочка СОН, то результатом работы алгоритма будет цепочка ТП, а если исходной была цепочка УМ, то результатом работы алгоритма будет цепочка БФН. Дана цепочка символов ПОЛЁТ. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т. е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)? Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ. Задания Д15 Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она чётна, то дублируется левый символ цепочки, а если нечётна, то в конец цепочки добавляется буква П. В полученной цепочке символов каждая буква заменяется буквой, стоящей перед ней в русском алфавите (А — на Я, Б — на А и т. д., Я — на Ю). Получившаяся таким образом цепочка является результатом работы описанного алгоритма. Например, если исходной была цепочка УРА, то результатом работы алгоритма будет цепочка ТПЯО, а если исходной была цепочка КРОТ, то результатом работы алгоритма будет цепочка ЙЙПНС. Дана цепочка символов НЕГА. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т. е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)? Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

Определите значение переменной а после выполнение алгоритма: Пример №1 a := 4 b := 10 a:= b - a *2 b := 24 / a*4 Пример №2 Определите значение переме … нной а после выполнение алгоритма: a := 5 b := 4 b := 100 – a*b a:= b /16*a Пример №3 Определите значение переменной а после выполнение алгоритма: a := 1 b := 24 a := b – a*4 b:= a*2 - b

перепишите приведенные ниже схемы уравнений реакций расставьте в них коэффициенты и укажите к какому типу реакций относится каждая их них 1)[tex]H_ <2>… [/tex]O → [tex]H_ <2>+ O_<2>[/tex]2)Pb + [tex]O_<2>[/tex] → PbO

4 Напишите программу для создания изображения. Раскрасьте данное изображе- ние по своему усмотрению. Дополнительные команды для построения графических … примитивов можно найти в справочной системе. ЦВЕТОК ТОЛЬКО.

Через WebMoney

R785211844650
Z210696637574
E368177590409

6. Как реализовать циклический сдвиг?

Автор ARV

18.12.2009 г.

В этом примере значение переменной сдвигается влево на 1 разряд, а значение старшего бита переменной (который будет вытолкнут влево при сдвиге) переносится в младший разряд операцией сдвига вправо на 7 разрядов.

Для сдвига вправо на 1 разряд надо поступить аналогично:

Удобно создать макросы для циклических сдвигов:

Однако, как быть, если надо сдвигать более чем на 1 разряд? Использовать вышеописанный макрос в цикле? Во многих случаях это приведет к неоправданному увеличению объема кода, лучше поступить так:

В этих макросах осуществляется циклический сдвиг x на y разрядов. Важно помнить, что x - байтовая переменная, поэтому y не может принимать значения больше 7.

Читайте также: