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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

As far as I can tell, the code at the link that you provided is not the best solution, nor even a working solution. The code which you copied from that link seems to make sense, but previous to the copied code, when the values are read into A, they are XORed by the value read in before them:

for (int i = 1; i <= N; i++)
{
    scanf("%d", &A[i]);
    A[i] ^= A[i - 1];
}

...meaning the following input:

1
4
1 2 3 4

...gets stored into A like so:

A[0]: 00000000000000000000000000000000 = 0
A[1]: 00000000000000000000000000000001 = 1
A[2]: 00000000000000000000000000000011 = 3
A[3]: 00000000000000000000000000000000 = 0
A[4]: 00000000000000000000000000000100 = 4

For the previous input, the correct answer should be:

F(1, 1) + F(1, 2) + F(2, 2) + F(1, 3) + F(2, 3) + F(3, 3) + F(1, 4) + F(2, 4) + F(3, 4) + F(4, 4)
= 1 + 3 + 2 + 2 + 1 + 3 + 5 + 6 + 7 + 4
= 34

...but here's what we get using the algorithm you posted as the "best one" (sum of c * (N - c + 1) * 2 ^ i from i = 0 to i = 29)

2 * (4 - 2 + 1) * 1 + 1 * (4 - 1 + 1) * 2 + 1 * (4 - 1 + 1) * 4
= 6 + 8 + 16
= 30

So it's off by four, and therefore isn't a working solution to the problem, let alone the best working solution.

Note that if the values hadn't been XORed when they were read in, here's what would be in A:

A[0]: 00000000000000000000000000000000 = 0
A[1]: 00000000000000000000000000000001 = 1
A[2]: 00000000000000000000000000000010 = 2
A[3]: 00000000000000000000000000000011 = 3
A[4]: 00000000000000000000000000000100 = 4

So then the formula sum of c * (N - c + 1) * 2 ^ i from i = 0 to i = 29 would give:

2 * (4 - 2 + 1) * 1 + 2 * (4 - 2 + 1) * 2 + 1 * (4 - 1 + 1) * 4
= 6 + 12 + 16
= 34

...which is the correct answer, according to the problem statement on the website you linked. I think this is why we've seen answers so far that agree with the code you posted - the code you posted makes sense, even if the preceding code (found at the page to which you linked) makes the entire program erroneous.