Задача №113938. Уравнения математической магии
Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: \(a - (a \oplus x) - x = 0\) для заданого \(a\), где знаком \(\oplus\) обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Ойра-Ойра быстро нашел \(x\), являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько существует неотрицательных решений данного уравнения. Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.
Вам предстоит решить задачу для нескольких возможных значений параметра \(a\). В первой строке находится целое число \(t\) (\(1 \le t \le 1000\)) — количество этих значений.
В последующих \(t\) строках находятся значения параметра \(a\), каждое значение — целое число от \(0\) до \(2^{30} - 1\) включительно.
Для каждого значения параметра \(a\) выведите строке одно целое число — количество неотрицательных решений уравнения с данным значением параметра. Ответы выводите в том же порядке, в каком параметры следуют во входных данных.
Можно доказать, что количество решений всегда конечно.
Определим операцию побитового исключительного ИЛИ (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. \(\)
Для первого значения параметра только \(x = 0\) является решением уравнения.
Для второго значения параметра решениями уравнения являются \(x = 0\) и \(x = 2\).
3 0 2 1073741823
1 2 1073741824