LC 1835. 所有数对按位与结果的异或和

这题有点意思，首先思路要要对，就是针对判断每个位。

假设在xth bit上，A1有a个0, b个1，A2有c个0, d个1，那么A1 x A2就有

所以最终有 (ac + ad + bc) 个0， bd个1.

如果1是偶数个的话，那么最终结果就是0，否则就是1.

一个优化点就是判断最多有多少个bits. 

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        maxv = max(max(arr1), max(arr2))
        maxbits = 0
        for i in reversed(range(32)):
            if maxv & (1 << i):
                maxbits = i + 1
                break

        def count(arr):
            ones = [0] * 32
            for i in range(maxbits):
                mask = 1 << i
                for x in arr:
                    if x & mask:
                        ones[i] += 1
            return ones

        a = count(arr1)
        b = count(arr2)
        ans = 0
        for i in range(32):
            c = a[i] * b[i]
            if c % 2:
                ans = ans | (1 << i)
        return ans