Задачи
March 12

Наибольшая разница в побитовом представлении

Задача: Дано натуральное число N. Разрешено бесконечное количество раз проводить перестановку значащих бит заданного числа, получая таким образом новые числа.

Определите какую наибольшую разность полученных двух чисел можно получить в результате таких этих операций?

Входные данные: N - натуральное число от 1 до 10^9.

Пример:

N = 19
Output: 21
Пояснение: 19 - 10011 в двоичном представлении, содержит 3 единицы и 5 бит. Очевидно, что наименьшим числом будет 00111 - 7, а наибольшим 11100 - 28. Тогда разница будет 28 - 7 = 21.

Разбор

Алгоритм будет следующим:

  1. Переведем число в двоичную систему и посчитаем общее кол-во бит и кол-во единичных битов в исходном числе.
  2. Определяем наибольшее и наименьшее число с помощью перестановки единичных битов числа.
    2.1. Наибольшее число получаем, когда все единичные биты переставляем влево, а нулевые вправо.
    2.2. Наименьшее число получаем, когда все единичные биты переставляем вправо, а нулеыве влево.
  3. Выводим разность этих чисел.


Для определения наибольшего и наименьшего числа используем операцию побитого сдвига.
То есть, единичный бит сдвигаем K раз, где K - количество единичных битов исходного числа и получаем наименьшее число.
min = (1 << K) - 1

Сдвигаем единичные биты влево на кол-во нулевых битов исходного числа и получаем наибольшее число.
max = min << zeroNum

Реализация

Play-test

https://dotnetfiddle.net/baNu4q