Запишите 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
Примеры
Ввод:
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.
Ввод:
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. Следуйте условию и ограничениям выше.