526互联

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

发布时间 2023-04-13 14:41:39作者: zhangk1988

题目描述

给了列表异或和的定义
现在的列表是arr1和arr2构造出来的，元素对是arr[i] and arr[j]
问以上列表的异或和？

f1-依次确定答案的每一位

基本分析

  1. 为什么考虑计算答案的每一位？表达式只包含位运算（按位与 和按位异或）
  2. 具体怎么计算？要知道答案的第k为是1还是0->分别计算arr1和arr2中第k为的1的个数，只有都是奇数时候才是1

代码

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        
        ans = 0
        for k in range(30, -1, -1):
            cnt1 = sum(1 for d in arr1 if d & (1<<k))
            cnt2 = sum(1 for d in arr2 if d & (1<<k))
            if cnt1 & 1 and cnt2 & 1:
                ans |= 1 << k
        
        return ans

总结

  1. 推导需要再消化
f2-公式变形

基本分析

  1. 怎么进行变形？(a & b) ^ (a & c) = a & (b ^ c)
  2. 最终结果？数组的异或和再与

代码

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        return reduce(xor, arr1, 0) & reduce(xor, arr2, 0)

总结

  1. 记住结论