5718. Большая разница

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

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

Вход. Одно натуральное число n (1 ≤ n ≤ 2·10⁹).

Выход. Одно число – искомая "Большая разница".

Пример входа	Пример выхода
19	21

РЕШЕНИЕ

битовые операции

Анализ алгоритма

Вычислим количество бит, а также число единиц в бинарном представлении числа n. Если все единицы числа поставить с правой стороны, а нули слева, то получим наименьшее число. Если все единицы числа поставить с левой стороны, а нули справа, то получим наибольшее. Их разница и будет искомой.

Пример

19₁₀ = 10011₂. Число 19 в бинарном представлении содержит 3 единицы и 5 бит. Наименьшим числом будет 00111₂ = 7₁₀, а наибольшим 11100₂ = 28₁₀. Большая разница равна 28 – 7 = 21.

Реализация алгоритма

Читаем значение n. Подсчитаем количество бит Bits и число единиц Ones в бинарном представлении числа n.

scanf("%d",&n);

Ones = Bits = 0;

while(n)

{

if (n % 2) Ones++;

Bits++;

n /= 2;

}

Вычисляем наименьшее число min.

for(i = 0; i < Ones; i++)

min = 2 * min + 1;

Вычисляем наибольшее число max.

for(max = min; i < Bits; i++)

max *= 2;

Выводим искомую большую разницу.

printf("%d\n",max - min);

Реализация со сдвигами

#include <stdio.h>

int n, Ones, Bits, i;

int min, max;

int main(void)

{

scanf("%d",&n);

Ones = Bits = 0;

while(n)

{

if (n % 2) Ones++;

Bits++;

n /= 2;

}

min = (1 << Ones) - 1;

max = min << (Bits - Ones);

printf("%d\n",max - min);

return 0;

}

Python реализация

n = int(input())

Ones = Bits = 0

while(n > 0) :

if (n % 2 == 1) : Ones += 1

Bits += 1

n //= 2

mn = 0

for i in range(0,Ones) :

mn = 2 * mn + 1

mx = mn

for i in range(Ones,Bits) :

mx *= 2

print(mx - mn)