Циклический сдвиг битов в байте влево или вправо

@Дима_Кирсанов · Регистрация: 08.10.2010

Студворк — интернет-сервис помощи студентам

Кто-нибудь пробовал реализовать такую задачу на С++. Если да, то какой алгоритм?
Например, если 32 << 10, то в результате должны получить 128.

Читаю Уоррен Генри - Алгоритмические трюки для программистов - 2014, он пишет (screenshot во вложении).
Используем формулу для циклического сдвига влево на n разрядов: y <- (x<<n)|(x>>(32-n)).
В результате получаем: y <- (32 << 10) | (32 >> (32-10))
y <- (32 << 10) | (32 >> 22)
y <- 32768 | 0
y = 32768
Результаты явно отличатся друг от друга. Или может быть я не правильно считаю?

@nmcf · 28.09.2016, 15:25

Сообщение от Дима_Кирсанов

Например, если 32 << 10, то в результате должны получить 128

Как это? У тебя размер целого какой?

@Дима_Кирсанов · 28.09.2016, 15:37 **[ТС]**

Сообщение от nmcf

Как это? У тебя размер целого какой?

Пока не знаю. В числе должно быть 8 разрядов. 32 = 00100000.

Сообщение от nmcf

Например, если 32 << 10, то в результате должны получить 128

Не веришь? А ты сам попробуй переставить единицу 10 раз влево с циклическим переходом.

@obivan · 28.09.2016, 15:51

Дима_Кирсанов, чтобы сдвиги проверить можно так делать
32 << 10 это эквивалент 32 * 2¹⁰, естественно при сдвиге вправо деление на два в степени сдвига

@Дима_Кирсанов · 28.09.2016, 16:13 **[ТС]**

Сообщение от obivan

чтобы сдвиги проверить можно так делать
32 << 10 это эквивалент 32 * 210, естественно при сдвиге вправо деление на два в степени сдвига

Я это все понимаю. Но тогда что имел ввиду У.Генри под словом циклический?

@castaway · 28.09.2016, 16:14

Тут нужно брать остаток от деления на 8 от n, а уже потом подставлять в формулу.

Добавлено через 22 секунды
Дима_Кирсанов, покажи свою программу.

@obivan · 28.09.2016, 16:45

Дима_Кирсанов, в асcемблере есть циклический сдвиг и арифмитический
пример циклического сдвига на 1
исходное число 1001 --- после сдвига 0011

пример арифмитического сдвига на 1
исходное число 1001 --- после сдвига 0010

я думаю речь об этом

Добавлено через 4 минуты

Сообщение от Дима_Кирсанов

если 32 << 10, то в результате должны получить 128

а насчет этого с каких таких делов 32 * 2¹⁰ = 128 ?

Добавлено через 2 минуты
Циклический сдвиг подразумевает то что самое крайнее левое число запишется в начало, а все остальное сдвинет позицию на +1

@castaway · 28.09.2016, 16:45

Сообщение от obivan

с каких таких делов 32 * 2¹⁰ = 128 ?

Да с простых. 10 % 8 == 2. 32 << 2 == 128.

@obivan · 28.09.2016, 16:50

Сообщение от castaway

Да с простых. 10 % 8

Тогда вопрос к чему это ? Вы подразумеваете ограничение вместимости числа в 1 байт ? Или я что-то не догоняю

Добавлено через 1 минуту
Аааа все я понял, это нам надо было получить 128, все вопрос отпал

@castaway · 28.09.2016, 16:51

Сообщение от obivan

Тогда вопрос к чему это ? Вы подразумеваете ограничение вместимости числа в 1 байт ? Или я что-то не догоняю

Сдвиг циклический. У ТС размер сдвигаемого числа равен восьми битам. Вроде всё просто, чего вы не догоняете?

@obivan · 28.09.2016, 16:52

Сообщение от castaway

У ТС размер сдвигаемого числа равен восьми битам

поздно понял

@Дима_Кирсанов · 28.09.2016, 19:05 **[ТС]**

Сообщение от castaway

Тут нужно брать остаток от деления на 8 от n, а уже потом подставлять в формулу

Это что - подгонка под ответ?
А что будет, когда n < 8 или n >= 11?

@castaway · 28.09.2016, 19:27

Сообщение от Дима_Кирсанов

Это что - подгонка под ответ?

Что значит "подгонка под ответ"?

Сообщение от Дима_Кирсанов

А что будет, когда n < 8 или n >= 11?

В обоих случаях будет правильный результат.

Похоже вы - единственный кто "недогнал" как это работает.

