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
