Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу
Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: a−(a⊕x)−x=0 для заданного a, где знаком ⊕ обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю 2
32. Ойра-Ойра быстро нашел x, являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю 2
32, Кристобаля Хунту интересует количество таких решений x, что 0 ≤ x ≤ 2
32. Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.
Входные данные
В первой строке задано одно целое число a (0 ≤ a ≤ 2
32−1).
Выходные данные
Выведите одно целое число — количество неотрицательных решений уравнения.
Примечание
Определим операцию побитового ИЛИ (XOR). Пусть даны два целых неотрицательных числа x и y, рассмотрим их двоичные записи (возможно с ведущими нулями): x
k...x
2x
1x
0 и y
k...y
2y
1y
0. Здесь x
i это i-й бит числа x, а y
i это i-й бит числа y. Пусть r=x⊕y — результат операции XOR над числами x и y. Тогда двоичной записью r будет r
k...r
2r
1r
0, где:
\(r_i = \begin{cases} 1, & \quad \text{если } x_i \neq y_i \\ 0, & \quad \text{если } x_i = y_i \end{cases} \)
В первом примере решениями уравнения являются 0 и 2147483648=2
31, так как 0−(0⊕0)−0=0−0−0=0 и 0−(0⊕ 2147483648)−2147483648=−4294967296=−2
32=0 по модулю 2
32.
Во втором примере решениями уравнения являются 0, 2, 2147483648=2
31 и 2147483650=2
31+2.
В третьем примере решениями являются все x, для которых выполнено 0 ≤ x ≤ 2
32.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
0 |
2 |
| 2 |
2 |
4 |
| 3 |
4294967295 |
4294967296 |