題目描述
對于64位或32位的無符號整數x，我們在它的二進制表示中，把1的個數稱為x的權重，例如x=7，它的二進制表示為0b111，由于有3個1，所以x的權重就是3，用S(k)表示64位或32位整數中，權重為k的所有整數的集合，其中k不等于0、32、64，現給定一個整數x，假定它屬于集合S(k)，要求找出另一個屬于S(k)的整數y，使得|x-y|的值最小，
解題思路
解題方法：可以先使用窮舉法，使k等于一個較小的數，比如k=3，假定x=0b1011，然后列舉一些同樣k=3的數字作為y，可以發現|x-y|最小時的y=0b1101，可以再假定x為其他一些值，并找出對應的|x-y|最小時的y，可以發現這樣一個簡單的規律：x對應的y其實就是在x的二進制表示中從右往左遍歷，找到兩個值不同的位元位，然后交換這兩個位元位的值就得到了y的二進制表示，
思考：由于這個規律只是通過簡單的幾個例子得出，不一定保證是正確的解題方法，所以可以再思考一下這個方法的可行性：想要兩個數的差的絕對值最小，就需要這兩個數盡可能相近，即二進制位上各個位置上的值要盡可能相同，而又由于需要權重相同，所以只能將其中一個0變為1，另一個1變為0，即將x中的其中一組0和1進行交換，而這樣變換之后的相減操作，想要兩個值的差值最小，交換的這兩個位置就必須盡可能相近且應該是從最低位開始查找，而最相近的兩個0和1無疑就是相鄰的0和1了，
解題代碼
def func(x):
"""假定x為64位整數"""
# 從低位向高位掃描
for i in range(64):
# 找出相鄰的一組0和1的位置
if ((x >> i) & 1) != ((x >> (i + 1)) & 1):
# 交換兩個位置的值
return x ^ ((1 << i) | (1 << (i + 1)))
print(bin(func(0b1011))) # 輸出： 0b1101
總結
像這類題目，光是憑想象短時間是不太能找出規律的，所以可以先使用窮舉法通過一些簡單的例子看看是否能找出規律，找到規律后需要再思考下這個規律是否滿足題目的要求，當然如果時間緊迫可以先寫出演算法，后面有時間再來完善和驗證演算法的正確性，交換x中指定兩個位置i和j的位元位使用公式x ^ ((1 << i) | (1 << j))即可，
題目及解題演算法來自：書籍《Python程式員面試寶典》，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/234134.html
標籤：其他
上一篇：二、基本資料型別