两个子集值的所有组合的 XOR 之和

Question

假设我有两个整数数组 a 和 b，每个数组都有 n 个整数。 我想知道两个不同子集中两个整数的所有组合的异或之和。

例如，

if n == 3

： 我想知道以下值：

a1^b1 + a1^b2 + a1^b3 + a2^b1 + a2^b2 + a2^b3 + a3^b1 + a3^b2 + a3^b3

有没有办法以与 + 和 x 类似的方式有效地做到这一点

i.e. 1*2 + 1*3 + 2*2 + 2*3 = (1+2)*(2+3)

Answer 1

有一个公式在数组中只有一个非零值时有效。因此，您可以一次执行一个位值，然后将每个位值的结果相加。

如果您知道 a 包含 x 1 和 n-x 0，并且 b 包含 y 1 和 n-y 0，则每个 a^b 要么是 1 要么 0，并且该数字1s 正好是 x * (n-y) + y * (n-x)。

如果隔离子集中的 1 位，则可以计算 XOR 对中设置了多少个 1 位。同样，如果隔离 2 位，则可以计算 XOR 对中设置了多少个 2 位。将每个位值的结果相加得出最终答案：

int total = 0;
for (int bit=1; bit>0 && (bit  < a.length || bit < b.length); bit<<=1) {
    int acount = 0;
    for (int val : a) {
        acount += val & bit;
    }
    acount /= bit;
    int bcount = 0;
    for (int val: b) {
        bcount += val & bit;
    }
    bcount /= bit;
    total += bit * ( acount * (b.length-bcount) + bcount * (a.length-acount) );
}

Answer 2

class Solution{
    public:
    // Returns sum of bitwise OR
    // of all pairs
    long long int sumXOR(int arr[], int n)
    {
         
    long long int ans = 0;

    for (int i = 0; i < 32; i++)
    {
        int sethai = 0;
        for (int j = 0; j < n; j++)
        {
            if (arr[j] & (1 << i))
            {
                sethai++;
            }
        }
        ans += (long long)((long long)sethai * (n - (long long)sethai)) * (1 << i);
    }

    return ans;
        
    }
};