一道面试题：编写一个函数比较两个整数大小，但不能使用任何比较操作符

soloforce

CSDN上炒得火热（汗）的一道老面试题，不过我看又对又好的答案还没出现。。。

[color="Red"]编写一个函数比较两个整数大小，但不能使用任何比较操作符

biinn

好玩，我试一下：

2. int comp_int(int var1, int var2)
3. /* return value < 0: means var1 < var2;
4. *              = 0: means var1 = var2;
5. *              > 0: means var1 > var2;
6. */
7. {
8.         return (var1 - var2);
9. }

复制代码

soloforce

Post by biinn
好玩，我试一下：

1. 
   
2. int comp_int(int var1, int var2)
   
3. /* return value < 0: means var1 < var2;
   
4. *              = 0: means var1 = var2;
   
5. *              > 0: means var1 > var2;
   
6. */
   
7. {
   
8.         return (var1 - var2);
   
9. }
   

复制代码

有没有考虑溢出情况？
var1 = -268435441
var2 = 2147483647

biinn

呦，该打！
太晚了，我先睡觉，明天再想。。。;-)

yist111

就算正确返回我还是得用比较符判断是否大于小于等于0啊

DoDo

不知道 "不能使用任何比较操作符" 的概念有多大, 暂时理解为不使用 >, <, ==, !=
下面是判断大于的函数, 类似的可写出其它几种操作
[PHP]
#include <stdio.h>

/* return 1 if a > b */
int greater(int a, int b)
{
        int sa = a >> 31; /* sign of a */
        int sb = b >> 31; /* sign of b */
        if (!sa && sb) return 1; /* a >= 0 && b < 0 */
        if (sa && !sb) return 0; /* a < 0 && b >= 0 */

        int c = a - b;
        if (!c) return 0; /* a == b */

        int sc = c >> 31; /* sign of (a - b) */
        return !sc;
}
int main(void)
{
#define N 13
        int nums[N][2] = {
                {1, 1},
                {1, 0},
                {1, -1},
                {0, 1},
                {0, 0},
                {0, -1},
                {-1, 1},
                {-1, 0},
                {-1, -1},
                {1, 2},
                {2, 1},
                {-1, -2},
                {-2, -1}
        };
        int i;
        for (i = 0; i < N; i++) {
                int a = nums[0];
                int b = nums[1];
                printf("%2d > %2d: %d\n", a, b, greater(a, b));
        }
        return 0;
}
[/PHP]

Arthur.Echo

1. #include <stdio.h>
2. #include <stdlib.h>
4. int main(int argc,char *argv[])
5. {
6.         int num1,num2;
9.         if(argc != 3)
10.         {
11.                 printf("Usage: cmp_int num1 num2\n");
12.                 exit(1);
13.         }
15.         num1 = atoi(argv[1]);
16.         num2 = atoi(argv[2]);
18.         num1 -= num2;
20.         if(num1 >> 31)
21.                 printf("The first number is less than the second one\n");
22.         else if(num1)
23.                 printf("The first number is greater than the second one\n");
24.         else
25.                 printf("The two numbers are equal\n");
28.         return 0;
29. }

复制代码

MatthewGong

提取符号位，如果异号，显然知道谁大谁小；然后在两者同号的情况下，取其差值的符号位来判断谁大谁小。也许可以避开溢出的问题。

2. #include <stdio.h>
4. int cmp( int a, int b )
5. /* return value 1: means a > b;
6. *                    0: means a = b;
7. *                   -1: means a < b;
8. */
9. {
10.   const int s = sizeof( int ) * 8 - 1;
11.   int sa = a >> s;
12.   int sb = b >> s;
13.   if (sa)
14.   {
15.       if (!sb)
16.         return -1;
17.   }
18.   else if (sb)
19.   {
20.       return 1;
21.   }
22.   if ( (b-a) >> s )
23.     return 1;
24.   else if ( (a-b) >> s )
25.     return -1;
26.   else
27.     return 0;
28. }
30. int main()
31. {
32.   int a, b;
33.   scanf("%d %d", &a, &b);
34.   switch ( cmp( a, b ) )
35.   {
36.   case 1:
37.     printf( "%d > %d\n", a, b );
38.     break;
39.   case 0:
40.     printf( "%d = %d\n", a, b );
41.     break;
42.   case -1:
43.     printf( "%d < %d\n", a, b );
44.     break;
45.   default:
46.     break;
47.   }
48.   return 0;
49. }

复制代码

参考：高等教育自学考试计算机原理冲刺模拟试卷
……
47.在计算机中，由于机器码的位数通常是给定的，因此计算机中数的表示范围(允许取值范围)是有限的。若两数进行加减运算的结果超出给定的取值范围就称为溢出。当计算过程中出现溢出时，必须及时处理。定点机如出现溢出，则要停止运算，进行中断处理。为了判断“溢出”是否发生，可采用两种检测方法：
……
（2）单符号位操作检测方法。这种判断溢出的方法是当操作数中的加数与被加数符号相同时，若运算结果的符号与操作数的符号不一致，则表示溢出；否则，表示没有溢出。而当加数和被加数符号不同时，相加运算的结果是绝对不会溢出的。
……

http://www.sooxue.com/kspx/zxks/zlst/200511/18196_9.html

P.S.
才发现跟DoDo学长的方法一样，但我采用strcmp的接口模式。接口不同而已。

根据楼下biinn的思路进行了修改。

2. #include <stdio.h>
4. int cmp( int a, int b )
5. /* return value 1: means a > b;
6. *              0: means a = b;
7. *             -1: means a < b.
8. */
9. {
10.     const int bit_width = ( sizeof( int ) << 3 ) - 1;
11.     int rslt = ( a >> bit_width ) - ( b >> bit_width );
12.     if ( !rslt )
13.     {
14.         rslt = (( a - b ) >> bit_width ) - (( b - a ) >> bit_width );
15.     }
16.     return rslt;
17. }
19. int main()
20. {
21.     int a, b;
22.     while (1)
23.     {
24.         scanf( "%d %d", &a, &b );
25.         switch ( cmp( a, b ) )
26.         {
27.         case 1:
28.             printf( "%d > %d\n", a, b );
29.             break;
30.         case 0:
31.             printf( "%d = %d\n", a, b );
32.             break;
33.         case - 1:
34.             printf( "%d < %d\n", a, b );
35.             break;
36.         default:
37.             break;
39.         }
40.     }
41.     return 0;
42. }

复制代码

biinn

Post by Lolita
有没有考虑溢出情况？
var1 = -268435441
var2 = 2147483647

Please check this version:

2. int comp_int(int var1, int var2)
3. /* return value < 0: means var1 < var2;
4. *              = 0: means var1 = var2;
5. *              > 0: means var1 > var2;
6. */
7. {
8.     int bit_width, msb, rtnvar;
10.     bit_width = sizeof(int) << 3;   
11.     msb = var2 >> (bit_width -1) -
12.           var1 >> (bit_width -1);
14.     if (msb)
15.         rtnvar = msb;
16.     else
17.         rtnvar = var1 - var2;
19.     return rtnvar;
20. }

复制代码

DoDo

to MatthewGong 兄:
从你的资料来看, 应该称呼我为学弟才对