Chef has two non negative integers N and X. He now wants to find the number of integers K such that 0 ≤ K < N, and (N \oplus K) \And X = 0. 

Note that \oplus denotes the bitwise XOR operator and \And denotes the bitwise AND operator.

Help Chef in finding the total required count.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input containing N and X denoting the two integers as described in the statement.

------ Output Format ------ 

For each test case, output the total number of integers K which satisfy the requirements mentioned.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N, X ≤ 2^{30} - 1$

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
3
4 5
8 4
1 2

----- Sample Output 1 ------ 
0
4
1

----- explanation 1 ------ 
Testcase 1: $N = 4, X = 5$. So we need to find the number of $K$, which satisfy $0 ≤ K 
< 4$, and $(4 \oplus K) \And 5 = 0$.

- $(100_{2} \oplus 000_{2}) \And 101_{2} = 100_{2} \And 101_{2} = 100_{2} \neq 0$
- $(100_{2} \oplus 001_{2}) \And 101_{2} = 101_{2} \And 101_{2} = 101_{2} \neq 0$
- $(100_{2} \oplus 010_{2}) \And 101_{2} = 110_{2} \And 101_{2} = 100_{2} \neq 0$
- $(100_{2} \oplus 011_{2}) \And 101_{2} = 111_{2} \And 101_{2} = 101_{2} \neq 0$

So, we have looked at all values of $K$, and found no value which satisfies the requirements. So the answer is $0$.

Source: codechef | Difficulty: HARD
Tags: Bit manipulation

Mathematics


Solutions:
for _ in range(int(input())):
	(m, ans) = (1, 0)
	(N, X) = list(map(int, input().split()))
	i = 0
	while True:
		if X & 1 << i:
			i += 1
			continue
		if N & 1 << i:
			ans += m
		m = 2 * m
		if 1 << i > max(N, X):
			break
		i += 1
	print(ans)


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)


def prod(arr):
	res = 1
	for el in arr:
		res *= el
	return res

def to_binary(n, l):
	if n == 0:
		return [0] * l
	res = []
	while n > 0 or len(res) < l:
		b = n % 2
		n //= 2
		res.append(b)
	return list(reversed(res))

def get_values(n, x):
	bn = to_binary(n, 32)
	bx = to_binary(x, 32)
	arr = []
	for i in range(len(bn)):
		if bx[i] == 0:
			arr.append([0, 1])
		else:
			arr.append([bn[i]])
	return [bn, bx, arr]

def f(bn, bx, arr, start):
	if len(bn) == 0:
		return 0
	for i in range(start, len(bn)):
		if bn[i] == 0:
			continue
		if len(arr[i]) == 2:
			return prod(map(len, arr[i + 1:])) + f(bn, bx, arr, i + 1)
		elif arr[i][0] == 0:
			return prod(map(len, arr[i + 1:]))
		else:
			return f(bn, bx, arr, i + 1)
	return 0

def g(n, x):
	values = get_values(n, x)
	return f(*values, 0)
t = int(input())
for i in range(t):
	(n, x) = [int(el) for el in input().split(' ')]
	print(g(n, x))


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


def fun(n, v1, v2, f, dp):
	if n == -1:
		return 1
	if dp[n][f] != -1:
		return dp[n][f]
	if f == 0:
		if 1 << n & v1 and 1 << n & v2:
			ans = fun(n - 1, v1, v2, 0, dp)
		elif 1 << n & v1 and 1 << n & v2 == 0:
			ans = fun(n - 1, v1, v2, 0, dp) + fun(n - 1, v1, v2, 1, dp)
		elif 1 << n & v1 == 0 and 1 << n & v2:
			ans = fun(n - 1, v1, v2, 0, dp)
		else:
			ans = fun(n - 1, v1, v2, 0, dp)
	elif 1 << n & v1 and 1 << n & v2:
		ans = fun(n - 1, v1, v2, 1, dp)
	elif 1 << n & v1 and 1 << n & v2 == 0:
		ans = 2 * fun(n - 1, v1, v2, 1, dp)
	elif 1 << n & v1 == 0 and 1 << n & v2:
		ans = fun(n - 1, v1, v2, 1, dp)
	else:
		ans = 2 * fun(n - 1, v1, v2, 1, dp)
	dp[n][f] = ans
	return ans
for _ in range(int(input())):
	f = -1
	(x, k) = map(int, input().split())
	for i in range(30, -1, -1):
		if 1 << i & x:
			f = i
			break
	dp = [[-1] * 2 for i in range(31)]
	ans = fun(f, x, k, 0, dp)
	print(ans - 1)


