算法分析(一)

王朝java/jsp·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

写程序归根到底就是做两件事:算法实现和错误处理.

这里列举一些常用的算法并给以简单的分析,希望能有一定的参考价值.

1.判断一个正整数是否事2的幂

C实现:

int is2Power(unsigned int x){

return (x &(x-1))==0;

}

Java实现:

boolean is2Power(int x){

return (x &(x-1))==0;

}

两者实现并没有多大区别,x&(x-1)就是把x的最右边的一个1位变为0位,如果x为2的幂

那么就只有一个位为1,返回的结果就是0了.

注意:x必须为正整数,0也不可以.

2.判断一个正整数是否事2n-1的形式

和上一个问题没有什么区别,这里只给出Java的实现.

boolean is2PowerOne(int x){

return x &(x+1);

}

3.判断一个正整数是否事2j-2k的形式,j>k>=0.

Java实现:

boolean is2PowerJK(int x){

return (((x|(x-1))+1)&x)==0;

}

首先要明白要满足2j-2k的形式,x中为1的位必须连续,也就是这个样子的 00...01..10...0,明白了这一点就

好办了,x-1就是改变最右边的1位以及后面的,也就是10...0变成01...1,高位不变.

x|(x-1)使得x的尾0都变成了1,最后的形式是:000...011..1

这个已经是2n-1的形式了,只要套用 x&(x+1)公式就可以了.

当j=k+1时,就变成了公式1了.

当k=0时,就变成公式2了.

4.求一个整数的绝对值.

Java实现:

int abs(int x){

return x-((x<<1)&(x>>31));

}

当n为0时:x<<1=0,x>>31=0,结果为0.

当n为正:x>>31为0,结果为x.

当n为负:x>>31为全1,也就是-1,x-(x<<1)等于-n

不过注意的是:当Integer.MIN_VALUE<n<-230该公式不行,因为这个时候x<<1溢出了.

当x为Integer.MIN_VALUE时,返回Integer.MIN_VALUE,这个是对的.

有关移位操作可以参考:http://blog.csdn.net/treeroot/archive/2004/10/20/144201.aspx

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航