【新人debut】【数学】在计算机中如何不使用比较符定义比较符？

需求：我们把视作是一个函数，关系式成立时返回1，不成立时返回0，并且定义它们的函数体禁止使用它们。

解决方案：在正式开始之前，介绍一下基础知识——整数类型（byte，short，int，long，long long等）在计算机中的表示。

byte：1位符号位+7位数值位，共8位；

short：1位符号位+15位数值位，共16位；

int：1位符号位+31位数值位，共32位；

long：1位符号位+63位数值位，共64位。

它们的共同特点是，用比特表示补码形式。最高位为符号位，0为正，1为负（浮点数采用的阶码是移码，恰好相反），其余位为数值位。

接着，我们观察到一个事实，符号位为0，原数可以是正数，也可以是0，但是符号位为1对应全部负数。

因此，我们得出下面的定理：

定理1：设x是整数，那么x<0当且仅当符号位为1。

因此，我们给出了判断x<0的代码——直接返回符号位（这里是伪代码，C++并没有getSignBit这个函数，只是为了大家容易理解）。

bool isNeg(int x){
    return getSignBit(x);
}

然后我们开始思考大一点的问题——如何判断x<y？

在数学上，我们直接计算x-y<0就可以了，但是这里有个陷阱。

比方说，

那么：

x<0，y>0，x-y<0理应返回1（true），但是却返回了0（false），为什么呢？

显然，是因为下溢了。

我们必须处理下溢的情况。

在上面的情况中，我们有x<0，y>0，所以第一个处理思路就是分类讨论。

我们把x<0，y>=0的情况单独拿出来讨论。显然，这时候必然有x<y。分类出这种情况的代码如下：

bool operator <(int x,int y){
    if(isNeg(x) && !isNeg(y)){
        return 1;
    }else{
        return isNeg(x-y);
    }
}

还有另一种溢出——上溢，这时有x>0，y<0，x-y<0，于是本应该为false却返回了true，解决方案如下：

bool operator <(int x,int y){
    if(isNeg(x) && !isNeg(y)){
        return 1;
    }else if(!isNeg(x) && isNeg(y)){
        return 0;
    }else{
        return isNeg(x-y);
    }
}

剩下的情况，x和y是同号的。在同号的情况下，x-y一定不会出现溢出，所以x-y<0的结果总是正确的。

接下来我们思考一下，如何将这三种情况合并呢？

首先，我们考虑x>=0,y<0的情况，它必然返回0，我们可以用and来短路，然后取反得到返回结果，否则考虑接下来的情况。

接下来，如果x<0，且y>=0，则返回true，否则进入下一步，我们用或的符号来短路。

下一步就简单了，计算x-y<0，因此最终的结果为：

稍微交换个顺序，得到：

于是计算过程的代码为

bool operator <(int x,int y){
    return isNeg(x) && !isNeg(y) || isNeg(x-y) && (!isNeg(y) || isNeg(x));
}

有什么更容易理解的方法呢？我们观察到，需要分类讨论的两个情况，x和y都有且只有一个为负数，并且x<0时返回1，因此我们可以用异或运算简化为：

​bool operator <(int x,int y){
    if(isNeg(x) ^ isNeg(y)){
        return isNeg(x);
    }else{
        return isNeg(x-y);
    }
}

然后进行下一步简化

bool operator <(int x,int y){
    return isNeg(x) ^ isNeg(y) ? isNeg(x) : isNeg(x-y);
}

此处备注：问号表达式都可以把问号换成&&，同时把相应的冒号换成||，但是这里为了可读性，选择用问号表达式来表达。

接下来，我们来讨论更大的问题——如何用x<y来定义其它比较运算符？

事实上，如下定义就可以了：

在计算机中，在函数体中交换两个数无非就是把地址换一下，压根不消耗任何时间。

而至于等于和不等于两个符号，在C++中非0数可以直接转化成true，所以我们直接返回(bool) x-y和!((bool) x-y)就可以了。

内部转换器的实现，可以对所有位数求or运算，得到转化结果。

由于时间限制，此处不多赘述。

总之，只要抓住了“int x<0当且仅当x的符号位是1”这个要点，定义比较符就是这么简单。