e-olymp 7457. Max-Min в двійковій системі счислення

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом $N$ знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

$N=13_{10}$, в двійковій системі числення — $1101_2$, найбільше число $1110_2 = 14_{10}$, найменше число $0111_2 = 7_{10}$. $14−7=7$.

Вхідні дані

В єдиному рядку записане число $N (N<2^{31})$.

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані Вихідні дані
2 1
15 0
86 105
1000 945
40 45

Код програми

 

 

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

  1. За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа $n$.
  2. Створимо функцію $max_number$, яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
  3. Створимо функцію $min_number$, яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
  4. Виведемо на екран різницю підрахованих функціями $max_number$ та $min_number$ значень.