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

rainshadow

PF

bleem1998

m = m & ~( m / 2 ) & ~( m / 4)
为什么这句可以得到最高的那一位呢


阿我理解了，那并不是最高一位，而是把后头两位给弄成0
可是这样一定能确保(x & m) / m = 1吗？
假设
m=000100110
x=000100001
那么(x&m)/m = 0

yuxh

原帖由 "bleem1998" 发表：
m = m & ~( m / 2 ) & ~( m / 4)
为什么这句可以得到最高的那一位呢

不是最高的一位，而是把m变成：0...0100X...X这样的形式，即1后面有两个0
于是当x在该位上为1时:
(x & m) + m / 2 >;=0...0100...0 + 0...0010...0 = 0...0110...0 >;=m
(x & m) + m / 2) <= 0...01001...1 + 0...001001...1 <= 0...011...10 < 2m
所以((x & m) + m / 2) / m = 1
而当x在该位上为0时：
(x & m) + m / 2 <= 0...00001...1 + 0....001001...1 = 0...0011...1 < m
所以((x & m) + m / 2) / m = 0

bleem1998

被你打败了
这都想得出来
厉害

zleil

原帖由 "yuxh" 发表：

不是最高的一位，而是把m变成：0...0100X...X这样的形式，即1后面有两个0
于是当x在该位上为1时:
(x & m) + m / 2 >;=0...0100...0 + 0...0010...0 = 0...0110...0 >;=m
(x & m) + m / 2) <= 0...01001............

也没必要这样，如果能有一个函数返回 m 的第一个为 1 的位置，那么问题不就很简单了？假设 m 的第 i 位是 1，那么( ( x & ( 1 << i ) ) >;>; i ) & x 就代表 x 是否在该位上为 1。
int bit( int v, int i )
{
        return ( v & (1 << i) ) >;>; i ;
}
int first_one( int x )
{
        int i,j,ret;

        i = 0;
        ret = 0;
        for( j=31; j>;=0; j-- ){
                ret |= bit(x,j) & (!ret);
                i += (!ret);
        }
        i = 31 - i;
        return i;
}

yuxh

我在前面的解释中说过了不能用循环
for( j=31; j>;=0; j-- )
这里j>;=0不就是判断吗？

zleil

晕了，我上一面的算法里也用了判断，悲哀！

我在前面的解释中说过了不能用循环
for( j=31; j>;=0; j-- )
这里j>;=0不就是判断吗？

这个把循环展开，体力活啊

yuxh

原帖由 "zleil" 发表：


这个把循环展开，体力活啊

想着想着就迷糊了，我也犯过这个错误的呀!幸亏发现得早，不然浪费不少时间了
呵呵~~~

zleil

原帖由 "yuxh" 发表：

想着想着就迷糊了，我也犯过这个错误的呀!幸亏发现得早，不然浪费不少时间了
呵呵~~~

说实话，你那个 m = a ^ b 真是太强了！！！

siah

int  main(int argc,char *argv[])
{
if(argc!=3)
  {
        printf("Usage:%s num1 num2\n",argv[0]);
        exit(0);
}
int num[3];
   int index=0;
   num[0]=atoi(argv[1]);
   num[1]=atoi(argv[2]);
   num[2]=atoi(argv[2]);

   index=num[2]-num[0];
   index=index/abs(index)+1;
   printf("The max is [%d]\n",num[index]);
        return 1;
}