UniLecs #163. Побитовая арифметика - 2

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

Необходимо определить наибольшую разность между двумя числами, которые можно получить в результате этих перестановок.

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

Вывод: разность наибольшего и наименьшего числа.

Пример: N = 5 (101)

110 - 011 = 6 - 3 = 3

Answer: 3

Идея: для начала нужно перевести число в двоичную систему и посчитать общее количество бит, а также количество единичных битов в представлении числа. А дальше все просто: нам нужно получить наибольшее и наименьшее число путем перестановки единичных битов. Очевидно, что наибольшее число получится, если все единичные биты переставить влево, а нулевые - вправо. Наименьшее число - наооборот: все единичные биты влево, а нулевые вправо. Ответом будет разность полученных чисел.

Реализация:

https://gist.github.com/unilecs/61dbd8b7bd6f6c54d24f040bb5f08d6d

Play-test: https://dotnetfiddle.net/QX84BK