Задача №113939. Уравнения математической магии
Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: \(a - (a \oplus x) - x = 0\) для заданого \(a\), где знаком \(\oplus\) обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю \(2^{32}\). Ойра-Ойра быстро нашел \(x\), являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю \(2^{32}\), Кристобаля Хунту интересует количество таких решений \(x\), что \(0 \leq x < 2^{32}\). Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.
В первой строке задано одно целое число \(a\) (\(0 \leq a \leq 2^{32} - 1\)).
Выведите одно целое число — количество неотрицательных решений уравнения.
Определим операцию побитового ИЛИ (XOR). Пусть даны два целых неотрицательных числа \(x\) и \(y\), рассмотрим их двоичные записи (возможно с ведущими нулями): \(x_k \dots x_2 x_1 x_0\) и \(y_k \dots y_2 y_1 y_0\). Здесь \(x_i\) это \(i\)-й бит числа \(x\), а \(y_i\) это \(i\)-й бит числа \(y\). Пусть \(r = x \oplus y\) — результат операции XOR над числами \(x\) и \(y\). Тогда двоичной записью \(r\) будет \(r_k \dots r_2 r_1 r_0\), где:
\(\) r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. \(\)
В первом примере решениями уравнения являются \(0\) и \(2147483648 = 2^{31}\), так как \(0 - (0 \oplus 0) - 0 = 0 - 0 - 0 = 0\) и \(0 - (0 \oplus 2147483648) - 2147483648 = -4294967296 = -2^{32} = 0\) по модулю \(2^{32}\).
Во втором примере решениями уравнения являются \(0\), \(2\), \(2147483648 = 2^{31}\) и \(2147483650 = 2^{31} + 2\).
В третьем примере решениями являются все \(x\), для которых выполнено \(0 \leq x < 2^{32}\).
0
2
2
4
4294967295
4294967296