好久沒發每日文了
2429. Minimize XOR
思路:
先數num1、num2化成二進位後分別有幾個1
假設num1、num2畫成二進位後1的個數為cnt1、cnt2
分成3個情況
1. cnt1 = cnt2 :
直接回傳num1
2. cnt1 > cnt2 :
假設diff = cnt1 - cnt2
從低位開始把num1是1的位數變為0
重複上述動作 diff 次
最後回傳num1
3. cnt1 < cnt2 :
假設diff = cnt2 - cnt1
從低位開始把num1是0的位數變成1
重複上述動作diff次
最後回傳num1
golang code :
func minimizeXor(num1 int, num2 int) int {
cnt1, cnt2, tmp := 0, 0, num1
for num2 > 0 {
cnt2 += num2 & 1
num2 >>= 1
}
for num1 > 0 {
cnt1 += num1 & 1
num1 >>= 1
}
ans, idx := tmp, 0
if cnt1 == cnt2 {
return tmp
} else if cnt1 < cnt2 {
cnt2 -= cnt1
for cnt2 > 0 {
if tmp&1 == 0 {
ans |= (1 << idx)
cnt2--
}
tmp >>= 1
idx++
}
} else {
cnt2 = cnt1 - cnt2
for cnt2 > 0 {
if tmp&1 == 1 {
ans ^= (1 << idx)
cnt2--
}
tmp >>= 1
idx++
}
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.98.9 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1736947934.A.7B2.html