1835. 所有数对按位与结果的异或和（Rating 1825）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

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

Rating 1825

思路

考虑位运算。对于某一位

遍历arr1

• 若arr1中某个数字对应位为1，那么与arr2中所有数字对应位按位与结果与arr2中所有数字对应位相同；
• 若arr1中某个数字对应位为0，那么与arr2中所有数字对应位按位与结果均为0；

因此，对于这一位，可以统计出来arr1所有数与arr2所有数按位与后1的数量和0的数量。

• 对于所有的0，异或后得到1个0
• 对于所有的1
  • 若1为奇数，则异或结果为1
  • 若1为偶数，则异或结果为0

按照以上思路编码即可。

后来参考灵神题解，根据数学性质

(a&b)^(a&c) == a&(b^c)

那么我们可以分别求出arr1和arr2中所有数字异或结果，再求与即为答案。

代码

位运算解法

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        n = len(arr2)
        ret = 0
        for b in range(31, -1, -1): # 遍历32位
            arr2_cnt0, arr2_cnt1 = 0, 0 # 统计arr2中当前位0的数量和1的数量
            for num in arr2:
                arr2_cnt0 += ((num >> b) & 1) == 0
                arr2_cnt1 += ((num >> b) & 1) == 1
            cnt0, cnt1 = 0, 0 # 统计当前位，arr1和arr2所有数字按位与后得到的0的数量和1的数量
            for num in arr1:
                if ((num >> b) & 1) == 0: # 若arr1数字对应位为0，那么与arr2中所有数字对应位按位与结果均为0
                    cnt0 += n
                else: # 若arr1数字对应位为1，那么与arr2中所有数字对应位按位与结果与arr2中所有数字对应位相同
                    cnt1 += arr2_cnt1
                    cnt0 += arr2_cnt0
            if cnt1 % 2 == 0: # 如果1的数量位偶数，那么异或结果是0
                ret = (ret << 1) + 0
            else: # 否则异或结果是1
                ret = (ret << 1) + 1
        return ret

数学解法

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        xor1, xor2 = 0, 0
        for num in arr1:
            xor1 ^= num
        for num in arr2:
            xor2 ^= num
        return xor1 & xor2