Algorithm to add sum of every possible xor-sum sub-array

I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here.

Problem Statement

XOR-sum of a sub-array is to XOR all the numbers of that sub-array. An array is given to you, you have to add all possible such XOR-sub-array.

Example

Input

Array :- 1 2

Output :- 6

Explanation

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.

I found an $O(N^2)$ solution, but it was too inefficient one and wasn't accepted in the competition.

I saw the best solution of this problem on Code Chef. But in this code, I didn't understand below module, please help me to understand that.

for (int i=0, p=1; i<30; i++, p<<=1) {
int c=0;
for (int j=0; j<=N; j++) {
if (A[j]&p) c++;
}
ret+=(long long)c*(N-c+1)*p;
}


In pseudocode:

• Set $r = 0$
• For $i$ from $0$ to $29$, let $p = 2^i$.
• Set $c=0$
• Iterate over the array $A$. For each element $A[j]$:
• If $A[j] \mathbin\& p \ne 0$ then increment $c$. ($\&$ is bitwise and.)
• Add $c \times (N-c+1) \times p$ to $r$
• @D.W. I just want help. I put lots of time on this. At the end, I got stuck. Please help me to put out from here, – devsda Nov 21 '13 at 5:20
• @D.W. If you can, shift this question to SO. – devsda Nov 21 '13 at 5:27
• @devsda There's an answer which explains the algorithm, and it uses mathematical formatting. I don't think this question needs to be migrated, and the answer can't be. If you need help with the code part, ask on Stack Overflow. – Gilles Nov 21 '13 at 12:12
• – Andre Holzner Aug 14 '16 at 14:10

After the first couple of lines the array $A$ contains the XOR of every prefix of the input numbers in binary. So a $1$ bit at position $k$ in $A[j]$ tells us that there are an odd number of input numbers in the range $0...j$ with $1$ at their position $k= \log p$.

For every $i,j$ s.t. $i \leq j$, if the $k$th bit of $A[i-1]$ is $1$ and the same bit in $A[j]$ is $0$ then there are an odd number of $1$s at bit-position $k$ of the input numbers in the range $i...j$. The same conclusion would be true if the $k$th bit was $0$ for $A[i-1]$ and $1$ for $A[j]$. Please observe that these are the only two situations where the number of ones at position $k$ is odd in the range $i...j$.

Therefore the number of pairs $(A^k[i-1],A^k[j])=(0,1)$ or $(1,0)$ is equal to the number of ranges in the input such that their XOR at position $k$ is $1$. Every such range contributes $p=2^k$ to the total sum. In that code, $c$ is the number of ones and $(N-c)$ is the number of zeros at position $k = \log p$. The "$+1$" is to count for the ranges of length one and a $1$ in their $k$th position.

• Then , why i only moves upto 30, Any logic ? – devsda Nov 21 '13 at 5:47
• Can you please explain the whole logic ? How this logic comes in mind, as I am naive. – devsda Nov 21 '13 at 5:58
• It'll help to start with an example of one bit numbers and see what really happens. Then extend it to two bits etc. – Parham Nov 21 '13 at 6:59
• You didn't give my first question's answer. – devsda Nov 21 '13 at 8:49
• ok. Instead of calculating XORs for all possible subarray and then summing them up (which is the naive solution), we count the number of subarrays which $k$th bit of their XOR is 1. This bit adds $2^k$ to the total sum. $c.(N-c)$ is the number of such subarrays. Is it clear now? – Parham Nov 21 '13 at 10:03

Just do the OR operations of all numbers and multiply the answer with power(2,N-1) where N is the length of your array.
For array given in question: 1 OR 2 = 3 Now, 3*(power(2,(2-1))) = 6 which is the answer.
The point here is that, Each set bit of any number occurs exactly in power(2,N-1) sub arrays.

• How does this answer the question? The question asks to understand what's going on in a particular solution. It sounds like you're proposing a different solution. Would you consider editing your answer to make it clearer how it answers the question that was asked? – D.W. Sep 9 '15 at 16:22
• Question line also says that "I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here." – Vedsar Kushwaha Sep 9 '15 at 18:16