Олимпиадный тренинг

Задача . Уравнения математической магии


Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу
Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: a−(a⊕x)−x=0 для заданного a, где знаком  ⊕  обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю 232. Ойра-Ойра быстро нашел x, являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю 232, Кристобаля Хунту интересует количество таких решений x, что 0 ≤ x ≤ 232. Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

Входные данные
В первой строке задано одно целое число a (0 ≤ a ≤ 232−1).

Выходные данные
Выведите одно целое число — количество неотрицательных решений уравнения.

Примечание
Определим операцию побитового ИЛИ (XOR). Пусть даны два целых неотрицательных числа x и y, рассмотрим их двоичные записи (возможно с ведущими нулями): xk...x2x1x0 и yk...y2y1y0. Здесь xi это i-й бит числа x, а yi это i-й бит числа y. Пусть r=x⊕y — результат операции XOR над числами x и y. Тогда двоичной записью r будет rk...r2r1r0, где:
\(r_i = \begin{cases} 1, & \quad \text{если } x_i \neq y_i \\ 0, & \quad \text{если } x_i = y_i \end{cases} \)

В первом примере решениями уравнения являются 0 и 2147483648=231, так как 0−(0⊕0)−0=0−0−0=0 и 0−(0⊕ 2147483648)−2147483648=−4294967296=−232=0 по модулю 232.

Во втором примере решениями уравнения являются 0, 2, 2147483648=231 и 2147483650=231+2.

В третьем примере решениями являются все x, для которых выполнено 0 ≤ x ≤ 232.
 
Примеры
Входные данные Выходные данные
1 0 2
2 2 4
3 4294967295 4294967296

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Python1
Комментарий учителя