算法分析(一)
写程序归根到底就是做两件事:算法实现和错误处理.
这里列举一些常用的算法并给以简单的分析,希望能有一定的参考价值.
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
