文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

列表的 異或和（XOR sum）指對(duì)所有元素進(jìn)行按位 XOR 運(yùn)算的結(jié)果。
如果列表中僅有一個(gè)元素，那么其 異或和 就等于該元素。

例如，[1,2,3,4] 的 異或和 等于 1 XOR 2 XOR 3 XOR 4 = 4 ，而 [3] 的 異或和 等于 3 。
給你兩個(gè)下標(biāo) 從 0 開(kāi)始 計(jì)數(shù)的數(shù)組 arr1 和 arr2 ，兩數(shù)組均由非負(fù)整數(shù)組成。

根據(jù)每個(gè) (i, j) 數(shù)對(duì)，構(gòu)造一個(gè)由 arr1[i] AND arr2[j]（按位 AND 運(yùn)算）結(jié)果組成的列表。其中 0 <= i < arr1.length 且 0 <= j < arr2.length 。

返回上述列表的 異或和 。

示例 1： 輸入：arr1 = [1,2,3], arr2 = [6,5] 輸出：0 解釋：列表 = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1] ， 異或和 = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0 。示例 2： 輸入：arr1 = [12], arr2 = [4] 輸出：4 解釋：列表 = [12 AND 4] = [4] ，異或和 = 4 。提示： 1 <= arr1.length, arr2.length <= 10^5 0 <= arr1[i], arr2[j] <= 10^9

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-xor-sum-of-all-pairs-bitwise-and
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

有公式：

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

用程序測(cè)試：

#include<bits/stdc++.h> using namespace std; int main(){for(int a = 0; a < 2; a++){for(int b = 0; b < 2; b++){for(int c = 0; c < 2; c++){cout << "a = " << a << " b = " << b << " c = " << c;cout << " (a&b)^(a&c) = " << ((a&b)^(a&c));cout << " a&(b^c) = " << (a&(b^c)) << endl;}}} } a = 0 b = 0 c = 0 (a&b)^(a&c) = 0 a&(b^c) = 0 a = 0 b = 0 c = 1 (a&b)^(a&c) = 0 a&(b^c) = 0 a = 0 b = 1 c = 0 (a&b)^(a&c) = 0 a&(b^c) = 0 a = 0 b = 1 c = 1 (a&b)^(a&c) = 0 a&(b^c) = 0 a = 1 b = 0 c = 0 (a&b)^(a&c) = 0 a&(b^c) = 0 a = 1 b = 0 c = 1 (a&b)^(a&c) = 1 a&(b^c) = 1 a = 1 b = 1 c = 0 (a&b)^(a&c) = 1 a&(b^c) = 1 a = 1 b = 1 c = 1 (a&b)^(a&c) = 0 a&(b^c) = 0

• 先對(duì)arr1每個(gè) 元素求的結(jié)果為 a1 & (b1^...^bn), a2 & (b1^...^bn), ... an & (b1^...^bn)
• 上式寫n項(xiàng)再求異或，然后把右邊一項(xiàng)提出來(lái)有 (a1^a2...^an) & (b1^...^bn)

class Solution { public:int getXORSum(vector<int>& arr1, vector<int>& arr2) {int xor1 = 0, xor2 = 0;for(auto a : arr1)xor1 ^= a;for(auto a : arr2)xor2 ^= a;return xor1 & xor2;} };

140 ms 91.2 MB C++

比賽時(shí)候按位猜的答案，兩邊的位必須都有奇數(shù)個(gè)1答案才為1

class Solution { public:int getXORSum(vector<int>& arr1, vector<int>& arr2) {int n1 = arr1.size(), n2 = arr2.size();int ans = 0;vector<int> ct1(32), ct2(32);for(int i = 0 ;i < n1 ; i++){for(int j = 0; j < 32; j++){if((arr1[i]>>j) & 1)ct1[j]++;}}for(int i = 0 ;i < n2 ; i++){for(int j = 0; j < 32; j++){if((arr2[i]>>j) & 1)ct2[j]++;}}for(int i = 0; i < 32; ++i){if(ct1[i]%2 && ct2[i]%2)ans |= 1<<i;}return ans;} };

296 ms 91.4 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1835. 所有数对按位与结果的异或和（位运算 (ab)^(ac) = a(b^c) ）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。