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

biinn

Post by MatthewGong

P.S.
我这边gcc4.1下， -1234 >> 31 的结果是－1而不是1…… C标准怎么说的呀？我都忘了。

biinn，这样的话
    msb = var2 >> (bit_width -1) - var1 >> (bit_width -1);
是不是应该改为：
   msb = var1 >> (bit_width -1) - var2 >> (bit_width -1);

多谢，Matthew 兄。看来光拍脑袋是不行的啊。

soloforce

大家写得都比我好，我原来的代码居然用了循环，而且没用上减法。。。

2. const int BYTE_BITS=8;
3. const int EQUAL=0;
4. const int MORE=1;
5. const int LESS=-1;
7. int cmp(int a, int b)
8. {
9.     int mask=0x1;
10.     mask<<=BYTE_BITS*sizeof(int)-1;
11.    
12.     // equal
13.     if(!(a^b))return EQUAL;  
15.     // one is positive , while the other is negative
16.     if( (a&mask)^(b&mask) ) return (a&mask) ? LESS : MORE ;
17.        
18.     // check the rest bits
19.     while( !((a&mask)^(b&mask)) ) mask>>=1;
21.     return (a&mask) ? MORE : LESS ;
22. }

复制代码

biinn

Post by Lolita
大家写得都比我好，我原来的代码居然用了循环，而且没用上减法。。。

今天问了我的同事这个问题，她的思路和罗版主的类似。

biinn

Post by Arthur.Echo

1. 
   
2.         i = (((num1 - num2) >> 31) * 2) + ((num2 - num1) >> 31);
   

复制代码

愚钝，看不懂 Arthur 兄的思路。只好用罗版主的数字跑了一下：
num1 = -268435441
num2 = 2147483647
结果 i = -1, result[1]：num1 > num2 ?

MatthewGong

Post by Lolita

1. 
   
2.     // one is positive , while the other is negative
   
3.     if( (a&mask)^(b&mask) ) return (a&mask) ? LESS : MORE ;
   

复制代码

昨天晚上想用“异或”的, 愣是没想起来操作符号是什么。

lolita的位操作******************！承教。

soloforce

Post by biinn
愚钝，看不懂 Arthur 兄的思路。只好用罗版主的数字跑了一下：
num1 = -268435441
num2 = 2147483647
结果 i = -1, result[1]：num1 > num2 ?

貌似也是溢出了。

soloforce

总结一下：
1、不要盲目用减法，因为异号整数相减容易溢出; 确保两数是同号后则可以用减法。
2、负整数右移 ( sizeof(int)*8-1 ) 后，得到的是 -1 而不是 1, 因为负整数右移是算术右移SAR。
3、注意移位运算的优先级比加减法低。
4、不要直接用31, 因为有些系统的int不是32位的。
5、 楼下补充：）

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.     int bit_width, msb, rtnvar;
10.     bit_width = sizeof(int) << 3;   
11.     msb =( var1 >> (bit_width -1) ) - ( var2 >> (bit_width -1) ) ;
13.     if (msb)
14.         rtnvar = msb;
15.     else
16.         rtnvar = var1 - var2;
18.     return rtnvar;
19. }

复制代码

Arthur.Echo

Post by biinn
愚钝，看不懂 Arthur 兄的思路。只好用罗版主的数字跑了一下：
num1 = -268435441
num2 = 2147483647
结果 i = -1, result[1]：num1 > num2 ?

就是没有考虑溢出的问题，再想想

biinn

Post by Lolita
总结一下：
1、不要盲目用减法，因为异号整数相减容易溢出; 确保两数是同号后则可以用减法。
2、负整数右移 ( sizeof(int)*8-1 ) 后，得到的是 -1 而不是 1, 因为负整数右移是算术右移SAR。
3、注意移位运算的优先级比加减法低。

这三点就是我从这道题中学到的东西，谢谢大家。

MooreChow

拜各位了，看都看了半天……思路是在叫绝