Wednesday, September 2, 2015

Leetcode: Power of Two

Given an integer, write a function to determine if it is a power of two.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Understand the problem:
The problem is a bit manipulation problem. 

The basic idea is to bit & with mask 1, and count the number of 1s. Then shift the n to the right until n is 0. If n is power of 2, the number of 1 should be equal to 1. 

Code (Java):
public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        
        int count = 0;
        
        while (n > 0) {
            count += (n & 1);
            n = n >> 1;
        }
        
        return count == 1;
    }
}

Another one-line solution:
A number is power of 2 is equalvent to if n & (n - 1) == 0. 

Code (Java):
public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        
        return (n & (n - 1)) == 0;
    }
}

No comments:

Post a Comment