Is Power Of Two

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.=

Example1

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

Example2

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

Example3

*Input*: n = 3
*Output*: false

SOLVING

we’ll use Bit manipulation method. Since in binary each bit is a power of 2 wee can use this to know if it’s a power of 2 or not

First Approach

If the number of 1 is equal to 1 so it’s a power of 2

Steps

• While n is superior to 0:
  • If the first bit is 1 increase count
  • Use shift right to move all bits one on the right
• If count equal 1 so it’s a power of 2

• Example 16

  [1,0,0,0,0]
       &      == FALSE
  [0,0,0,0,1]
  
  [0,1,0,0,0]
       &      == FALSE
  [0,0,0,0,1]
  
  [0,0,1,0,0]
       &      == FALSE
  [0,0,0,0,1]
  
  [0,0,0,1,0]
       &      == FALSE
  [0,0,0,0,1]
  
  [0,0,0,0,1]
       &      == TRUE | COUNT += 1
  [0,0,0,0,1]
  
  COUNT = 1 (16 is a power of 2)
  

• Example 5

  [0,0,1,0,1]
       &      == TRUE | COUNT += 1
  [0,0,0,0,1]
  
  [0,0,0,1,0]
       &      == FALSE
  [0,0,0,0,1]
  
  [0,0,0,0,1]
       &      == TRUE | COUNT += 1
  [0,0,0,0,1]
  
  COUNT = 2 (5 is **not** a power of 2)
  

Code

class Solution {
public:
  bool isPowerOfTwo(int n) {
    int count = 0;

    while (n > 0) {
      if (n & 1)
	count++;
      n = n >> 1; // or n >>= 1
    }
    return count == 1;
  }
};

Second Approach

Check if there is similarities between n and n-1

Steps

• Return false if x<=0
• Return the result of & comparison between n and n-1
• Yeah that’s all x)

• Example 16

  [1,0,0,0,0] = 16
       &      == FALSE | 16 is a power of 2
  [0,1,1,1,1] = 15
  

• Example 5

  [0,0,1,0,1] = 5
       &      == TRUE | 5 is **not** a power of 2
  [0,0,1,0,0] = 4
  

Code

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

• PROBLEM
• BITMANIPULATION