xy0v0's Blog

Back

对于无符号数 AA 和 BB ,判断 A<BA < B 是否成立

  1. 首先对 AA 取 NOT 得  A~A
  2. 将取反后的值与第二个输入  BB  相加
  3. 检查是否有进位输出

我们可以利用补码的性质来判断:

NOT(A)+1=2n−A\text{NOT}(A) + 1 = 2^n - A

有 n=8n=8

接下来对 A<BA<B进行变形:

A<B⇒A−B<0⇒A+(−B)<0A < B \Rightarrow A - B < 0 \Rightarrow A + (-B) < 0

现在等价于检查 A+NOT(B)+1A+\text{NOT}(B)+1 的最高位是否为 1,而又有:

NOT(A)+B=(2n−1)−A+B=(2n−1)+(B−A)\text{NOT}(A) + B = (2^n - 1) - A + B = (2^n - 1) + (B - A)

B>AB > A时,(B−A)>0(B - A) > 0,NOT(A)+B\text{NOT}(A) + B 必定产生进位,由此说明该方案可行