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.



Array :- 1 2

Output :- 6


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$
  • $\begingroup$ @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, $\endgroup$
    – devsda
    Nov 21, 2013 at 5:20
  • $\begingroup$ @D.W. If you can, shift this question to SO. $\endgroup$
    – devsda
    Nov 21, 2013 at 5:27
  • $\begingroup$ @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. $\endgroup$ Nov 21, 2013 at 12:12
  • $\begingroup$ see also math.stackexchange.com/questions/712487/… $\endgroup$ Aug 14, 2016 at 14:10

2 Answers 2


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.

  • $\begingroup$ Then , why i only moves upto 30, Any logic ? $\endgroup$
    – devsda
    Nov 21, 2013 at 5:47
  • $\begingroup$ Can you please explain the whole logic ? How this logic comes in mind, as I am naive. $\endgroup$
    – devsda
    Nov 21, 2013 at 5:58
  • $\begingroup$ It'll help to start with an example of one bit numbers and see what really happens. Then extend it to two bits etc. $\endgroup$
    – Parham
    Nov 21, 2013 at 6:59
  • $\begingroup$ You didn't give my first question's answer. $\endgroup$
    – devsda
    Nov 21, 2013 at 8:49
  • $\begingroup$ 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? $\endgroup$
    – Parham
    Nov 21, 2013 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.

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Sep 9, 2015 at 16:22
  • $\begingroup$ Question line also says that "I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here." $\endgroup$ Sep 9, 2015 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.