Q:

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 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.
For better understanding, question statement is here also.
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.
My code
Time Complexity :- O(N^2), (Inefficient one, didn't accpted in the competition)
#include<iostream>

using namespace std;

long long int input[100001];

main() {
    int T;
    int N;
    long long int val;
    long long int temp = 0;
    long long int answer = 0;
    cin >> T;

    while(T--) {
        cin >> N;
        for(int i = 0; i < N; i++) {
            cin >> val;
            temp = temp^val;
            answer += temp;
            input[i] = temp;
        }

        for( int i = 0; i < N; i++ ) {
            for( int j = i+1; j < N; j++ ) {
                answer += input[i]^input[j];
            }
        }
        cout << answer << endl;
        answer = 0;
        temp = 0;
    }
    return 0;
}

Question:-
I saw the best solution of this problem on this link
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;
        }

Thanks in advance. Looking for your kind reply.

A:

I think you left out some very important details:
int A[MAXN];// the arrays contain int values
//xor all the elements of the array as you read them
for (int i=1; i<=N; i++) {
    scanf("%d", &A[i]);
    A[i]^=A[i-1];
}

After reading the inputs you will end up with:
A[0] = A[0]
A[1] = A[1]^A[0]
...
A[N] = A[N]^A[N-1]^...^A[0]

This is O(N) an you get it for free basically since you have to read the input anyway.
This takes care or the XOR part. Now you are left with only the SUM part of the problem.
You have N int numbers (32bit), here is where the part you showed comes in:
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;
        }

For each bit you go through the array and count the number of 1 and add them to the final result.
This part is O(30*N) which is still linear time so O(N). which is better than O(N^2).
Hope this sheds some light on the matter.

A:

Think of the numbers arranged in a Nx32 matrix, where each row represents a number in array and each column represents i'th bits of all the numbers. Now, effects of XOR operation are confined within a column. Therefore, we can separate each column, calculate the XOR-sum for that column and add it to the result.
I have separated a column. How to calculate XOR-sum within this column?
For this purpose, we count the number of 1 in this column. Let c denote the number of 1 in a column. Then, number of 0 will be N - c. To produce 1 in column result (0s have no effect on final result), for each 1 from c, we can take a 0 from N - c, or take no 0 at all. Therefore, there are N - c + 1 ways for each 1 to produce 1 after XOR operation. As there are c 1s, Total number of 1 after XOR operation is c * (N - c + 1).
Each column contributes differently to the final result with respect to there position i. Therefore, multiply column-result with 2^i (1 << i) and add this to final result.

for (int i=0, p=1; i<30; i++, p<<=1)
This loop separates the columns. It also makes p = 1 << i.
if (A[j]&p) c++;
This line counts number of 1 in a column.
ret+=(long long)c*(N-c+1)*p;
This elevates the column-result with respect to column position and add this to final result. Remember that, p = 1 << i (= 2^i).

CONFESSION: I only explained what is done in the code. I have no proof that this will cover all the sub-arrays.

