不用判断语句，求两个数的最大值

2025-01-22 技术教程

我之前看到这道题的时候是一道笔试题的。当时不会做，写了一个用逻辑表达式的答案，但是我感觉应该不符合题目的意思。但是又很想知道这道题的答案，然后我就去百度谷歌了一番。但是好像百度谷歌也找不到我想要的那种。然后自己想了好久。然后想出了一个我比较满意的答案。先把自己写的源码写上来。

inttakeOfFlag(intnumber){returnnumber&0x7FFFFFFF;}intmax(inta,intb){intary[]={a,b};intreta=a+0x80000000;intretb=~(b+0x80000000)+1;intc=(~((b&(takeOfFlag(~b)+1))|(reta&retb)|((reta|retb)&(takeOfFlag(reta)+takeOfFlag(retb))))>>(sizeof(int)*8-1))&0x1;returnary[c];}

这段程序测试了很多数值都没问题了。包括边缘测试那些。这样写程序可读性是非常差的。现在来解释下为什么这样写可以得出比较大的数。首先在计算机里面数字的存储是用补码的形式存储的。在类型转换的时候数值在内存当中是不变的。补码是如何就是如何。只是可能让计算机认为的位数不一样。正数的补码是和自身一样保持不变。然后负数的补码是符号位不变其他数值按位取反加1。然后在一个int型当中用一个较大的数减去一个很小的负数就会溢出。然后那个负数的补码非符号位算法好像是0x7FFFFFFF - x + 1 = 0x80000000 - x,所以说负数的非符号位表示的是比0x80000000大多少。如果把所有的int都转成比0x80000000大多少的一个unsigned int类型，那么这个数字大的就是比较大的数字。转化成long long相减看符号位就能看到，但是这么说来的话就是你允许溢出到更高的位。但是我好像有种强迫症。我想找到不会溢出到更高位的方法。如何比较两个认定为是正数的大小呢？这时好像已经没之前的复杂了。因为不用考虑两个相减的数有负数的情况。我想到了两个数相减的方法。但是我不允许看到更高的位啊。后来想到两个数相减相当于一个正数加上一个负数。虽然一个是正数一个是负数。但是一正一负还是确定的。然后两个数相加的和和两个补码相加的和得到和的补码一样的。所以就把他们都转成补码。一个正数和一个负数相加如果是正数就是a大如果是负数就是b大。但是一个正数和一个负数相加如何才能得到正数呢？后来想到了方法符号位相加是负的只有两个补码的非符号位相加有溢出然后让符号位变为0时得到的才是正数。但是如何判断两个数相加会有溢出呢？首先两个最高位都是1或者是其中一个一除开最高位相加有进位的情况下才会出现溢出。后来经过测试代码的时候发现那个数值0x80000000有点特殊。然后就对他做了特殊处理也就是那个b & (takeOfFlag(~b) + 1)的由来。因为0x80000000在int里面永远都是最小的而只有它在b & (takeOfFlag(~b) + 1这个运算最高位是1的。

如果允许溢出到更高位我也写出了一个比较简洁的代码

intmaxEdition2(inta,intb){intary[]={a,b};longlongreta=a+0x80000000;longlongretb=b+0x80000000;returnary[((reta-retb)>>(sizeof(longlong)*8-1))&0x1];}

我看到很网上的一些帖子上面出现了逻辑运算符都是不允许的。如果允许使用逻辑运算符我也想到了一个更加简洁的方法。

intmaxEdition3(inta,intb){intret=a;(b>a)&&(ret=b);returnret;}

上面这3个函数都是经过比较多的测试是没问题的了。

另外还有一个我认为也是比较好的方法。好像思路和我的差不多都是两个数相减针对溢出的问题进行特别处理。在一个论坛上面看到的我把那个回复的原文贴上来吧。

win_hate回复于：2005-06-07 22:24:04

这段代码的简单说明：

#defineMASK0x7fffffffintmax(intx,inty){intz;z=(x>;>;31)-(y>;>;31)+(((x&MASK)-(y&MASK))>;>;31);z=(z+1)*(z+2)*(3-2*z)/6;returnz*x+(1-z)*y;}

思路：计算x-y的差，自己处理进位：

第一行：

(((x&MASK)-(y&MASK))>;>;31)计算低31位相减后的符号，0或－1。也可以看成低31位相减后对高位的借位。

(x>;>;31)-(y>;>;31)是第32位的差，带符号扩展

z=(x>;>;31)-(y>;>;31)+(((x&MASK)-(y&MASK))>;>;31);

处理进位.

第二行：

可以分析出，z有四种可能的值，1，0，-1,-2。其中

1，0对应x>;=y，－1，－2对应x<y

我对z作一个修正，即一个映射，把1,0对应为1;－1，－2对应为0。映射可用Lagrange插值公式得到。

第三行：
还是Lagrange插值，1->;x,0->;y

ps>;第二行也可以直接从最高位判断正负。