Given two arrays A and B each of length N.
   
Find the value \sum_{i=1}^N\sum_{j=1}^N \max(A_{i}\oplus B_{j},A_{i}\& B_{j}).  
Here \oplus and \& denote the [bitwise XOR operation] and [bitwise AND operation] respectively.

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

- The first line of input contains a single integer T - the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N - the length of arrays A and B.
- The second line of each test case contains N space-separated integers A_{1},A_{2},…,A_{N} representing the array A.
- The third line of each test case contains N space-separated integers B_{1},B_{2},…,B_{N} representing the array B.

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

For each test case, output the value \sum_{i=1}^N\sum_{j=1}^N \max(A_{i}\oplus B_{j},A_{i}\& B_{j}).

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i}, B_{i} < 2^{20}$
- Sum of $N$ does not exceed $2\cdot 10^{5}$ over all test cases.

----- Sample Input 1 ------ 
3
2
3 4
1 2
1
0
0
3
2 4 3
1 2 1
----- Sample Output 1 ------ 
15
0
30
----- explanation 1 ------ 
- Test Case $1$: For the given arrays, the value is: $\max(3\oplus 1,3\& 1) + \max(3\oplus 2,3\& 2) + \max(4\oplus 1,4\& 1) + \max(4\oplus 2,4\& 2) = 2 + 2 + 5 + 6 = 15$.

- Test Case $2$: For the given arrays, the value is: $\max(0\oplus 0,0\& 0) = 0$.

- Test Case $3$: For the given arrays, the value is: $\max(2\oplus 1,2\& 1) + \max(2\oplus 2,2\& 2) + \max(2\oplus 1,2\& 1) + \max(4\oplus 1,4\& 1) + \max(4\oplus 2,4\& 2) + \max(4\oplus 1,4\& 1) + \max(3\oplus 1,3\& 1) + \max(3\oplus 2,3\& 2) + \max(3\oplus 1,3\& 1)$  
$= 3 + 2 + 3 + 5 + 6 + 5 + 2 + 2 + 2 = 30$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics


Solutions:
from math import log2

def debug_matrix(a):
	for row in a:
		print(row)
	print()

def debug_list(a):
	print(a)
	print()
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = [0] * 21
	y = [0] * 21
	cx = [0] * 21
	cy = [0] * 21
	result = [0] * 21
	zx = 0
	zy = 0
	for i in range(21):
		x[i] = [0] * 21
		y[i] = [0] * 21
	for num in a:
		if num == 0:
			zx += 1
			continue
		row = int(log2(num))
		cx[row] += 1
		col = 0
		while num > 0:
			if num & 1:
				x[row][col] += 1
			col += 1
			num >>= 1
	for num in b:
		if num == 0:
			zy += 1
			continue
		row = int(log2(num))
		cy[row] += 1
		col = 0
		while num > 0:
			if num % 2 == 1:
				y[row][col] += 1
			col += 1
			num >>= 1
	for i in range(21):
		if cx[i] == 0:
			continue
		for j in range(21):
			if cy[j] == 0:
				continue
			if i == j:
				for k in range(21):
					result[k] += x[i][k] * y[j][k]
			else:
				for k in range(21):
					result[k] += (cx[i] - x[i][k]) * y[j][k]
					result[k] += (cy[j] - y[j][k]) * x[i][k]
	val = 0
	pow = 1
	for i in result:
		val += pow * i
		pow <<= 1
	if zx > 0:
		val += sum(b) * zx
	if zy > 0:
		val += sum(a) * zy
	print(val)


