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

linux_newbie

[quote]原帖由 "FH"]楼上的别添乱了，前边已经说过多次溢出的问题了，你没看？[/quote 发表：


哈哈，确实如此。再来一个。
上面那个算法有问题，由于直接调用了减法表达式，因此会出现溢出。
下面这个是修正的算法：
将一个int分成两部分，最高位为符号位，剩下的31位为负载部分。
符号位通过signed_bit得出，为0（如果>;=0)或者为1（< 0)
负载部分通过value_stuff得出，介于0到0x7FFFFFFF之间，总为正数。
value_diff宏将两个数的负载部分进行减法运算（由于负载在0-0x7FFFFFFF之间且总为正数，因此不可能溢出），为0表示计算后的结果为正数，则x的负载大于或者等于y，否则x的负载小于y。

然后预先建立一个3维数组：
对于的维分别代表：

signed_bit(x), signed_bit(y), value_diff(x, y)

然后给这个数组初始化：

x,                //000 x为正数，y为正数，x负载>;=y， 那么x为最大值
y,                //001 x为正数，y为正数，x负载<y， 那么y为最大值
x,                //010 x为正数，y为负数，那么x为最大值 （无需考虑负载部分）
x,                //011 x为正数，y为负数，那么x为最大值（无需考虑负载部分）
y,                //100 x为负数，y为正数，那么y为最大值（无需考虑负载部分）
y,                //101 x为负数，y为正数，那么y为最大值（无需考虑负载部分）
x,                //110 x为负数，y为负数，x负载>;=y， 那么x为最大值
y                //111 x为负数，y为负数，x负载<y， 那么y为最大值

剩下就是分别得到3个维的index，并返回数组中的值。

1. 
   
2. 
   
3. #define signed_bit(x) (( (x) & 0x80000000) >;>; 31)
   
4. #define value_stuff(x)     ( x & 0x7FFFFFFF)
   
5. 
   
6. #define value_diff(x, y) signed_bit( value_stuff(x) - value_stuff(y) )
   
7. 
   
8. 
   
9. int Max( int x, int y)
   
10. {
    
11.   int nums[2][2][2] =
    
12.   {
    
13.                 x,                //000
    
14.                 y,                //001
    
15.                 x,                //010
    
16.                 x,                //011
    
17.                 y,                //100
    
18.                 y,                //101
    
19.                 x,                //110
    
20.                 y                //111
    
21.   };
    
22. 
    
23. 
    
24.   int idx0 = signed_bit(x);
    
25.   int idx1 = signed_bit(y);
    
26.   int idx2 = value_diff(x, y);
    
27. 
    
28.   return nums[idx0][idx1][idx2];
    
29. }

复制代码

JohnBull

原帖由 "svenwang" 发表：
int max(int a, int b)
{
int pair[2] = {a, b};
return pair[a < b];
}

I like this answer.

ecloud

楼上的，你认为出现一个“<”复合题意吗？
我觉得这个不行，由于C中使用数字作为真假，所以只要有任何得比较运算符就可以理解为做了判断
我觉得svenwang的方法有点偷换概念了
个人认为：
位运算由于硬件体制的问题，难免出现各种溢出现象
还是FH的模拟电路方法是正解，不知道CPU中的比较门电路的数学原型是不是就是这个样子的
估计这个面试单位是Intel的核心开发部 -_-!

cellar

70年代 09:47:12
两个int类型的数据，不用任何的判断语句如if、switch、?:等，找出其中的大值
面试题，你答一下
蚊见蚊爱 09:48:50
考，这是编程的艺术上的课后题
蚊见蚊爱 09:48:57
用绝对值做
蚊见蚊爱 09:49:04
27分难度
蚊见蚊爱 09:49:24
绝对值函数就是一个if的组合函数
蚊见蚊爱 09:49:34
还有什么话说？
70年代 09:49:24
具体说说
蚊见蚊爱 09:52:04
x/2+y/2+abs(x/2-y/2)

yuxh

1、在不考虑溢出的情况下，unsigned int z=((x-y)>;>;31)&1的值有两种可能，x>;=y时为0，x<y时为1，所以当x>;=y时(1-z)*x+z*y的值为x，当x<y时其值为y，所以(1-z)*x+z*y就是x，y的最大值。函数如下：

