Все задачи
Средне Решено: 0 Процент решений: 0%

Разворот битов

Запишите младшие width битов числа в обратном порядке.

Чему вы научитесь

  • Получать младший бит с помощью AND 1
  • Собирать число побитово с помощью сдвигов
  • Соблюдать фиксированную разрядность

Условие

Запишите n в двоичном виде ровно width битами, при необходимости дополнив ведущими нулями, а затем прочитайте эти биты в обратном порядке. Для n = 6 и width = 4 число 6 записывается как 0110, в обратном порядке это снова 0110, поэтому результат равен 6. Для width = 8 получаем 00000110, после разворота 01100000, то есть 96. Разворот битов применяется в быстром преобразовании Фурье и в некоторых приёмах хеширования.

Реализуйте reverse_the_bits(n, width).

Входные данные

n: неотрицательное целое число, которое помещается в width битов.

width: сколько битов нужно развернуть.

Выходные данные

Верните значение развёрнутой width-битовой последовательности.

Ограничения

1 ≤ width ≤ 63

0 ≤ n < 2^width

Примеры

Пример 1
Ввод:
n = 6
width = 8

Ожидаемый вывод:
expected = 96
Ввод:
long long n = 6;
long long width = 8;

Ожидаемый вывод:
long long expected = 96;
Ввод:
long n = 6;
long width = 8;

Ожидаемый вывод:
long expected = 96;

Пояснение

6 в 8 битах - это 00000110, после разворота получается 01100000, то есть 96.

Пример 2
Ввод:
n = 1
width = 3

Ожидаемый вывод:
expected = 4
Ввод:
long long n = 1;
long long width = 3;

Ожидаемый вывод:
long long expected = 4;
Ввод:
long n = 1;
long width = 3;

Ожидаемый вывод:
long expected = 4;

Пояснение

1 - это 001, после разворота получается 100, то есть 4.

Как подступиться

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

Подсказка 1

Повторите width раз: возьмите младший бит n, затем сдвиньте n вправо.

Подсказка 2

Перед добавлением только что взятого бита сдвиньте результат влево на один.

Подсказка 3

Ведущие нули n становятся конечными нулями результата, и фиксированное число итераций это учитывает.

Ожидаемая сложность

время O(width), доп. память O(1)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.