15 thg 3, 2013

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);
}

Không có nhận xét nào:

Đăng nhận xét

Related Posts Plugin for WordPress, Blogger...