Sum of XOR of all possible subsets

https://www.geeksforgeeks.org/sum-xor-possible-subsets/

Given an array arr[] of size n, we need to find sum of all the values that comes from XORing all the elements of the subsets.

Input :  arr[] = {1, 5, 6}
Output : 28
Total Subsets = 23
1 = 1
5 = 5
6 = 6
1 ^ 5 = 4
1 ^ 6 = 7
5 ^ 6 = 3
1 ^ 5 ^ 6 = 2
0(empty subset)
Now SUM of all these XORs = 1 + 5 + 6 + 4 +
                            7 + 3 + 2 + 0
                          = 28

A Naive approach is to take the XOR all possible combination of array[] elements and then perform the summation of all values. Time complexity of this approach grows exponentially so it would not be better for large value of n.

An Efficient approach is to find the pattern with respect to the property of XOR. Now again consider the subset in binary form like:

    1 = 001
    5 = 101
    6 = 110
1 ^ 5 = 100
1 ^ 6 = 111
5 ^ 6 = 011
1^5^6 = 010

So if we analyze all these binary number of the XORs, we can observe that set bit occurs at all the position of i(0 to n-1) will exactly contribute to half of 2n. So we can easily imposed these two condition at each such positions of i.

• If there is any value of arr[] that has set tth bit set, then exactly half of 2n subsets will be of the form, so they will contribute to 2n-1+i to the final sum.
• If there is no value of arr[] that ith bit set, then we can say that there will be no term in all subsets that have a ith bit set.

Now the question boils down to check which position of element of the arr[] will be set or not. But here is some trick that we will not iterate for all elements one by one in spite of that we can simple take the OR of all such values and multiply with 2n-1, For example:-

Take a OR of all arr[] elements, we get 
= 1 | 5 | 6
= 001 | 101 | 110
= 111

Now to find final summation, we can write it down as:-
= 1*2n-1+2 + 1*2n-1+1 + 1*2n-1+0
= 2n-1 * (1*22 + 1*21 + 1*20 )
= 2n-1 * (1112)
= 2n-1 * 7

Put n = 3,  we get
= 28

So at last for any value of n and array elements, we can simple say that the final sum will be 2n-1 times the bitwise OR of all the inputs.

    // Returns sum of XORs of all subsets

    static int xorSum(int arr[], int n)

    {

          

        int bits = 0;

      

        // Finding bitwise OR of all elements

        for (int i = 0; i < n; ++i)

            bits |= arr[i];

      

        int ans = bits * (int)Math.pow(2, n-1);

      

        return ans;

    }