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

Arthur.Echo

1. #include <stdio.h>
2. #include <stdlib.h>
4. int main(int argc,char *argv[])
5. {
6.         int num1,num2;
7.         int i = 0;
8.         int tok =0;
10.         char result[3][32];
12.         if(argc != 3)
13.         {
14.                 printf("Usage: cmp_int num1 num2\n");
15.                 exit(1);
16.         }
19.         num1 = atoi(argv[1]);
20.         num2 = atoi(argv[2]);
22.         sprintf(result[0],"%d = %d",num1,num2);
23.         sprintf(result[1],"%d > %d",num1,num2);
24.         sprintf(result[2],"%d < %d",num1,num2);
26.         printf("The lagest int number is %d\n",~(1 << (sizeof(int) * 8 - 1)));
27.         printf("The lest int number is %d\n",1 << (sizeof(int) * 8 - 1));
29.         tok = (num1 >> 31) ^ (num2 >> 31); // = 0 if they have the same tok, else =-1;
31.         i = (((num1 >> 31) & tok) * 2) + ((num2 >> 31) & tok) + ((((num1 - num2) & (~tok)) >> (sizeof(int) * 8 - 1)) * 2) + (((num2 - num1) & (~tok)) >> (sizeof(int) * 8 - 1));
33.         printf("Result: %s\n",result[-i]);
35.         return 0;
36. }

复制代码

Arthur.Echo

Post by Arthur.Echo

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main(int argc,char *argv[])
   
5. {
   
6.         int num1,num2;
   
7.         int i = 0;
   
8.         int tok =0;
   
9. 
   
10.         char result[3][32];
    
11. 
    
12.         if(argc != 3)
    
13.         {
    
14.                 printf("Usage: cmp_int num1 num2\n");
    
15.                 exit(1);
    
16.         }
    
17. 
    
18. 
    
19.         num1 = atoi(argv[1]);
    
20.         num2 = atoi(argv[2]);
    
21. 
    
22.         sprintf(result[0],"%d = %d",num1,num2);
    
23.         sprintf(result[1],"%d > %d",num1,num2);
    
24.         sprintf(result[2],"%d < %d",num1,num2);
    
25. 
    
26.         printf("The lagest int number is %d\n",~(1 << (sizeof(int) * 8 - 1)));
    
27.         printf("The lest int number is %d\n",1 << (sizeof(int) * 8 - 1));
    
28. 
    
29.         tok = (num1 >> 31) ^ (num2 >> 31); // = 0 if they have the same tok, else =-1;
    
30. 
    
31.         i = (((num1 >> 31) & tok) * 2) + ((num2 >> 31) & tok) + ((((num1 - num2) & (~tok)) >> (sizeof(int) * 8 - 1)) * 2) + (((num2 - num1) & (~tok)) >> (sizeof(int) * 8 - 1));
    
32. 
    
33.         printf("Result: %s\n",result[-i]);
    
34. 
    
35.         return 0;
    
36. }
    

复制代码

我自己测了一下，没有发现问题，溢出解决了，没有用到比较操作符和if、switch等
大家找找问题看，谢谢

soloforce

强啊！ 连判断语句都不用了。。。。

zyobi

#include <iostream.h>
int main()
{
        int a, b;
        cin >> a >> b;
        if(a - b)
        {
                if((int)(a/b))
                        cout << "a > b\n";
                else
                        cout << "a < b\n";
        }
        else
        {
                cout << "a=b\n";
        }
        return 0;
}

ywchen2000

开眼界了.呵呵呵呵

biinn

Post by Arthur.Echo

1. 
   
2. tok = (num1 >> 31) ^ (num2 >> 31); // = 0 if they have the same tok, else =-1;
   
3. i = (((num1 >> 31) & tok) * 2) + ((num2 >> 31) & tok) + ((((num1 - num2) & (~tok)) >> (sizeof(int) * 8 - 1)) * 2) + (((num2 - num1) & (~tok)) >> (sizeof(int) * 8 - 1));
   

复制代码

这个最强！
不过看不懂算法，求Arthur兄讲解一下 :-)

Arthur.Echo

1. tok = (num1 >> 31) ^ (num2 >> 31); // = 0 if they have the same tok, else =-1;

复制代码

这一条代码是判断两个数的符号的，如果两个数同号则结果为0x00000000，如果异号结果则为0xffffffff.

1. i = (((num1 >> 31) & tok) * 2) + ((num2 >> 31) & tok) + ((((num1 - num2) & (~tok)) >> (sizeof(int) * 8 - 1)) * 2) + (((num2 - num1) & (~tok)) >> (sizeof(int) * 8 - 1));

复制代码

这条语句分两部分：
第一部分是：

1. (((num1 >> 31) & tok) * 2) + ((num2 >> 31) & tok)

复制代码

处理异号的情况，此时tok=0xffffffff，这样后一部分就不起作用了，因为它们都&(~tok).
第二部分是：

1. ((((num1 - num2) & (~tok)) >> (sizeof(int) * 8 - 1)) * 2) + (((num2 - num1) & (~tok)) >> (sizeof(int) * 8 - 1));

复制代码

处理同号的情况，此时tok=0x00000000，这样前一部分就不起作用了，因为它们都&tok。
这样同号异号分开处理就可以处理异号相减所发生的益处的情况。

soloforce

Arthur.Echo 兄的解法当真非常巧妙！鬼斧神工了，呵呵