@Дима_Кирсанов · 28.09.2016, 20:44 **[ТС]**

Сообщение от castaway

Похоже вы - единственный кто "недогнал" как это работает.

может быть

Сообщение от castaway

Сообщение от Дима_Кирсанов
А что будет, когда n < 8 или n >= 11?
В обоих случаях будет правильный результат.

Сообщение от castaway

Тут нужно брать остаток от деления на 8 от n, а уже потом подставлять в формулу.

Считаю: y <- (x<<n)|(x>>(32-n)), для x=32 и n=7
y <- (32<<(7%8))|(32>>(32-(7%8)))
y <- (32<<7)|(32>>25)
y <- 4096|0
y = 4096

y <- (x<<n)|(x>>(32-n)), для x=32 и n=11
y <- (32<<(11%8))|(32>>(32-(11%8)))
y <- (32<<3)|(32>>29)
y <- 256|0
y = 256

Сообщение от castaway

Добавлено через 22 секунды
Дима_Кирсанов, покажи свою программу.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
 
int main()
{
  //y <- (x<<n)|(x>>(32-n))
  int x = 32;
  int n = 7;
  int res = (x << (n%8))|(x >> (32 -(n%8)));
  cout << res << endl;
  return 0;
}

не знаю что тут еще добавить

@castaway · 28.09.2016, 20:54

Сообщение от Дима_Кирсанов

В числе должно быть 8 разрядов.

Дима_Кирсанов, ты как-нибудь там определись, 8 разрядов у тебя или 32...

@Дима_Кирсанов · 28.09.2016, 21:14 **[ТС]**

Сообщение от castaway

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

8 разрядов. Но как делать циклический сдвиг не понятно

@nmcf · 28.09.2016, 21:15

Тогда char, а не int используй. И в тех формулах из книжки 32 замени на 8.

@castaway · 28.09.2016, 21:20

Сообщение от Дима_Кирсанов

8 разрядов

А тогда какого хрена ты в своих вычислениях используешь 32?

Сообщение от Дима_Кирсанов

Например, если 32 << 10, то в результате должны получить 128.

Тут ты считаешь для 8-и разрядов, а в изображении из первого сообщения формула для 32-х разрядов.

@Дима_Кирсанов · 28.09.2016, 21:34 **[ТС]**

Сообщение от nmcf

И в тех формулах из книжки 32 замени на 8.

Получается так: y <- (x<<n)|(x>>(8-n))

Сообщение от nmcf

Тогда char, а не int используй.

Вот тут уже сложнее:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <fstream>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
 
int main()
{
  //y <- (x<<n)|(x>>(8-n))
  char x = '3';
  char n = '7';
  char res = (x << n)|(x >> (8 - n));
  cout << res << endl;
  return 0;
}

@nmcf · 28.09.2016, 21:55

Зачем символы-то присвоил? Обычные числа используй.
И n можно оставить int, это же просто показатель.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@Дима_Кирсанов 5 / 5 / 7 Регистрация: 08.10.2010 Сообщений: 228

	Циклический сдвиг битов в байте влево или вправо 28.09.2016, 15:20. Показов 10381. Ответов 19 Метки нет (Все метки) Кто-нибудь пробовал реализовать такую задачу на С++. Если да, то какой алгоритм? Например, если 32 << 10, то в результате должны получить 128. Читаю Уоррен Генри - Алгоритмические трюки для программистов - 2014, он пишет (screenshot во вложении). Используем формулу для циклического сдвига влево на n разрядов: y <- (x<<n)\|(x>>(32-n)). В результате получаем: y <- (32 << 10) \| (32 >> (32-10)) y <- (32 << 10) \| (32 >> 22) y <- 32768 \| 0 y = 32768 Результаты явно отличатся друг от друга. Или может быть я не правильно считаю? Миниатюры 0

@obivan Падаван С++ 447 / 261 / 89 Регистрация: 11.11.2014 Сообщений: 916
	28.09.2016, 15:51
	Дима_Кирсанов, чтобы сдвиги проверить можно так делать 32 << 10 это эквивалент 32 * 2¹⁰, естественно при сдвиге вправо деление на два в степени сдвига 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	28.09.2016, 16:14
	Тут нужно брать остаток от деления на 8 от `n`, а уже потом подставлять в формулу. Добавлено через 22 секунды Дима_Кирсанов, покажи свою программу. 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	28.09.2016, 21:15
	Тогда char, а не int используй. И в тех формулах из книжки 32 замени на 8. 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	28.09.2016, 21:55
	Зачем символы-то присвоил? Обычные числа используй. И n можно оставить int, это же просто показатель. 0