LeetCode Notes: Power of Two

#leetcode

Question

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.

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

Example 4:

Input: n = 4

Output: true

Example 5:

Input: n = 5

Output: false

Constraints:

  • -231 <= n <= 231 - 1

Follow up: Could you solve it without loops/recursion?

Solution One

Analysis:

In the conventional way, a number can be divided into many 2 and multiplied by 2, then we will keep dividing this number by 2. If the result is output 1, then it is a power of 2.

Code:

/**
  * @param {number} n
  * @return {boolean}
  */
var isPowerOfTwo = function(n) {

     // Two special numbers are processed first
     if(n === 1) return true

     if(n === 0) return false

     // call method to process other numbers
     return divide(n)

     // Recursive search
     function divide(num){

         const result = num / 2
         const remainder = num% 2

         if(remainder !== 0){ // When the remainder is not 0, it means that the number is not divisible by 2, and it is eliminated directly
             return false;
         }else if(result === 1){ // If the remainder is 0, the final result is 1, which is a qualified number
             return true
         }else{ // When the remainder is 0, the result value is greater than or equal to 2, indicating that you can continue to divide by 2, recursively
             return divide(result)
         }

     }
};

Solution Two

Analysis:

Directly handle binary, if n is a power of 2, then there are the following rules:

  1. n has only one 1 in the binary representation, and the rest are all 0s
  2. n-1 means to change the 1 in n to 0, and the following number to 1
  3. We use the feature of bitwise and &, and get that n & (n-1) is always 0

If there are any doubts, let's explain the process in detail

Let's review the characteristics of bitwise and &, both numbers are 1 and the result is 1, otherwise it is 0, as follows:

aba AND b
000
010
100
111

The principle of n & (n-1) conversion is as follows, assuming num = 8:

In the binary representation of 8, 1 is on the far left

8     (1 0 0 0)
 
7     (0 1 1 1)
 
8 & 7 (0 0 0 0)
 
       ▲

We can see that the 1 in the first place is converted to 0, and the result is all 0.

Copy the following code to the console to see the print result:

console.log((8).toString(2)) // output: 1000
console.log((7).toString(2)) // output: 111
console.log((8 & 7).toString(2)) // Output: 0 (the only 1 is converted to 0)

in conclusion:

n & (n-1) can convert the rightmost 1 of the binary number of n to 0. In our problem, the only 1 is converted to 0

Also use the case of bitwise AND, refer to Hamming Distance

Code:

/**
  * @param {number} n
  * @return {boolean}
  */
var isPowerOfTwo = function(n) {
     return n> 0 && (n & (n-1)) === 0
};

Solution Three

Analysis:

It is still directly processing binary, this time the calculation method is slightly different, using the characteristics of binary negative numbers, n & -n to calculate.

Before the calculation, we understand how to calculate the negative binary value. In computers, negative numbers are expressed in the complement of their original positive numbers. What is the complement?

The original binary is bit-inverted to get the complement, and the Ones' complement +1 is the Two's complement.

Brief description, the binary value of a negative number is obtained by taking the inverse code +1 based on the binary value of the original positive number.

For example, the principle of n & -n conversion is as follows, assuming num = 8:

8                              (1 0 0 0)

The Ones' complement of 8      (0 1 1 1)
 
The Ones' complement of 8，+1
The Two's complement of 8
-8                             (1 1 1 1)
 
8 & -8                         (1 0 0 0)
 
                                ▲

We can get the rule that as long as the number that satisfies the condition of (n & -n) === n, it is a power of 2.

Code:

/**
  * @param {number} n
  * @return {boolean}
  */
var isPowerOfTwo = function(n) {
     return n > 0 && (n & -n) === n
};

Reference

Comments