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

@Дима_Кирсанов · Регистрация: 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, это же просто показатель.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

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

	Циклический сдвиг битов в байте влево или вправо 28.09.2016, 15:20. Показов 10300. Ответов 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