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

yuxh

1. #define SHIFT (sizeof(int) * 8 - 1)
   
2. 
   
3. int max(int x, int y)
   
4. {
   
5.         unsigned int m, n, p;
   
6.         int ary[2] = {x, y};
   
7. 
   
8.         m = x ^ y;
   
9.         n = x & m;
   
10.         p = y & m;
    
11.         m = (m >;>; SHIFT) & 1;
    
12. 
    
13.         return ary[(p && !(n / p) ) ^ m];
    
14. }
    

复制代码

嘿嘿~~~

bleem1998

强悍呐看不太明白
不过(p && !(n / p) ) ^ m这句使用了隐含条件判断吧

yuxh

那这样呢？

1. #define SHIFT (sizeof(int) * 8 - 1)
   
2. 
   
3. int max(int x, int y)
   
4. {
   
5.         unsigned int m, n;
   
6.         int ary[2] = {x, y};
   
7. 
   
8.         m = x ^ y;
   
9.         m = m & ~(m / 2) & ~(m / 4);
   
10.         n = m | 0x01;
    
11. 
    
12.         return ary[ ((x & n) + n / 2) / n ^ !((m >;>; SHIFT) & 0x01)];
    
13. }
    

复制代码

bleem1998

看不懂
给虾米们讲讲吧

zleil

楼上的能否详细解释一下？？？

bleem1998

我解释什么

yuxh

原来的程序有个BUG，现在修正了
刚吃完饭，现在又要开会，等会儿再来解释

bleem1998

日程排列的很紧凑嘛
中午是阴阳交替之时
要注意休息阿

yuxh

说明一下吧：
这个算法是企图对x、y按位比较，简单地说，如果不考虑+、-号，则在第一次出现两者的位不相同时，该位是1的值比较大，如
00001111111100001111000011110000
00001110111100111111110011111010
左数第8位上，前者是1，后者是0，所以前者比后者大。
对于有符号的情况我们在后面再分析。
1、首先，x^y把x、y中不相同的位置1了，假设x^y=0...01X...X，后面的X表示任意的0或1，这表示在1所在的位置之前的位x、y是相等的，在这一位上或者x为1、y为0；或者x为0、y为1；我们主要是要确定哪一个为1。可惜的是我们无法得到0...010...0这个数以及1所在的位号(不然就要用循环去确定，这不符合题目的要求)
2、设m=x^y，则当x >; y时，x在该位上为1，所以x  & m = 0...01X...X，所以(x & m) / m 大约为1(注意“大约”，因为有等于0的可能存在，我们等会儿把它排除掉)；当x < y时，x & m = 0...00X...X，所以(x & m) / m = 0，现在我们的程序好象可以工作了。。。
3、但是，有一个BUG，如果m == 0呢？(x & m) / m会溢出!m = 0说明x=y，现在的处理是m = m | 0x01，即把最后一位置1，使m >;= 1!
这样当m == 0时，我们不管(x & m) / m算出来的是个啥结果，反正哪个都一样(x == y嘛!)，而m >; 0时，最后一位是不是1不影响我们的计算结果了!
4、前面说过这里还有个BUG，即当x在该位上为1时，我们不能确定(x & m) / m 一定 = 1，因为尽管x & m在该位上也为1，但x & m还是有可能 < m的(还是感叹如果我们能得到0..010...0这个数就好了!)。现在的处理是m = m & ~( m / 2 ) & ~( m / 4)，把m这个数变成0...0100X...X，算式也修正为((x & m) + m / 2) / m，这个可以满足我们的要求了
5、最后再来考虑一下有符号的情况
设t=((x & m) + m / 2) / m，f = m的第一位=m >;>; SHIFT(上面的&0x01其实可以不要)
则当m = 0时，表示x、y同号，这时按上面的方式确定最大值
当m = 1时，x、y一正一负，t表示x首位，为1则x < 0，为0则x >;= 0
总的说来：
(1)当f=0，t=0时最大值为y -----1
(2)当f=0，t=1时最大值为x -----0
(3)当f=1，t=0时最大值为x -----0
(4)当f=1，t=1时最大值为y -----1
显然结果是t ^ !f
(如果不让用!那就是t ^ (~f & 0x01))

yuxh

程序才几行，说明倒写了一大堆!呵呵~~~
大家看看有没有什么地方没想到的？