Объяснение алгоритма на зеркальное отображение двоичного представления числа

@puulower · Регистрация: 12.09.2020

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

Вот есть такой алгоритм

C

1
2
3

A[i] = ((A[i] >> 1) & 0x55) | ((A[i] << 1) & 0xAA);
A[i] = ((A[i] >> 2) & 0x33) | ((A[i] << 2) & 0xCC);
A[i] = ((A[i] >> 4) & 0x0F) | ((A[i] << 4) & 0xF0);

A[i] - какое то число, не больше одного байта
И можете пояснить почему число сначала смещается на 1 бит вправо и логически умножается на 0x55, и логически складывается с числом смещенным на 1 бит влево и логически умноженным на 0xAA и так до конца? Как это работает?

Байт · 08.11.2020, 14:58

puulower, попробуй расписать константы по битам

@puulower · 08.11.2020, 15:19 **[ТС]**

Байт, ну я так делал, все работает. Но почему используются именно такие числа? Как это объяснить?

@TheCalligrapher · 08.11.2020, 16:47

Ну если алгоритм понятен, то и числа будут понятны. Алгоритм сначала меняет местами четные биты с нечетными. Два числа, используемые при таком обмене - это битовые маски четных и нечётных битов. Затем алгоритм аналогичным образом меняет местами соседние группы из двух битов. Числа - это битовые маски таких групп. И, наконец, алгоритм меняет местами группы по четыре бита. С соответствующими масками.

Verevkin · 08.11.2020, 18:05

есть книжка

Объяснение алгоритма на зеркальное отображение двоичного представления числа

@puulower · 08.11.2020, 18:10 **[ТС]**

Verevkin, спасибо, а можно название книжки?

Добавлено через 1 минуту
TheCalligrapher, понял, спасибо

Verevkin · 08.11.2020, 18:18

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

спасибо, а можно название книжки?

генри уоррен. "алгоритмические трюки для программистов".

Новые блоги и статьи
Что такое хорошо и что такое плохо, вид сбоку. Индивид и общество - грань не нарушения. Hrethgir 18.01.2025 В моей личной жизни и времени, я рассуждаю категорией "хуже-лучше", в том плане, когда меня спросили например - "а зачем ты делаешь свой процессор?", то я ответил - "чтобы сделать свою жизнь лучше". . .	Передача по ссылке или по значению в Java? InfoMaster 18.01.2025 В мире программирования на Java одним из ключевых аспектов, требующих глубокого понимания, является механизм передачи параметров в методы. Этот фундаментальный концепт часто становится источником. . .	Тернарный условный оператор в Python InfoMaster 18.01.2025 В мире программирования существует множество инструментов и конструкций, позволяющих создавать эффективный и лаконичный код. Одним из таких инструментов является тернарный условный оператор, который. . .	Как удалить неотслеживаемые файлы из рабочего дерева Git InfoMaster 18.01.2025 В процессе разработки программного обеспечения с использованием системы контроля версий Git часто возникает необходимость в управлении неотслеживаемыми файлами. Неотслеживаемые файлы (untracked. . .	Что делает код if __name__ == "__main__": в Python InfoMaster 18.01.2025 В мире программирования на Python существует множество важных концепций, и одной из наиболее интересных является конструкция if __name__ == "__main__". Эта специальная конструкция играет ключевую. . .	Как заставить Git забыть об отслеживаемом файле, добавленном в .gitignore InfoMaster 18.01.2025 В мире разработки программного обеспечения система контроля версий Git стала неотъемлемой частью рабочего процесса, позволяя эффективно отслеживать изменения в коде и управлять ими. Однако. . .
Что означает use strict в JavaScript и для чего используется InfoMaster 18.01.2025 В мире современной веб-разработки JavaScript играет ключевую роль как один из основных языков программирования. По мере его эволюции возникла необходимость в механизмах, которые помогли бы. . .	Как работать со скрытыми (hidden) элементами в jQuery InfoMaster 18.01.2025 В современной веб-разработке управление видимостью элементов на странице является одним из ключевых аспектов создания интерактивных пользовательских интерфейсов. jQuery предоставляет мощный набор. . .	Как переключаться между ветками (Branch) с помощью checkout в Git InfoMaster 18.01.2025 Ветки в Git являются одной из ключевых концепций для управления версионностью кода, позволяя разработчикам эффективно работать в команде и параллельно развивать программные проекты. Каждый новый. . .	Что такое стек и куча, чем они отличаются и где находятся InfoMaster 18.01.2025 Понимание основных концепций памяти в программировании В мире современного программирования эффективное управление памятью играет ключевую роль в создании производительных и надежных приложений. . . .	Как использовать комментарии в JSON InfoMaster 18.01.2025 JSON (JavaScript Object Notation) представляет собой легкий и широко используемый формат обмена данными, который стал стандартом де-факто для веб-приложений и программных интерфейсов. При работе с. . .	Как заставить git pull перезаписать локальные файлы в Git InfoMaster 18.01.2025 Проблема перезаписи локальных файлов в Git При работе с системой контроля версий Git разработчики часто сталкиваются с ситуацией, когда необходимо синхронизировать локальный репозиторий с. . .

Объяснение алгоритма на зеркальное отображение двоичного представления числа

Решение

Решение

Байт Диссидент 27710 / 17328 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	08.11.2020, 14:58	2
	puulower, попробуй расписать константы по битам 0

@puulower 5 / 5 / 0 Регистрация: 12.09.2020 Сообщений: 21
	08.11.2020, 15:19 [ТС]	3
	Байт, ну я так делал, все работает. Но почему используются именно такие числа? Как это объяснить? 0

@TheCalligrapher Вездепух 12805 / 6679 / 1798 Регистрация: 18.10.2014 Сообщений: 16,910
	08.11.2020, 16:47	4
	Сообщение было отмечено puulower как решение Решение Ну если алгоритм понятен, то и числа будут понятны. Алгоритм сначала меняет местами четные биты с нечетными. Два числа, используемые при таком обмене - это битовые маски четных и нечётных битов. Затем алгоритм аналогичным образом меняет местами соседние группы из двух битов. Числа - это битовые маски таких групп. И, наконец, алгоритм меняет местами группы по четыре бита. С соответствующими масками. 1

Verevkin Злостный нарушитель 9682 / 5243 / 1197 Регистрация: 12.03.2015 Сообщений: 24,708
	08.11.2020, 18:05	5
	Сообщение было отмечено puulower как решение Решение есть книжка 1

@puulower 5 / 5 / 0 Регистрация: 12.09.2020 Сообщений: 21
	08.11.2020, 18:10 [ТС]	6
	Verevkin, спасибо, а можно название книжки? Добавлено через 1 минуту TheCalligrapher, понял, спасибо 0

Verevkin Злостный нарушитель 9682 / 5243 / 1197 Регистрация: 12.03.2015 Сообщений: 24,708
	08.11.2020, 18:18	7
	Сообщение от puulower спасибо, а можно название книжки? генри уоррен. "алгоритмические трюки для программистов". 1