不使用比较和条件判断实现min函数的一种方法

不使用比较和条件判断实现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)