Tổng XOR của tất cả các tập con trong C++

Cho mảng arr[] gồm n số. Nhiệm vụ là tính tổng XOR của tất cả các tập con (subset) có thể tạo thành từ mảng.

Ví dụ minh họa

Input: arr[] = {5, 1, 4}
Output: 20
Giải thích:
Tất cả các tập con và XOR tương ứng:
{5} = 5
{1} = 1
{4} = 4
{5, 1} = 4
{5, 4} = 1
{1, 4} = 5
{5, 1, 4} = 0
Tổng = 5 + 1 + 4 + 4 + 1 + 5 + 0 = 20

Cách đơn giản là sinh tất cả 2ⁿ tập con, tính XOR từng tập và cộng dồn. Độ phức tạp O(n * 2ⁿ), chỉ phù hợp n nhỏ.

Phương pháp tối ưu: Sử dụng tính chất XOR

Quan sát quan trọng: Mỗi bit trong kết quả tổng chỉ phụ thuộc vào việc bit đó có xuất hiện trong OR của tất cả phần tử hay không.

• Tính bitOR = arr[0] | arr[1] | ... | arr[n-1]
• Mỗi bit được set trong bitOR sẽ đóng góp đúng 2^(n-1) lần vào tổng (vì có 2^(n-1) tập con có XOR tại bit đó = 1).
• Kết quả: sum = bitOR * 2^(n-1)

Độ phức tạp O(n), cực kỳ hiệu quả.

Chương trình C++ minh họa

#include <iostream>
#include <cmath>
using namespace std;

long long subSetXORSum(int arr[], int n) {
    int bitOR = 0;
    for (int i = 0; i < n; ++i)
        bitOR |= arr[i];
    return (long long)bitOR * (1LL << (n - 1)); // Dùng bit shift thay pow để chính xác
}

int main() {
    int arr[] = {1, 5, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Tong XOR cua tat ca tap con la " << subSetXORSum(arr, size);
    return 0;
}

Kết quả

Tong XOR cua tat ca tap con la 20