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

Problem Detail: 

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$

Asked By : devsda

Answered By : Mahmoud A.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18194