Read problems statements in Russian here 
Polo, the Penguin, likes the XOR operation. Please read NOTE if you are not familiar with XOR operation. 
XOR-sum of a list of numbers is the result of XOR-ing all of them. XOR-sum of (A[1] XOR A[2] XOR ... XOR A[N]) is defined as A[1] XOR (A[2] XOR (A[3] XOR ( ... XOR A[N]))).
He has an array A consisting of N integers. Index in the array are numbered from 1 to N, inclusive. Let us denote by F(L, R), the XOR-sum of all integers in the array A whose indices lie from L to R, inclusive, i.e. F(L, R) = A[L] XOR A[L+1] XOR ... XOR A[R]. Your task is to find the total sum of XOR-sums F(L, R) over all L and R such that 1 ≤ L ≤ R ≤ N.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of A. The second line contains N space-separated integers A[1], A[2], ..., A[N].

------ Output ------ 

For each test case, output a single line containing the total sum to the corresponding test case.

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

$1 ≤ T ≤ 100,000$
$1 ≤ N ≤ 100,000$
$0 ≤ A[i] ≤ 1,000,000,000 (10^{9})$
$The total sum of all N over all test cases will not exceed 100,000.$

------ Example ------ 

Input:
1
2
1 2

Output:
6

------ Explanation ------ 

Example case 1. F(1, 1) = A[1] = 1, F(2, 2) = A[2] = 2 and F(1, 2) = A[1] XOR A[2] = 1 XOR 2 = 3. Hence the answer is 1 + 2 + 3 = 6.

------ NOTE ------ 

XOR operation is a bitwise "Exclusive OR" operation performed on two integers in binary representation. First, the shorter number is prepended with leading zeroes until the numbers have equal size in binary. Then the resulting number (also in binary) contains 0 in all positions where the corresponding bits coincide, and 1 on the rest of the positions.
For example, 3 XOR 5 = 011_{2} XOR 101_{2} = 110_{2} = 6.

Source: codechef | Difficulty: HARD
Tags: Bit manipulation

Mathematics


Solutions:
def solver():
	T = int(input())
	for _ in range(T):
		ans = 0
		n = int(input())
		arr = [int(x) for x in input().split()]
		for i in range(1, len(arr)):
			arr[i] = arr[i] ^ arr[i - 1]
		for i in range(32, -1, -1):
			t = 1 << i
			cnt = 0
			for e in arr:
				if e & t != 0:
					cnt += 1
			ans += cnt * (n - cnt + 1) * t
		print(ans)
solver()


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	s = s.split()
	li = []
	for i in s:
		li += [int(i)]
	res = 0
	for i in range(0, 31):
		s = 0
		ones = 0
		e = 0
		o = 0
		zero = 0
		for j in li:
			if 1 << i & j == 0:
				if ones % 2 == 0:
					s += e
				else:
					s += o
				zero += 1
			else:
				ones += 1
				if ones % 2 == 0:
					e += zero + 1
					s += e - 1
				else:
					o += zero + 1
					s += o - 1
				zero = 0
		res += 2 ** i * s
	res += sum(li)
	print(res)


import sys
data = sys.stdin.read().split()
data.reverse()

def read():
	return int(data.pop())

def readStr():
	return data.pop()
T = read()
res = []
for test in range(T):
	n = read()
	A = [read() for i in range(n)]
	ans = 0
	for b in range(30):
		cnt = 0
		V = []
		sum = [0, 0]
		for a in A:
			if a & 1 << b:
				V.append(cnt + 1)
				sum[len(V) % 2] += cnt + 1
				cnt = 0
			else:
				cnt += 1
		V.append(cnt + 1)
		sum[len(V) % 2] += cnt + 1
		cnt = 0
		for i in range(len(V)):
			s = V[i]
			cnt += s * sum[i % 2]
			sum[(i + 1) % 2] -= s
		ans += cnt * (1 << b)
	res.append(str(ans))
print('\n'.join(res))


import sys

def bin_one(num):
	s = bin(num)[2:]
	return set([len(s) - i - 1 for i in range(len(s)) if s[i] == '1'])
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	A = [int(i) for i in sys.stdin.readline().rstrip().split()]
	max_bin_len = len(bin(max(A))[2:])
	C = [0] * max_bin_len
	S = 0
	total_sum = 0
	for i in range(0, n):
		S ^= A[i]
		index_ones = bin_one(S)
		for j in range(len(C)):
			if j in index_ones:
				total_sum += (i + 1 - C[j]) * pow(2, j)
				C[j] += 1
			else:
				total_sum += C[j] * pow(2, j)
	print(total_sum)


for _ in range(int(input())):
	n = int(input())
	arr = [int(c) for c in input().split()]
	s = []
	xorval = 0
	for i in arr:
		xorval ^= i
		s.append(xorval)
	count = [0 for i in range(32)]
	ans = sum(s)
	for i in range(32):
		if s[0] & 1 << i:
			count[i] += 1
	for j in range(1, len(s)):
		for i in range(32):
			if s[j] & 1 << i:
				ans += (j - count[i]) * 1 << i
			else:
				ans += count[i] * (1 << i)
		for i in range(32):
			if s[j] & 1 << i:
				count[i] += 1
	print(ans)