Задача
Для заданного целого $x$ найти количество таких $a$, удовлетворяющих условию:
- $ a $ xor $x > x $
- $ 0 < a < x $
где $a$ и $x$ — целые, xor — битовый XOR оператор.
Имеются $q$ запросов, каждый из которых содержит целое число $x$. Для каждого запроса выведите общее количество значений $a$, удовлетворяющих условиям выше.
Входные данные
Первая строка содержит число запросов $q$ $(1 \leqslant q \leqslant 10^5)$. Каждая из следующих $q$ строк содержит значение $x$ $(1 \leqslant x \leqslant 10^{10})$.
Выходные данные
Для каждого теста выведите в отдельной строке количество значений $a$, удовлетворяющих приведенным условиям.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 2 2 10 |
1 5 |
| 2 | 3 13 3 16 |
2 0 15 |
| 3 | 5 1 7 4294967295 42 451 |
0 0 0 21 60 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int main() { long q, x, res, two; cin >> q; for(long i = 0; i < q; ++ i){ cin >> x; res = 0; two = 1; // two = 2^0 while(x > 0){ if(x % 2 == 0) // проверяем равен ли бит нулю res += two; x >>= 1; // двигаемся к следующему биту two <<= 1; // увеличиваем степень двойки } cout << res << endl; } return 0; } |
Решение
XOR выдаёт число, биты которого равны $1$, когда лишь у одного из чисел соответствующий бит равен $1$. Числа большие чем $x$ получаем лишь тогда, когда $2^{k}\leqslant a<2^{k+1}$, где $k$- номер бита числа $x$, который равен нулю. Таких $a$ существует $2^k$ штук для каждого такого бита.