import math
t = int(input())
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = 0
	for i in a:
		s += i
	bits = [0] * 20
	msb = [0] * 20
	t = [[0 for z in range(20)] for j in range(20)]
	for i in range(n):
		if a[i] == 0:
			continue
		k = int(math.log(a[i], 2))
		msb[k] += 1
		for j in range(20):
			bv = a[i] >> j & 1
			bits[j] += bv
			t[k][j] += bv
	res = 0
	for i in range(n):
		if b[i] == 0:
			res += s
			continue
		k = int(math.log(b[i], 2))
		for j in range(20):
			bv = b[i] >> j & 1
			if bv == 0:
				res += (bits[j] - t[k][j]) * (1 << j)
			else:
				res += t[k][j] * (1 << j)
				res += (n - bits[j] - (msb[k] - t[k][j])) * (1 << j)
	print(res)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sum1 = 0
	for i in range(n):
		sum1 += a[i]
	msb = [0] * 20
	bits = [0] * 20
	t = [[0 for i in range(20)] for j in range(20)]
	for i in range(n):
		if a[i] == 0:
			continue
		k = int(math.log(a[i], 2))
		msb[k] += 1
		for j in range(20):
			bv = a[i] >> j & 1
			bits[j] += bv
			t[k][j] += bv
	ans = 0
	for i in range(n):
		if b[i] == 0:
			ans += sum1
			continue
		k = int(math.log(b[i], 2))
		for j in range(20):
			bv = b[i] >> j & 1
			if bv == 0:
				ans = ans + (bits[j] - t[k][j]) * (1 << j)
			else:
				ans = ans + t[k][j] * (1 << j)
				ans = ans + (n - bits[j] - (msb[k] - t[k][j])) * (1 << j)
	print(ans)


import sys
import math

def List():
	return list(map(int, sys.stdin.readline().split()))

def Ints():
	return map(int, sys.stdi.readline().split())

def Strs():
	return map(sys.stdin.readline().strip())

def Op(s):
	sys.stdout.write(s + '\n')

def Int():
	return int(sys.stdin.readline())

def Str():
	return sys.stdin.readline().strip()

def NList(n, l):
	return [n for i in range(l)]

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
for _ in range(Int()):
	n = Int()
	l1 = List()
	l2 = List()
	s = sum(l1)
	msb = NList(0, 20)
	bits = NList(0, 20)
	sets = [NList(0, 20) for i in range(20)]
	res = 0
	for i in range(n):
		if l1[i] == 0:
			continue
		k = int(math.log2(l1[i]))
		msb[k] += 1
		for j in range(20):
			if l1[i] >> j & 1 == 1:
				bits[j] += 1
				sets[k][j] += 1
	for i in range(n):
		if l2[i] == 0:
			res += s
		else:
			msbb = int(math.log2(l2[i]))
			for j in range(20):
				if l2[i] >> j & 1:
					res += sets[msbb][j] * (1 << j)
					res += (n - bits[j] - (msb[msbb] - sets[msbb][j])) * (1 << j)
				else:
					res += (bits[j] - sets[msbb][j]) * (1 << j)
	Op(str(res))


import sys
input = sys.stdin.readline
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	setbit = [0 for i in range(20)]
	msbbit = [0 for i in range(20)]
	mat = [[0 for i in range(20)] for j in range(20)]
	tot = 0
	for i in range(n):
		tot += a[i]
		k = -1
		for j in range(20):
			if a[i] & 1 << j != 0:
				setbit[j] += 1
				k = j
		if k != -1:
			msbbit[k] += 1
			for j in range(20):
				if a[i] & 1 << j != 0:
					mat[k][j] += 1
	ans = 0
	for i in range(n):
		k = -1
		for j in range(20):
			if b[i] & 1 << j != 0:
				k = j
		if k == -1:
			ans += tot
			continue
		for j in range(20):
			if b[i] & 1 << j:
				ans += (1 << j) * mat[k][j]
				ans += (1 << j) * (n - msbbit[k] - (setbit[j] - mat[k][j]))
			else:
				ans += (1 << j) * (setbit[j] - mat[k][j])
	sys.stdout.write(str(ans) + '\n')


def get_msb(n):
	ans = -1
	for j in range(21):
		if 1 << j & n:
			ans = j
	return ans
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	msb = [0] * 21
	bits = [0] * 21
	bit_table = [[0] * 21 for j in range(21)]
	s = 0
	for i in range(N):
		a = A[i]
		s += a
		k = get_msb(a)
		if k != -1:
			msb[k] += 1
			for j in range(k + 1):
				if 1 << j & a:
					bits[j] += 1
					bit_table[k][j] += 1
	res = 0
	for i in range(N):
		if B[i] == 0:
			res += s
		else:
			k = get_msb(B[i])
			for j in range(21):
				if 1 << j & B[i]:
					res += (1 << j) * bit_table[k][j]
					res += (1 << j) * (N - bits[j] - msb[k] + bit_table[k][j])
				else:
					res += (1 << j) * (bits[j] - bit_table[k][j])
	print(res)