# Sum of XOR of all possible subsets

See an example.

``````
Given set {1, 2, 3}

The subsets of the set are:
{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

The XOR of each subset can be calculated as follows:

XOR({1}) = 1
XOR({2}) = 2
XOR({3}) = 3
XOR({1,2}) = 1 XOR 2 = 3
XOR({1,3}) = 1 XOR 3 = 2
XOR({2,3}) = 2 XOR 3 = 1
XOR({1,2,3}) = 1 XOR 2 XOR 3 = 0
-----------------
1 + 2 + 3 + 3 + 2 + 1 = 12
``````

The algorithm to calculate the sum of XOR of all possible subsets of a given array is as follows:

1. Initialize a variable `xor_sum` to 0, which will hold the XOR of all the elements in the array.

2. Loop through the array, and for each element, perform a bitwise OR operation with the current value of `xor_sum`. This will compute the XOR of all the elements in the array.

3. Once the XOR of all the elements in the array has been computed, multiply it by 2^(n-1), where n is the length of the array. This will give us the sum of XOR of all possible subsets of the array.

4. Print the result of the multiplication.

## Code Solution

``````// C Program
// Sum of XOR of all possible subsets
#include <stdio.h>

void sumSubsetsXor(int arr[], int n)
{
if (n <= 0)
{
return;
}
int sum = 0;
// Execute loop through byte array size
for (int i = 0; i < n; i++)
{
// Sum of or element
sum = sum | arr[i];
}
// Display calculated result
printf("XOR Sum : %d", sum *(1 << n - 1));
}
int main()
{
int arr[] = {
6 , 2 , 5 , 3
};
// Get the size of arr
int n = sizeof(arr) / sizeof(arr[0]);
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
sumSubsetsXor(arr, n);
return 0;
}``````

#### input

``XOR Sum : 56``
``````/*
Java Program for
Sum of XOR of all possible subsets
*/
public class Subarray
{
public void sumSubsetsXor(int[] arr, int n)
{
if (n <= 0)
{
return;
}
int sum = 0;
// Execute loop through byte array size
for (int i = 0; i < n; i++)
{
// Sum of or element
sum = sum | arr[i];
}
// Display calculated result
System.out.print("XOR Sum : " + (sum * (1 << n - 1)));
}
public static void main(String[] args)
{
int[] arr = {
6 , 2 , 5 , 3
};
// Get the size of arr
int n = arr.length;
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
}
}``````

#### input

``XOR Sum : 56``
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program for
Sum of XOR of all possible subsets
*/
class Subarray
{
public: void sumSubsetsXor(int arr[], int n)
{
if (n <= 0)
{
return;
}
int sum = 0;
// Execute loop through byte array size
for (int i = 0; i < n; i++)
{
// Sum of or element
sum = sum | arr[i];
}
// Display calculated result
cout << "XOR Sum : " << (sum *(1 << n - 1));
}
};
int main()
{
int arr[] = {
6 , 2 , 5 , 3
};
// Get the size of arr
int n = sizeof(arr) / sizeof(arr[0]);
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
return 0;
}``````

#### input

``XOR Sum : 56``
``````// Include namespace system
using System;
/*
Csharp Program for
Sum of XOR of all possible subsets
*/
public class Subarray
{
public void sumSubsetsXor(int[] arr, int n)
{
if (n <= 0)
{
return;
}
int sum = 0;
// Execute loop through byte array size
for (int i = 0; i < n; i++)
{
// Sum of or element
sum = sum | arr[i];
}
// Display calculated result
Console.Write("XOR Sum : " + (sum * (1 << n - 1)));
}
public static void Main(String[] args)
{
int[] arr = {
6 , 2 , 5 , 3
};
// Get the size of arr
int n = arr.Length;
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
}
}``````

#### input

``XOR Sum : 56``
``````<?php
/*
Php Program for
Sum of XOR of all possible subsets
*/
class Subarray
{
public	function sumSubsetsXor(\$arr, \$n)
{
if (\$n <= 0)
{
return;
}
\$sum = 0;
// Execute loop through byte array size
for (\$i = 0; \$i < \$n; \$i++)
{
// Sum of or element
\$sum = \$sum | \$arr[\$i];
}
// Display calculated result
echo("XOR Sum : ".(\$sum * (1 << \$n - 1)));
}
}

function main()
{
\$arr = array(6, 2, 5, 3);
// Get the size of arr
\$n = count(\$arr);
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
}
main();``````

#### input

``XOR Sum : 56``
``````/*
Node JS Program for
Sum of XOR of all possible subsets
*/
class Subarray
{
sumSubsetsXor(arr, n)
{
if (n <= 0)
{
return;
}
var sum = 0;
// Execute loop through byte array size
for (var i = 0; i < n; i++)
{
// Sum of or element
sum = sum | arr[i];
}
// Display calculated result
process.stdout.write("XOR Sum : " + (sum * (1 << n - 1)));
}
}

function main()
{
var arr = [6, 2, 5, 3];
// Get the size of arr
var n = arr.length;
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
}
main();``````

#### input

``XOR Sum : 56``
``````#   Python 3 Program for
#   Sum of XOR of all possible subsets
class Subarray :
def sumSubsetsXor(self, arr, n) :
if (n <= 0) :
return

sum = 0
i = 0
#  Execute loop through byte list size
while (i < n) :
#  Sum of or element
sum = sum | arr[i]
i += 1

#  Display calculated result
print("XOR Sum : ", (sum * (1 << n - 1)), end = "")

def main() :
arr = [6, 2, 5, 3]
#  Get the size of arr
n = len(arr)
#    (6) + (2) + (5) + (3) +
#    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
#    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
#    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
#    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
#    --------------
#    56
#    --------------

if __name__ == "__main__": main()``````

#### input

``XOR Sum :  56``
``````#   Ruby Program for
#   Sum of XOR of all possible subsets
class Subarray
def sumSubsetsXor(arr, n)
if (n <= 0)
return
end

sum = 0
i = 0
#  Execute loop through byte array size
while (i < n)
#  Sum of or element
sum = sum | arr[i]
i += 1
end

#  Display calculated result
print("XOR Sum : ", (sum * (1 << n - 1)))
end

end

def main()
arr = [6, 2, 5, 3]
#  Get the size of arr
n = arr.length
#    (6) + (2) + (5) + (3) +
#    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
#    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
#    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
#    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
#    --------------
#    56
#    --------------
end

main()``````

#### input

``XOR Sum : 56``
``````/*
Scala Program for
Sum of XOR of all possible subsets
*/
class Subarray()
{
def sumSubsetsXor(arr: Array[Int], n: Int): Unit = {
if (n <= 0)
{
return;
}
var sum: Int = 0;
var i: Int = 0;
// Execute loop through byte array size
while (i < n)
{
// Sum of or element
sum = sum | arr(i);
i += 1;
}
// Display calculated result
print("XOR Sum : " + (sum * (1 << n - 1)));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subarray = new Subarray();
var arr: Array[Int] = Array(6, 2, 5, 3);
// Get the size of arr
var n: Int = arr.length;
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
}
}``````

#### input

``XOR Sum : 56``
``````import Foundation;
/*
Swift 4 Program for
Sum of XOR of all possible subsets
*/
class Subarray
{
func sumSubsetsXor(_ arr: [Int], _ n: Int)
{
if (n <= 0)
{
return;
}
var sum = 0;
var i = 0;
// Execute loop through byte array size
while (i < n)
{
// Sum of or element
sum = sum | arr[i];
i += 1;
}
// Display calculated result
print("XOR Sum : ", (sum * (1 << (n - 1))), terminator: "");
}
}
func main()
{
let arr = [6, 2, 5, 3];
// Get the size of arr
let n = arr.count;
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
}
main();``````

#### input

``XOR Sum :  56``
``````/*
Kotlin Program for
Sum of XOR of all possible subsets
*/
class Subarray
{
fun sumSubsetsXor(arr: Array < Int > , n: Int): Unit
{
if (n <= 0)
{
return;
}
var sum: Int = 0;
var i: Int = 0;
// Execute loop through byte array size
while (i < n)
{
// Sum of or element
sum = sum or arr[i];
i += 1;
}
// Display calculated result
print("XOR Sum : " + (sum * (1 shl (n - 1))));
}
}
fun main(args: Array < String > ): Unit
{
val arr: Array < Int > = arrayOf(6, 2, 5, 3);
// Get the size of arr
val n: Int = arr.count();
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
}``````

#### input

``XOR Sum : 56``
``````package main
import "fmt"
/*
Go Program for
Sum of XOR of all possible subsets
*/

func sumSubsetsXor(arr[] int, n int) {
if n <= 0 {
return
}
var sum int = 0
// Execute loop through byte array size
for i := 0 ; i < n ; i++ {
// Sum of or element
sum = sum | arr[i]
}
// Display calculated result
fmt.Print("XOR Sum : ", (sum * (1 << (n - 1))))
}
func main() {

var arr = [] int {
6,
2,
5,
3,
}
// Get the size of arr
var n int = len(arr)
/*
(6) + (2) + (5) + (3) +
(6 ^ 2) + (6 ^ 5) + (6 ^ 3) +
(2 ^ 5) + (2 ^ 3) + (5 ^ 3) +
(6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) +
(6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
--------------
56
--------------
*/
sumSubsetsXor(arr, n)
}``````

#### input

``XOR Sum : 56``

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.