題目連結:
題目意譯:
給定兩正整數 num1 和 num2,請找到正整數 x 使得:
x 與 num2 在有著相同數量的設置位元(Set Bits),且
x 與 num1 XOR 之值為可能的最小值。
注意到該 XOR 之操作為按位元(Bitwise) XOR。
回傳該整數 x。測資之生成滿足 x 之值唯一。
一個整數的設置位元之數量為其於二進位制中 1 的個數。
限制:
1 ≦ num1, num2 ≦ 10 ^ 9
範例測資:
範例 1:
輸入: num1 = 3, num2 = 5
輸出: 3
解釋:
num1 和 num2 的二進位表示法分別為 0011 和 0101。
整數 3 與 num2 有著相同的設置位元,而 3 XOR 3 = 0 是最小值。
範例 2:
輸入: num1 = 1, num2 = 12
輸出: 3
解釋:
num1 和 num2 的二進位表示法分別為 0001 和 1100。
整數 3 與 num2 有著相同的設置位元,而 3 XOR 1 = 2 是最小值。
解題思維:
首先先數一下 num2 有多少個設置位元,假設有 C2 個。同樣地,算一下 num1 有幾個設置位元,假設有 C1 個。
如果 C1 = C2,則事情非常地簡單——x 之值即為 num1,因為 XOR 之後的結果為 0,必定是最小值;
如果 C1 < C2,則 num1 中是 1 的位元,對應到 x 之中也是 1(XOR 後才能消掉)。而剩下的 C2 - C1 的位元應選盡可能靠右的(也就是在二進位中代表的數字越小者),當然不能選到已經是 1 的位元。而這個造出來的數值即為 x(為了篇幅短一點,證明省略;但真的想證的話,只要用反證法假設我們的選擇不是最佳,然後發現這個假設是錯的即可);
如果 C1 > C2,則選出 num1 中盡可能靠左的 C2 個設置位元,它們對應於 x 中也將是設置位元,這樣子的 x 之值也是所求(一樣這邊省略證明,但證明精神如上所述)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。