ผลรวมของ XOR ของทุกคู่ในอาร์เรย์ใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ arr[] ขนาด n จำนวนเต็ม หาผลรวมของ XOR ของทุกคู่ที่เป็นไปได้ในอาร์เรย์

ตัวอย่าง

Input: arr[] = {5, 1, 4}
Output: 10
Explanation:
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
ผลรวม = 4 + 5 + 1 = 10

วิธีแก้ปัญหา

วิธีง่าย (Nested Loops) - O(n²)

Initialise sum = 0
for i = 0 to n-1:
    for j = i+1 to n-1:
        sum += arr[i] ^ arr[j]
return sum

วิธีที่มีประสิทธิภาพ (Bit Manipulation) - O(n)

พิจารณาแต่ละตำแหน่งบิต (0-31) แยกกัน:

ผลรวมบิตที่ i = (จำนวนบิต 1) * (จำนวนบิต 0) * (2^i)

ผลรวมทั้งหมด = ผลรวมของทุกบิต

ตัวอย่างโค้ด C++ (วิธีที่มีประสิทธิภาพ)

#include <iostream>
#include <math.h>
using namespace std;

long findXORSum(int arr[], int n) {
    long sum = 0;
    int unsetBits = 0, setBits = 0;
    for (int i = 0; i < 32; i++) {
        unsetBits = 0; setBits = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] % 2 == 0)
                unsetBits++;
            else
                setBits++;
            arr[j] /= 2;
        }
        sum += (unsetBits * setBits * (pow(2, i)));
    }
    return sum;
}

int main() {
    int arr[] = { 5, 1, 4, 7, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Sum of XOR of all pairs in an array is " << findXORSum(arr, n);
    return 0;
}

ผลลัพธ์

Sum of XOR of all pairs in an array is 68