The sum of XOR of all pairs in Java
The Sum of XOR of All Pairs (SXAP) is a fundamental principle in discrete mathematics used for optimization, data encoding, and cryptographic protocols. Originating from bitwise XOR operations, it optimizes algorithms, ensures data security, and reduces redundancy in digital communication systems. SXAP's study extends beyond practical applications to understanding binary arithmetic and combinatorial structures.
Example1:
Input: arr[ ] = {7, 3, 5}
Output: 12
Explanation: Every potential pair along with its Xor value: ( 3^5 = 6) + (7^3 = 4) + (7^5 = 2) = 6 + 4 + 2 = 12
Example2:
Input: arr[ ] = {5, 9, 7, 6}
Output: 47
Explanation: Every potential pair along with its Xor value: (5^9=12) + (5^7=2) + (5^6=3) + (9^7=14) + (9^6=15) + (7^6=1) = 12 + 2 + 3 + 14 + 15 + 1 = 47
Using Bit Manipulation
Algorithm
Step 1: Initialize sumXOR to 0.
Step 2: Iterate over each bit position from 0 to 31.
Step 3: Inside the loop, initialize countSetBits to 0.
Step 4: Iterate through array elements.
Step 5: If the ith bit of the current element is set, increment countSetBits.
Step 6: Calculate countUnsetBits as n - countSetBits.
Step7 : Add (1 << i) * countSetBits * countUnsetBits to sumXOR.
Step 8: Return sumXOR.
Here is an implementation of finding the sum of XOR of all pairs using bit manipulation :
FileName:SumofXOR.java
public class SumofXOR { public int sumXOR(int arr[], int n) { int sumXOR = 0; for (int i = 0; i < 32; i++) { // Count the number of elements having ith bit set int countSetBits = 0; for (int j = 0; j < n; j++) { if ((arr[j] & (1 << i)) != 0) countSetBits++; } // Count the number of elements having ith bit not set int countUnsetBits = n - countSetBits; // For each set bit, there will be countSetBits * countUnsetBits pairs contributing to sumXOR sumXOR += (1 << i) * countSetBits * countUnsetBits; } return sumXOR; } public static void main(String[] args) { int[] arr = {5, 9, 7, 6}; int n = arr.length; SumofXOR sum = new SumofXOR(); System.out.println("Sum of XOR of all pairs: " + sum.sumXOR(arr, n)); } }
Output:
The sum of XOR of all pairs: 47
Complexity analysis: The above approach has a time complexity of O(n * 32) due to its nested loop structure. Its space complexity is O(1), as it uses a constant extra space regardless of the input array size.
Using Mathematical Approach
Algorithm
Step 1: Initializes sumXOR to 0.
Step 2: Iterates through each element of the array.
Step 3: Calculates the XOR of the current pair of elements.
Step 4: Adds the result to sumXOR.
Step 5: Returns sumXOR.
Here is an implementation of finding the sum of XOR of all pairs using a mathematical approach :
FileName:SumofXOR1.java
public class SumofXOR1 { public int sumXOR(int arr[], int n) { int sumXOR = 0; for (int i = 0; i < n; i++) { // For each element, iterate through the remaining elements of the array for (int j = i + 1; j < n; j++) { // Calculate the XOR of the current pair of elements and add it to sumXOR sumXOR += arr[i] ^ arr[j]; } } return sumXOR; } public static void main(String[] args) { int[] arr = {5, 9, 7, 6}; int n = arr.length; SumofXOR1 sol = new SumofXOR1(); // Calculate and print the sum of XOR of all pairs of numbers in the array System.out.println("Sum of XOR of all pairs: " + sol.sumXOR(arr, n)); } }
Output:
The sum of XOR of all pairs: 47
Complexity analysis: The above approach has a time complexity of O(n^2) due to its nested loop structure and a space complexity of O(1) due to its constant extra space usage.
Using Optimized Approach
Algorithm
Step 1: Initialize the variable to hold the XOR sum of pairs.
Step 2: Iterate through each bit position from 0 to 31.
Step 3: Count the number of elements with i'th bit set at each bit position.
Step 4: Calculate the contribution of the current bit position to the XOR sum.
Step 5: Add the current bit position's contribution to the result.
Step 6: Return the final result as XOR of all array pairs.
Here is an implementation of finding the sum of XOR of all pairs using an optimized approach :
FileName:XORSumPairs.java
public class XORSumPairs { static long sumXOR(int arr[], int n) { // Initialize the result long result = 0; // Traverse through all bits for (int i = 0; i < 32; i++) { // Count the number of elements with i'th bit set int count = 0; for (int j = 0; j < n; j++) { if ((arr[j] & (1 << i)) != 0) { count++; } } // Add "count * (n - count) * 2^i" to the result result += (long)count * (n - count) * (1 << i); } return result; } public static void main(String[] args) { int[] arr = {5, 9, 7, 6}; System.out.println("Sum of XOR of all pairs : " + sumXOR(arr, arr.length)); } }
Output:
The sum of XOR of all pairs: 47
Complexity analysis: The above approach's time complexity is O(n) because it iterates over each element of the array once to calculate the XOR sum, and its space complexity is O(1) because it uses a fixed amount of extra space regardless of the size of the input array.