# LeetCode Notes: Power of Two

## 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 == 2`

.^{x}

**Example 1:**

Input:n = 1

Output:true

Explanation:2^{0}= 1

**Example 2:**

Input:n = 16

Output:true

Explanation:2^{4}= 16

**Example 3:**

Input:n = 3

Output:false

**Example 4:**

Input:n = 4

Output:true

**Example 5:**

Input:n = 5

Output:false

**Constraints:**

- -2
^{31}<= n <= 2^{31}- 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:

`n`

has only one 1 in the binary representation, and the rest are all 0s`n-1`

means to change the 1 in`n`

to 0, and the following number to 1- 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:

a | b | a AND b |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

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
};
```

## Comments