for _ in range(int(input())):
	(n, x) = [int(x) for x in input().split()]
	dp = [[0] * 2 for i in range(31)]
	i = 0
	while n > 0 or x > 0:
		n_r = n % 2
		x_r = x % 2
		if x_r == 0:
			if i == 0:
				dp[i][0] = 2
				dp[i][1] = n_r
			else:
				dp[i][0] = 2 * dp[i - 1][0]
				if n_r == 0:
					dp[i][1] = dp[i - 1][1]
				else:
					dp[i][1] = dp[i - 1][0] + dp[i - 1][1]
		elif i == 0:
			dp[i][0] = 1
			dp[i][1] = 0
		else:
			dp[i][0] = dp[i - 1][0]
			dp[i][1] = dp[i - 1][1]
		n //= 2
		x //= 2
		i += 1
	print(dp[i - 1][1])


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	n1 = 0
	n2 = 0
	x1 = n
	x2 = x
	while x1 > 0:
		n1 += 1
		x1 = x1 >> 1
	while x2 > 0:
		n2 += 1
		x2 = x2 >> 1
	x1 = n
	x2 = x
	ans = 1
	while n1 >= 0:
		if x2 & 1 << n1 > 0:
			ans *= 1
		elif x1 & 1 << n1 > 0:
			ans *= 2
		else:
			ans = ans * 2 - 1
		n1 -= 1
	print(ans - 1)


for _ in range(int(input())):
	dp = [[-1, -1] for i in range(55)]
	(n, x) = list(map(int, input().split()))

	def helper(i, g):
		if i < 0:
			return 1
		if dp[i][g] != -1:
			return dp[i][g]
		ans = 0
		if x >> i & 1:
			ans += helper(i - 1, g)
		elif n >> i & 1:
			ans += helper(i - 1, g)
			ans += helper(i - 1, 0)
		else:
			ans += helper(i - 1, g)
			if g == 0:
				ans += helper(i - 1, g)
		dp[i][g] = ans
		return ans
	print(helper(39, 1) - 1)


def dfs(ind, g):
	if ind < 0:
		return 1
	if dp[ind][g] != -1:
		return dp[ind][g]
	res = 0
	if X >> ind & 1:
		res += dfs(ind - 1, g)
	elif N >> ind & 1:
		res += dfs(ind - 1, g)
		res += dfs(ind - 1, 0)
	else:
		res += dfs(ind - 1, g)
		if g == 0:
			res += dfs(ind - 1, g)
	dp[ind][g] = res
	return dp[ind][g]
T = int(input())
for i in range(T):
	(N, X) = [int(x) for x in input().split()]
	dp = [[-1 for i in range(2)] for j in range(55)]
	print(dfs(39, 1) - 1)


from functools import lru_cache

@lru_cache(None)
def solve(i, ceil):
	if i < 0:
		return 1
	ans = 0
	if X & 1 << i == 0:
		mini = 1 << i
		maxi = (1 << i + 1) - 1
		if ceil <= mini:
			pass
		elif ceil <= maxi:
			ans += solve(i - 1, ceil ^ mini)
		else:
			ans += solve(i - 1, float('inf'))
		mini = 0
		maxi = (1 << i) - 1
		if ceil <= mini:
			pass
		elif ceil <= maxi:
			ans += solve(i - 1, ceil ^ mini)
		else:
			ans += solve(i - 1, float('inf'))
	elif N & 1 << i == 0:
		mini = 0
		maxi = (1 << i) - 1
		if ceil <= mini:
			pass
		elif ceil <= maxi:
			ans += solve(i - 1, ceil ^ mini)
		else:
			ans += solve(i - 1, float('inf'))
	else:
		mini = 1 << i
		maxi = (1 << i + 1) - 1
		if ceil <= mini:
			pass
		elif ceil <= maxi:
			ans += solve(i - 1, ceil ^ mini)
		else:
			ans += solve(i - 1, float('inf'))
	return ans
for _ in range(int(input())):
	(N, X) = map(int, input().split())
	solve.cache_clear()
	print(solve(31, N))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	y = len(bin(n)) - 2
	na = [0 for i in range(y)]
	xa = [0 for i in range(y)]
	arr = [0 for i in range(y)]
	val = 1
	for i in range(y):
		if val & x:
			xa[i] = 1
		if val & n:
			na[i] = 1
		val *= 2
	ans = 1
	for i in range(y - 1, -1, -1):
		if xa[i] == 0 and na[i] == 1:
			ans *= 2
		elif xa[i] == 0 and na[i] == 0:
			ans *= 2
			ans -= 1
	print(ans - 1)