Re: [問題]比大小求最小值
考慮到 M 一定不止一個，如果沒有其他條件的話，
我想一個比較直觀但會有很多 if 的解法，不是漂亮的數學解。步驟只有兩個。
第一步：
把 L、U、N 以二進位表示並對齊，截出開頭 U 比 L 長的那部分，叫做 head。
此時有兩種情況：
U 比較長：會產生長度為 len(U) - len(L) 的區間。如
110001001001011110
1101100111000100010011 => 1101
^^^^
一樣長：跳過起始一樣的部分，截下再次遇到 L 的 1 之前的區間。如
1101100111000100010011
1101110001001001011110 => 10
^^
第二步：
將 N 位置相對應的區間拿出來 bit invert(0->1, 1->0)，先叫 nx，此時有三種情況：
nx > head: nx &= head，變成以下其中之一。
nx = head: U 往下走，跳過 0，若 N 同位置也是 1 時，M 該位為 0，以下補 1。
若走完沒遇到上述情況，M = U - 1
nx < head: 讚，後面全部補滿 1 就是 M。
雖然轉了 U、L，這就是我推文說的小於 U 找 M，不知道有沒有 bug = =
如果沒錯的話複雜度 O(log(U))。
--
金木水火土
鍂林沝炎圭
鑫森淼焱垚
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.194.2.92
※ 編輯: ck574b027 來自: 123.194.2.92 (11/06 03:35)
推
11/06 16:04, , 1F
11/06 16:04, 1F
→
11/06 18:16, , 2F
11/06 18:16, 2F
討論串 (同標題文章)
Python 近期熱門文章
PTT數位生活區 即時熱門文章
