2009年5月5日星期二

不使用逻辑运算求得两数的最大值

下面将介绍两个不使用逻辑运算求两数最大值的算法:
 
算法一
 

int max(const int *p, const int *q)

{

    int array[] = {*p, *q};

    return array[(unsigned)(*- *q) >> (sizeof(int) * 8 - 1)];

}

算法二

int max(const int *p, const int *q)

{

    return (((*+ *q) + abs(*- *q)) / 2);

}

分析:

算法一利用计算机系统中数的存储方式为其补码这一特性。补码的最高位为符号位,如果为正,则最高位为0,反之则为1。通过右移运算得到其最高位的值。之所以转换为无符号数是因为无符号数右移时左边高位移入0,而对于有符号数,当原来符号位为0(该数为正)时左边也是移入0,但如果符号位为1,时左边移入0还是1则不确定,取决于所用的计算机系统。

当*p大于*q时,右移后得0,则函数返回数组中下标为0的元素,即*p;反之则*q。

缺点:如果*p与*q之差大于等于2^31,则算法出错。

算法二则利用<math.h>中的函数abs()。

如果a大于b,则

abs(a - b) = a - b

(a + b + abs(a - b)) / 2 = (a + b + a - b) / 2 = a

如果a小于b,则

abs(a - b) = b - a

(a + b + (abs(a - b)) /2 = (a + b + b - a) / 2 = b

缺点:要调用库函数。(a + b + abs(a - b))使a, b中的最大值的绝对值要小于2^30,否则可能会溢出(考虑有符号数的表示范围为-2^31~2^31-1)。

注:C99符加的标准ANSI C库中abs()包含在中。

没有评论: