Tổng XOR của tất cả các cặp trong mảng C++

Cho mảng arr[] gồm n số nguyên. Tìm tổng XOR của tất cả các cặp phần tử (arr[i], arr[j]) với i < j.

Ví dụ minh họa

Input: arr[] = {5, 1, 4}
Output: 10
Giải thích:
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
Tổng = 4 + 5 + 1 = 10

Phương pháp đơn giản (O(n²))

Duyệt tất cả cặp (i, j) với i < j, tính XOR và cộng dồn.

int findXORSum(int arr[], int n) {
    long long sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            sum += (arr[i] ^ arr[j]);
    return sum;
}

Phương pháp tối ưu: Xử lý bit (O(32 * n))

Xét từng vị trí bit i (0..31). Giả sử có setBits phần tử có bit i = 1, và unsetBits = n - setBits phần tử có bit i = 0.

Số cặp có XOR tại bit i bằng 1 chính là setBits * unsetBits (một phần tử có bit 1, một phần tử có bit 0).

Đóng góp của bit i vào tổng: setBits * unsetBits * 2^i.

Tổng kết quả là tổng đóng góp của tất cả các bit.

Chương trình C++ tối ưu

#include <iostream>
using namespace std;

long long findXORSumOptimized(int arr[], int n) {
    long long sum = 0;
    for (int i = 0; i < 32; i++) {
        long long setBits = 0;
        for (int j = 0; j < n; j++)
            if (arr[j] & (1LL << i))
                setBits++;
        long long unsetBits = n - setBits;
        sum += setBits * unsetBits * (1LL << i);
    }
    return sum;
}

int main() {
    int arr[] = {5, 1, 4, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tong XOR cua tat ca cap la " << findXORSumOptimized(arr, n);
    return 0;
}

Kết quả

Tong XOR cua tat ca cap la 68