不使用比較和條件判斷實現min函數的一種方法

• 2022 年 5 月 5 日
• 筆記

不使用比較和條件判斷實現min函數，參數為兩個32位無符號int。

面試的時候遇到的題目，感覺很有意思。

搜了一下多數現有的解法都是僅有兩種限制之一，即要麼僅要求不能使用比較，要麼僅要求不能使用條件判斷，於是打算寫一下一種能兼顧兩種限制的實現方法。

需要注意的是，條件判斷當然也包含三目表達式、switch-case語句甚至abs等隱含條件分支的語法糖或標準庫函數，除非能夠不藉助條件分支實現（例如沒有條件分支的abs：參考鏈接）。

Solution

基本思想很簡單，在二進位表示下從高位開始逐位比較，相同的位置可以直接忽略，直到遇到第一個不相同的位置，大小關係就決定了。譬如比較

a=011010
b=010110

時，從高位至低位比較到第三位時兩數不同。此時必定是較大者 a 此位為 1，較小者 b 此位為 0，記此位為符號位 sign_a, sign_b。

實際上此時我們已經分辨出兩數的大小，再想辦法將較大者的資訊抹掉即可。方法是分別將 a, b 剩餘的每一位都與符號位相或，此時較大者 a 後半部分變為全 1，而較小者 b 不變，將兩者相與，其結果等於 b，求得min。

在實際實現時可以使用位運算消除條件分支，具體可以參考程式碼。

"""
myMin(0b011010, 010110)

(1)
011010  A
010110  B
^ same 0 vs. 0

(2)
011010  A
010110  B
 ^ same 1 vs. 1

(3)
011010  A
010110  B
  ^ diff, sign_A=1, sign_B=0

(4)
011110  A'
010110  B'
   ^ A_i |= sign_A, B_i |= sign B

(5)(6)
011111  A''
010110  B''
     ^ A_i |= sign_A, B_i |= sign B

A'' & B'' = B
"""

def myMin(a, b):
    found = 0
    sign_a, sign_b = 0, 0
    for i in range(32, -1, -1):
        bit = 1 << i
        xa, xb = (a & bit) >> i, (b & bit) >> i

        # if not found:
        #   d = xa ^ xb
        # else:
        #   d = 0
        d = (not found) & (xa ^ xb)

        # if xa ^ xb == 1:
        #   found = 1
        found |= xa ^ xb

        # if d:
        #   sign_a, sign_b = xa, xb
        sign_a |= d & xa
        sign_b |= d & xb

        a |= sign_a * bit
        b |= sign_b * bit
    return a&b

# 用於生成隨機測試用例測試正確性
import random, time
loop = 0
MAX = 1<<32
while True:
    a, b = random.randint(0, MAX), random.randint(0, MAX)
    if myMin(a, b) != min(a, b):
        print(f"min({a}, {b}) = {min(a, b)} != {myMin(a, b)}")
        break
    loop += 1
    print(loop, end='\r')
    time.sleep(0.001)