不使用比较和条件判断实现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) 可以看到，在实现时我们的逻辑实际上是等价于一些条件分支的，这是因为条件分支仅用来控制运算而未控制程序流程，因此可以相互代替。举个例子，对于带有条件分支的代码 ans = a if flag else b（ans = flag ? a : b in C++/Java），我们可以写成
mask = (1 << 32) - 1; // 0b111111...111 ans = (flag * mask) & a + (!flag * mask) & b; 等等。而对于 if (flag) {return;} 这样的代码块，这种 trick 就很难有什么直接应用了。
