notes/OJ notes/pages/Leetcode Power-of-Two.md

Leetcode Power-of-Two

2022-07-22 14:30

Algorithms:

#algorithm #bit_manipulation

Data structures:

#DS #bitset

Difficulty:

#coding_problem #difficulty_medium

Additional tags:

#leetcode

Revisions:

N/A

Related topics:

Links:

• Link to problem

---

Problem

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

Examples

Example 1:

Input: n = 1 Output: true Explanation: 20 = 1

Example 2:

Input: n = 16 Output: true Explanation: 24 = 16

Example 3:

Input: n = 3 Output: false

Constraints

• -231 <= n <= 231 - 1

Thoughts

[!summary] This is a #bit_manipulation problem. The solution can come from investigating multiple examples and find the common rules

Simple solution using bit masking:

Method 1, using masking

• if n <= 0, return false, because it's impossible to be power of 2.
• else, return !(n & (n - 1))

power of 2 and --1 looks like this

2 : 10
1 : 01

4 : 100
3 : 011

8 : 1000
7 : 0111

so, if it is power of 2, !(n & (n - 1)) will produce true.

otherwise, (n & (n - 1)) will produce something other than 0.

Method 2, count bits

power of 2 must have one and only one true in the bitset:

2 : 10
4 : 100
8 : 1000
...

So, by counting if the bitset has only one true.

Solution

Method 1:

class Solution {
public:
  bool isPowerOfTwo(int n) {
    // n == 0: return 0
    // n != 0: return !(n & (n - 1))
    if (n <= 0) {
      return false;
    } else {
      return !(n & (n - 1));
    }
  }
};

Method 2:

class Solution {
public:
  bool isPowerOfTwo(int n) {
    if (n <= 0) {
      return false;
    } else {
      return (bitset<32>(n).count() == 1);
    }
  }
};