这是前两天在知乎上看到的一个问题,作者提出了这样一个问题:
“C语言中不使用选择结构和条件运算符有哪些方法可以判断两个整数的大小?”
不能使用条件运算符(如三目运算符),也不可以使用选择结构。
源问题链接:源问题链接
首先,这个问题是肯定有解的。因为在计算机内部,所有的操作都是逻辑运算(与或非,或者称为布尔运算),
同样地,大小比较的实现,也是由一连串逻辑运算组合而成的。
下面就来讲讲怎么解决这个问题。
开始之前需要特别地注明:回答中限制的操作是+ - << >> & | ^ ~,不允许使用条件选择语句以及逻辑运算符。
问题分析
- 问题的转化
- 转化问题后需要解决的问题
- 解决方法
问题的转化
将比较x > y转换为x-y > 0即可,当x-y<0时,x<y,否则x>y。
//x,y均为int
int t = x - y;
int sign = (t>>31)&1;
如果sign为1,则t<0,否则t>0。
转化问题后需要解决的问题
以上是解决的主要方法,但会遇到一个致命的问题:
overflow,即溢出。
举个例子:
//此处的0x80000000为INT_MIN,为int的下限
int x = 0x80000000, y = 1;
int t = x - y;
int sign = (t>>31)&1;
这段代码执行后不会得到预期的结果sign == 1,而是sign == 0。
这是由于int存在上下限而导致的加减溢出,导致t = INT_MAX,这就是我们需要解决的额外难题。
解决方法
- 有溢出比较,根据不同的情况,判断发生了什么情况的overflow,并做出判断
- 无溢出比较,不使用加减法,从而避免出现overflow
- 无溢出比较,使用加减法,但不处理overflow
以上是一个有序列表,是按照解决问题的复杂度排序的。
其中关于有溢出比较的解决方法Tenma已经详细给出,
详情见知乎:知乎-Tenma的回答
无溢出比较
这里说两种方法,一种是我自己想的,一种是在知乎上看到的更好更巧妙的方法。
先说我的方法,不使用加减法来避免出现overflow。
主要步骤如下:
- 把数字转换为无符号数字,也就是取绝对值
- 比较两个绝对值的大小
- 根据若干条件决定是否需要调换两个数的位置
直接上代码:
#include <stdio.h>
int abs_(int x){
int res = x;
int t = x;
t >>= 31;
res = res ^ t - t;
return res;
}
int isEqual(int a,int b){//equal == 1
unsigned v = a ^ b;
return ((v - 1) >> 31) & ((v >> 31) ^ 1);
}
int getLargerOne(int x,int y){//调用时需要保证x与y均为正数
int t = (x - y)>>31<<31;
printf("%x\n",t);
return x&(~t) | (y&t);
}
void swap(int *a, int *b){
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
int compare(int x, int y){//is x > y then return 1;
int min = 0,max = 0;
//如果存在0x80000000,最小就是它,并且设立flag取消后续操作
/*
if(isMinExist){
min = 0x80000000;
max = anotherOne;
}
*/
unsigned isMinExist = (isEqual(x,0x80000000) | isEqual(y,0x80000000))<<31>>31;
min = 0x80000000 & isMinExist;
max = (x&~(isEqual(x,0x80000000)<<31>>31) | y&~(isEqual(y,0x80000000)<<31>>31))&isMinExist;
//考虑非最大值问题
int a = abs_(x);
int b = abs_(y);
unsigned sa = ((unsigned)x&0x80000000)>>31;
unsigned sb = ((unsigned)y&0x80000000)>>31;
/*
t = a - b
if(a > b && !isMinExist){ //or t > 0
min = y;//b
max = x;//a
}else{
min = x;//a
max = y;//b
}
*/
int t = a - b;
unsigned isLarger = isEqual((t&0x80000000)>>31,0)<<31>>31;
isLarger&=~isMinExist;//如果上面已经操作过了,这里就不应该操作
printf("is a larger than b = %x\n",isLarger == 0xFFFFFFFF);
min = (min&~isLarger) | (y & isLarger | (x & ~isLarger) & ~isMinExist);
max = (max&~isLarger) | (x & isLarger | (y & ~isLarger) & ~isMinExist);
//all done
/*
if(isSameSign){
if(sa == 1) //isAllNeg
isNeedSwap = true;
}else if((max == y && sb == 1) || (max == x && sa == 1)){ //may need swap
isNeedSwap = true;
}
*/
int isSameSign = isEqual(sa, sb);
int isAllNeg = isEqual(sa, 1) & isSameSign;
unsigned isNeedSwap = isAllNeg<<31>>31;//if sa == sb == 1,isNeedSwap = 0xFFFFFFFF;
int condition1 = isEqual(max, y) & isEqual(sb, 1);
int condition2 = isEqual(max, x) & isEqual(sa, 1);
unsigned cond = (condition1 | condition2)<<31>>31;
isNeedSwap |= cond;
isNeedSwap&=~isMinExist;
printf("isNeedSwap = %x\n",isNeedSwap == 0xFFFFFFFF);
int tmin = min,tmax = max;
swap(&tmin, &tmax);
min = (min & ~isNeedSwap) | ((tmin & isNeedSwap) & ~isMinExist);
max = (max & ~isNeedSwap) | ((tmax & isNeedSwap) & ~isMinExist);
printf("smaller = %d, larger = %d\n",min,max);
return isEqual(max,x);
}
int main(){
/*
1.转换为绝对值
2.判断数字大小
3.如果符号不一致,则反转
*/
printf("is x larger than y : %d\n",compare(-2147483644, -2147483648) == 1);
return 0;
}
但需要特别地注意,对INTMIN取绝对值依然是它本身。因此需要对含有INT_MIN的比较做额外的处理。
最后无非就是把流程写成代码,具体流程在代码里面有注释。
效果如图:
更精巧的方法
这是在我写完原回答后的一天看到的,被作者回答思路的精巧所折服。
同样是无溢出比较,而且使用加减法,但不处理overflow。
简要描述如何更精巧地解决,以下是若干条件:
- 函数只需要对符合条件的比较返回1,其余情况不考虑(即丢弃,返回0)
- 1.对于x>0, y<0的情况始终返回1
- 2.如果x > y且x和y的符号相同,无论是否发生overflow,结果都应该是正数(这个可以停下来,自己琢磨一下)
- 3.对于x<0, y>0的情况不考虑,返回0
- 4.对于x == y的情况始终返回0
这时我们就可以逐个解决这些问题。
首先定义函数isGreater(x, y)判断x是否大于y:
int isGreater(int x, int y) {
//codes here
}
将判断正负数的操作转化为判断数字符号位的操作:如(x>>31)&1
所以对于条件1,只需要
int cond1 = ((~x&y)>>31) &1;
当条件1时,cond1将为1,否则为0。
判断两个数符号是否相等
int sign = ~(x^y)>>31;
当符号相同时,sign将为1,否则为0。
其中^操作符为异或操作,已经忘记异或操作的同学可以去百度复习一下。
判断两个数是否相等
比较简单的方法是使用!!(x^y),但回答限制了操作范围,不允许使用逻辑取反符!。
因此可以自己实现一遍逻辑取反,当然了,all bit level。
int getLogicalNeg(int x){
/*
0 --> 1
1 --> 0
other --> 0
*/
int isZero = isEqual(x,0);
return 1&isZero | 0 & ~isZero;
}
实现了逻辑取反后,就可以进行判断了,当然,也有另一种方法判断两个数是否相等:
int isEqual(int a,int b){//equal == 1
unsigned v = a ^ b;
return ((v - 1) >> 31) & ((v >> 31) ^ 1);
}
当参数a == b时,返回1,否则返回0。
这里由于我们需要x == y时返回0,因此可以对isEqual()返回的结果对1异或,即可获得相反的结果。
最后判断x-y的符号
这里使用((x-y)>>31)&1或((x+~y+1)>>31)&1,&1可有可无,因为后面会消掉。
将以上的代码组合即可,下面是代码:
int isGreater(int x, int y) {
/*
返回1(即 x>y)的情形:
1. x>0,y<0
2. x与y同号,相减的结果为正数
*/
int cond1 = ((~x&y)>>31) &1;
int sign = ~(x^y)>>31;
int equal = isEqual(x,y)^1;//x==y --> 0
return cond1 | sign & ~(x-y)>>31 &equal;
// <condition1> <condition2>
}
感兴趣的朋友可以暂时遗忘掉这里所讲述的方法,自己实现一次。
最后测试的时候一定要特别测试几个特殊的值,如INT_MAX和INT_MIN
给出一些测试的值,供大家测试:
====== x ========= y ======
- INT_MIN INT_MIN -
- INT_MIN INT_MAX -
- INT_MIN 0 -
- -100 10 -
- -100 -10 -
- 100 10 -
- 10 100 -
- 10 10 -
- -123 0 -
- 123 0 -
===========================
以上是关于“在C语言中不使用选择结构和条件运算符如何判断两个整数的大小”的三种解决方法,
惊叹于巧妙的实现方法,学习无止境。
这里的排版可能不太好看,可以去知乎看我的回答:知乎-MeetinaXD的回答
觉得还不错的话,在知乎点个赞吧 :)