# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Akshit Monga

*Tejas Pandey*

**Preparer:***Takuki Kurokawa, Utkarsh Gupta*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

2001

# PREREQUISITES:

Bitwise operations

# PROBLEM:

You are given N and X. Find the number of integers K such that 0 \leq K \lt N and ((N \oplus K) \And X) = 0.

# EXPLANATION

Since this task deals with bitwise operations, it makes sense to look at things bit by bit.

If the binary representation of a number y has a 1 in the i-th position, we say the i-th bit is *set* in y.

Now, we want the bitwise and of N\oplus K with X to be 0. This means that if a bit is set in X, it will be set in K if and only if it is set in N. In other words, if some bit of X is set, there is exactly one choice for such a bit in K.

After this, we apply a classical technique when counting things that must be lexicographically smaller than something else. Iterate over the positions, and fix the one that is the first to be **strictly less**, then we have complete freedom in all following positions.

That is, iterate bits from 30 down to 0. Suppose we are currently at the i-th bit. We will assume that the bits from 30 to (i+1) of both N and K are equal, and the i-th bit of K is strictly less than the i-th bit of N (of course, note that this is only possible when the i-th bit of N is 1, and the i-th bit of X is not 1).

Now, bits 0 to i-1 are totally free (except for the restriction on set bits of X mentioned before), and each of these have 2 choices (can be 0 or 1). So, if there are c such free bits, we add 2^c to the answer.

The final algorithm looks like this:

- Iterate i from 30 down to 0.
- If the i-th bit is either set in X or not set in N, do nothing
- Otherwise, count the number of bits from 0 to i-1 that are not set in X. If this number is c, add 2^c to the answer.

This can be implemented in \mathcal{O}(\log N) by maintaining the running sum of bits that are not set in X; however a more naive implementation in \mathcal{O}(\log^2 N) will still be fast enough.

# TIME COMPLEXITY:

\mathcal{O}(\log N) per test case.

# CODE:

## Setter's code (Python)

```
t=int(input())
for _ in range(t):
n,x=map(int,input().split())
ans=p=0
for i in range(0,30):
if not x&(1<<i):
if n&(1<<i):ans+=(1<<p)
p+=1
print(ans)
```

## Tester's code (C++, tabr)

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, x;
cin >> n >> x;
int ans = 0;
for (int i = 29; i >= 0; i--) {
if (~x & (1 << i)) {
ans *= 2;
if (n & (1 << i)) {
ans += 1;
}
}
}
cout << ans << endl;
}
return 0;
}
```

## Editorialist's code (C++)

```
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, x; cin >> n >> x;
int ans = 0, ct = 31 - __builtin_popcount(x);
for (int bit = 30; bit >= 0; --bit) {
if ((x >> bit) & 1) continue;
--ct;
if ((~n >> bit) & 1) continue;
// Let this be the first bit that is strictly less than n
ans += 1 << ct;
}
cout << ans << '\n';
}
}
```