Question

Formatted question description: https://leetcode.ca/all/231.html

 231	Power of Two

 Given an integer, write a function to determine if it is a power of two.

 Example 1:

 Input: 1
 Output: true
 Explanation: 2^0 = 1

 Example 2:

 Input: 16
 Output: true
 Explanation: 2^4 = 16

 Example 3:

 Input: 218
 Output: false

Algorithm

Observe the characteristics of the binary notation of the power of 2:

 2   4       8       16 　　....

 10  100     1000    10000　...

The power of 2 has only one 1, and the rest is 0s, so our problem-solving idea is to determine whether the lowest bit is 1 each time, then shift to the right, and finally count the number of 1s to determine whether it is Power of 2

Code

Java

public class Power_of_Two {


    class Solution {
        public boolean isPowerOfTwo(int n) {
            int cnt = 0;
            while (n > 0) {
                cnt += (n & 1);
                n >>= 1;
            }
            return cnt == 1;

        }
    }
}

// OJ: https://leetcode.com/problems/power-of-two/
// Time: O(1)
// Space: O(1)
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while ((n & 1) == 0) n >>= 1;
        return n == 1;
    }
};

class Solution(object):
  def isPowerOfTwo(self, n):
    """
    :type n: int
    :rtype: bool
    """
    return n != 0 and (n & -n) == n

231 - Power of Two

Question

Algorithm

Code

All Problems

All Solutions