主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始的正整數陣列 nums，以及一個正整數 k。
一個數對 (num1, num2) 如果滿足以下條件，則會被稱為「出色的」：
num1 和 num2 都存在於陣列 nums 之中、
(num1 OR num2) 和 (num1 AND num2) 中是 1 的位元之總和大於等於 k，其中 OR 為按位元之 OR 位元運算而 AND 為按位元之 AND 位元運算。
回傳相異的出色數對的數量。
兩數對 (a, b) 和 (c, d) 如果滿足 a != c 或是 b != d，則視為相異。例如，(1, 2) 和 (2, 1) 是相異的。
注意到一個數對 (num1, num2) 滿足 num1 == num2 的話，也依舊可以是出色數對，只要在陣列之中 num1 有至少出現一次。
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9
1 ≦ k ≦ 60
範例測資：
範例 1：
輸入： nums = [1,2,3,1], k = 3
輸出： 5
解釋： 出色數對為以下：
- (3, 3)。(3 AND 3) 和 (3 OR 3) 之值都等於二進位制中的 (11)。是 1 的位元之總數為 2 + 2 = 4，其值大於等於 k = 3。
- (2, 3) 和 (3, 2)。(2 AND 3) 等於二進位制中的 (10)，而 (2 OR 3) 等於二進位制中的 (11)。是 1 的位元之總數為 1 + 2 = 3。
- (1, 3) 和 (3, 1)。(1 AND 3) 等於二進位制中的 (01)，而 (1 OR 3) 等於二進位制中的 (11)。是 1 的位元之總數為 1 + 2 = 3。
所以出色數對總數量為 5 個。
範例 2：
輸入： nums = [5,1,1], k = 10
輸出： 0
解釋： 這個陣列中沒有出色數對。
解題思維：
如果我們把 (num1 OR num2) 和 (num1 AND num2) 分開考慮的話，很有可能什麼都觀察不出來。
不過如果我們把兩者的資訊一起考慮的話，事情就不太一樣了。假設現在 num1 = 1001011 、num2 = 1110001，則
(num1 OR num2) 的結果為 1111011、
(num1 AND num2) 的結果為 1000001。
1 的總數量是 8，剛好就是 num1 和 num2 各自 1 的數量之加總。
而這不是巧合，不管試幾個例子都會是對的。這是為什麼呢？
因為 (num1 OR num2) 的結果代表著每一個位元如果在 num1 或 num2 其中一者是 1 則該位元就是 1；反之，兩者都是 0 則該位元為 0。所以我們計算這個結果的 1 的位元之數量代表著我們在統計哪些位元在給定的兩個數字之中是 1，但是對於同時在兩個數字中都是 1 的位元我們只會算到一次。而剛好這部分可以由 AND 的操作來找到。
如果純文字說明太難理解，則可以直接窮舉單一位元（因為每一個位元彼此獨立，不會互相影響結果）所有可能性即可看出：
0 OR 0 和 0 AND 0：結果 1 的總數為 0，兩數原先 1 的總數也為 0；
0 OR 1 和 0 AND 1：結果 1 的總數為 1，兩數原先 1 的總數也為 1；
1 OR 0 和 1 AND 0：結果 1 的總數為 1，兩數原先 1 的總數也為 1；
1 OR 1 和 1 AND 1：結果 1 的總數為 2，兩數原先 1 的總數也為 2。
因此我們只要計算所有 i + j ≧ k 的總數即可，其中 i 和 j 為某兩數各自的 1 之數量。
而我們只要預先掃過 nums 中每個數字，並統計其 1 的位元數便可以知道 nums 中有多少數字包含特定 1 的數量。因此對於 i + j ≧ k，只要看數量 i 的有多少數字（假設為 x）、數量 j 有多少數字（假設為 y），便可以知道這一個 (i, j) 數對之結果為兩者相乘（即 x × y）。因此所求只要把所有符合條件的數對之結果相加即為所求。
不過，由於題目在提及從 nums 中取出數字（參見「兩數對 (a, b) 和 (c, d)」那一段）時，兩數對相異的條件是看數值本身而不是看數字在 nums 中的位置是否相異。因此，nums 中如果有重複出現的次數實際上不會對答案產生影響，反而在上述的計算之中會多算。因此我們需要事先把重複的數字消到只剩一個存在於 nums 之中。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
