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&lt;30; i++, p&lt;&lt;=1) {
    int c=0;
    for (int j=0; j&lt;=N; j++) {
        if (A[j]&amp;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\&amp; p \ne 0$ then increment $c$. ($\&amp;$ is bitwise and.)

Add $c \times (N-c+1) \times p$ to $r$
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.