# 1835. Find XOR Sum of All Pairs Bitwise AND
###### tags: `Leetcode` `Hard` `Bit Manipulation` `XOR`
Link: https://leetcode.com/problems/find-xor-sum-of-all-pairs-bitwise-and/
## 思路
### 思路一 $O(N)$ $O(N)$
参考[这里](https://github.com/wisdompeak/LeetCode/tree/master/Bit_Manipulation/1835.Find-XOR-Sum-of-All-Pairs-Bitwise-AND)
先考虑arr1里面的$a_1$跟arr2里面的所有数字$b_1$, $b_2$,...做运算
也就是($a_1$ & $b_1$)^($a_1$ & $b_2$)^ ... ^($a_1$ & $b_n$)
这里我们一位一位考虑
如果$a_1$的某一位是1 那么对于这一位而言我们就要考虑$b_1$, $b_2$,...的这一位里面1的个数 如果是奇数那么这一位的结果就是1 否则就是0
如果$a_1$的某一位是0 那么这一位就会变成0
### 思路二 $O(N)$ $O(1)$
参考[这里](https://leetcode.com/problems/find-xor-sum-of-all-pairs-bitwise-and/discuss/1163992/JavaC%2B%2BPython-Easy-and-Concise-O(1)-Space)

## Code
### 思路一

class Solution {
public int getXORSum(int[] arr1, int[] arr2) {
boolean[] oneCnts = new boolean[32];
for(int num:arr2){
for(int i=0; i<32; i++){
if(((num>>i)&1)==1) oneCnts[i] = !oneCnts[i];
}
}

int ans = 0;
for(int num:arr1){
int temp = 0;
for(int i=0; i<32; i++){
if(((num>>i)&1)==0) continue;
else if(oneCnts[i]){
temp += 1<<i;
}
}
ans ^= temp;
}
return ans;
}
}

### 思路二

class Solution {
public int getXORSum(int[] arr1, int[] arr2) {
int xora = 0, xorb = 0;
for(int num:arr1) xora^=num;
for(int num:arr2) xorb^=num;
return xora&xorb;
}
}