1. int max(int x,int y)
   
2. {
   
3.     unsigned int z;
   
4. 
   
5.     z=((x-y)>;>;31)&1;
   
6. 
   
7.     return (1-z)*x+z*y;
   
8. }
   

复制代码

2、在考虑溢出的情况下，unsigned int z=((x^y)>;>;31)&1的值有两种可能，x、y同号时为0，x、y异号时为1。当x、y同号时x-y不会溢出，可参考1，得出最大值；当x、y异号时，取正的那个就是最大值。函数如下：

1. int max1(int x,int y)
   
2. {
   
3.     unsigned int z;
   
4. 
   
5.     z=((x-y)>;>;31)&1;
   
6. 
   
7.     return (1-z)*x+z*y;
   
8. }
   
9. 
   
10. int max2(int x, int y)
    
11. {
    
12.     unsigned int z;
    
13. 
    
14.     z=(x>;>;31)&1;
    
15.     return (1-z)*x + z*y;
    
16. }
    
17. 
    
18. int max(int x, int y)
    
19. {
    
20.     unsigned int z;
    
21. 
    
22.     z=((x^y)>;>;31)&1;
    
23.     return (1-z)*max1(x,y) + z*max2(x,y);
    
24. }

复制代码

yuxh

若用A0110A 的思路，则我前面写的那个函数也不会有溢出的问题，同样是考虑了同号和异号的情况。

river_wave

int max(int x,int y)
{
    int a[2];
    int sign;

    a[0]=x;
    a[1]=y;
    //改语句判断x,y大小，sign为0表示x>;y，sign为1表示x<y
    sign=((x-y)&0x80000000)>;>;31;

    printf("sign=%d,a[0]=%d,a[1]=%d\n",sign,a[0],a[1]);

    return a[sign];
}

win_hate

一个不用逻辑表达式，基于插值的方法：

1. 
   
2. int max (int a, int b)
   
3. {
   
4.         int g, r1, r2;
   
5. 
   
6.         g = ((a^b) >;>; 31) & 1;
   
7.         r1 = (a >;>; 31) & 1;
   
8.         r2 = ((a-b) >;>; 31) & 1;
   
9. 
   
10.         return g*(r1*b + (1-r1)*a) + (1-g)*(r2*b + (1-r2)*a);
    
11. }
    

复制代码

win_hate

这个贴子顶这么长了，我对上面出现的解决方法做一个总结。

问题：int a, b; 求 max (a,b)，不能用判断语句。

一、寻找最大数的根据：

1、允许用逻辑表达式：
        利用逻辑表达式的值， {a>;=b、a<b} = {0，1}。
2、不允许用逻辑表达式：
        利用比特位

        a^b 的最高位 ---- 判断符号是否相等
        a-b 的最高位 ---- 在符号相同的情况下判断大小
        a   的最高位 ---- a的符号
        b   的最高位 ---- b的符号

二、对上述标准的应用：

1、把大小关系对应到一个或若干个矩阵当中

        在本贴中，这个想法最早可以从 A0110A 的贴子中看到，但那段代码有点瑕疵。
       
        wg0124, svenwang 基于逻辑表达式构造了简单的对应关系。

        在不允许使用逻辑表达式的情况下，FH 和 linuxnewbie 仍然能实现对应。FH 和 linuxnewbie 的方法都可视力为A0110A方法的一个扩展。其中linuxnewbie的对应方法很直接，而且有注释，应该容易理解。FH 的方法我略微解释一下，在同号的情况下，FH 先把 a,b 的符号对应为 01 或 10，这正好是 2, 1，然后再把大小关系对应到一个矩阵中去。


2、使用插值

        yuxh和本人 给出的方法均基于插值。

        注意到无论是否使用逻辑表达式，我们的判定依据都是若干bit，当它们取不同值的时候，映射为不同值。从数学上看，这就是个插值问题。

三、只从数学上考虑：

        单纯出于数学上的考虑，不管计算机本身的限制， JohnBull 版主给出了两个公式，该公式刻画了max, min 与 绝对值的关系。有兴趣的朋友可以自行推导一下。如果推导有困难，可以查阅与“数学分析”相关的书。

cellar

差不多了吧？再来！
不用循环求一个整数是否为2的n次幂 n<=31