Задача
Для заданного целого $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 20 21 |
import java.util.*; class Main{ public static void main (String[] args){ Scanner in = new Scanner(System.in); long q, x, res, two; q = in.nextInt(); for(long i = 0; i < q; ++ i){ x = in.nextLong(); res = 0; two = 1; // two = 2^0 while(x > 0){ if(x % 2 == 0) // check if the last bit is equal to zero res += two; x >>= 1; // moving to the next bit two <<= 1; // same as two *= 2 } System.out.println(res); } } } |
Решение
XOR выдаёт число, биты которого равны $1$, когда лишь у одного из чисел соответствующий бит равен $1$. Числа большие чем $x$ получаем лишь тогда, когда $2^{k}\leqslant a<2^{k+1}$, где $k$- номер бита числа $x$, который равен нулю. Таких $a$ существует $2^k$ штук для каждого такого бита.