Sum of Pairwise XOR (explained BITS manipulation)

Hey there!!

Waiting for learning new things? So here it is.

It is a question given here :- click here.

We encourage you to try solving problem first by yourself but still if you are getting trouble then move on to tutorials.

So, in this question we require to find sum of XOR of all pairs that can be made in a set.

As you can see time limit for this question is 2 sec. So, going by conventional method will require O(n^2) complexity solution. As n can be 10^6, Hence it is difficult to pass under given constraints.

So what should be the logic?





Since this question deals with bits manipulation so let us thinks that way.

We know a XOR operation returns 1  if any one of the bit is 1 but not both. So let us apply this knowledge here.

EXAMPLE given is :

1 8 9 2 3      and its answer is       66.

Lets do it:
BITS Representation:

1: 0001           8:1000           9:1001         2:0010           3: 0011

A quick snapshot of ALGORITHM:

1. Pick up a position and traverse that position bit in all numbers one by one.
2. Count the numbers that have set bit(1) at that position.(suppose k)
3. Now number that have that bit as 0 are total-k.
4. We know that XOR operation will return 1 when two bits are different.
5. So total such pair at that bit position will be k*(n-k). (n=total numbers)
6. now we got such pairs so to convert them to decimal form multiply (2^bitposition) by k*(n-k).
7. add that multiplication result to your answer.
8. Do it for all such bit position and u get your answer.

Complexity of this ALGO is O(32*n).(assuming at most 32 bit number present) and this will pass in given constraints.


So here going bit by bit for every no._________
Lets pick up first bit i.e. 0th bit.

• 0th bit are :  1,0,1,0,1

                     value of k as said in algorithm is= 3 and since n=5 (total numbers) so (n-k)=2;
                      so ans= ans+ (2^0)*(k*(n-k)) = 6 .......... since we are looking at 0th bit.

• 1st bit are : 0,0,0,1,1

                     similarly k=2  n-k=3
                     ans= ans + (2^1)*(6) = 12;

• 2nd bit are : 0,0,0,0

                     similarly k=0  n-k=5
                     ans= ans + (2^2)*(0) = 0;

• 3rd bit are : 0,1,1,0,0

                     similarly k=2  n-k=3
                     ans= ans + (2^3)*(6) = 48;

• If you are wondering how to know that i-th bit is 1. Then here is the operation 1&(a[j]>>i) this will whether i-th bit is set or not.

and here is our ans after adding all ans = 66.

TIPS:

1. there can be 32 bits so to be safe loop till 32 bits.
2. use long long int.

Hope u enjoyed knowing about this problem.

TRYING is best learning, So try yourself first,Still facing problem you can contact for solution or comment below.

Soon We will be adding Tutorials on BIT manipulation. Hang on till then :) :D .