public boolean isPowerOfTwo(int n){
if( 0 == n|| 1 == n ) return true;
int x = n / 2;
int y = n%2;
if (1 == y) return false;
return isPowerOfTwo(x);
}
Hoặc chúng ta không cần viết đệ qui như sau:
public boolean isPowerOfTwo(int n){
boolean ret;
if( 0 == n|| 1 == n ){
ret = false;
}else{
int x = n / 2;
int y = n%2;
while ( x > 0){
if (1 == y) {
ret = false;
break;
};
x = x / 2;
y = x%2;
}
ret = true;
}
return ret;
}
Sau đây là cách nhanh hơn sử dụng hàm logarit:
public boolean isPowerOfTwo(int n){
double logn2 = Math.log(n)/Math.log(2);
int logn2i = (int) (Math.floor(logn2));
if(logn2-logn2i==0)
return true;
else
return false;
}
Tuy nhiên nếu chúng ta để ý một chút chúng ta sẽ có cách kiểm tra nhanh nhất. Các số là luỹ thừa của 2 đều có 1 chữ số 1 trong biểu diễn nhị phân của chúng. Ví dụ số1: 000001
2: 000010
4: 000100
8: 001000
16: 010000
32: 100000
Xét số n = 32 ( 100000) và n -1 = 31 (011111) và rõ ràng n&(n-1) = 0.
Ta có giải thuật như sau:
public boolean isPowerOfTwo(int n){
return ((n!=0) && (n&(n-1))==0);
}
Thật ngắn gọn, đơn giản phải không các bạn!