Наибольшая разница в побитовом представлении
Задача: Дано натуральное число N. Разрешено бесконечное количество раз проводить перестановку значащих бит заданного числа, получая таким образом новые числа.
Определите какую наибольшую разность полученных двух чисел можно получить в результате таких этих операций?
Входные данные: N - натуральное число от 1 до 10^9.
N = 19
Output: 21
Пояснение: 19 - 10011 в двоичном представлении, содержит 3 единицы и 5 бит. Очевидно, что наименьшим числом будет 00111 - 7, а наибольшим 11100 - 28. Тогда разница будет 28 - 7 = 21.
Разбор
- Переведем число в двоичную систему и посчитаем общее кол-во бит и кол-во единичных битов в исходном числе.
- Определяем наибольшее и наименьшее число с помощью перестановки единичных битов числа.
2.1. Наибольшее число получаем, когда все единичные биты переставляем влево, а нулевые вправо.
2.2. Наименьшее число получаем, когда все единичные биты переставляем вправо, а нулеыве влево. - Выводим разность этих чисел.
Для определения наибольшего и наименьшего числа используем операцию побитого сдвига.
То есть, единичный бит сдвигаем K раз, где K - количество единичных битов исходного числа и получаем наименьшее число.min = (1 << K) - 1
Сдвигаем единичные биты влево на кол-во нулевых битов исходного числа и получаем наибольшее число.max = min << zeroNum