Kiểm tra một số có là luỹ thừa của 2 hay không nhanh nhất

Thông thường để muốn kiểm tra một số có là luỹ thừa của 2 hay không thì chúng ta đem số này chia cho 2 như sau:

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!

Bài viết liên quan