# #3 [Leetcode 231](https://leetcode.com/problems/power-of-two/) Power of Two

###### tags:`Recursion` `iteration` `bit manipulation` `easy` `leetcode`

<br>

## Issue

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

### Sample Input & Output

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

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

Input: n = 3
Output: false

### Constraints

* -2^31 <= n <= 2^31 - 1.

### Follow up

:::spoiler Could you solve it without loops/recursion?
* Solution `Bit manipulation`
:::

<br>

## Solutions

### Most voted

:::spoiler Recrusion

/**
 * Time complexity would be O(logn).
 * Space complexity would be O(logn).
 */

var isPowerOfTwo = function(n) {
    if (n < 1) return false;
    if (n === 1) return true;
    return isPowerOfTwo(n/2);
};

:::

<br>

:::spoiler Iteration

<br>

https://leetcode.com/problems/power-of-two/discuss/2403463/Javascript-Solution

/**
 * Time complexity would be O(logn).
 * Space complexity would be O(logn).
 */

var isPowerOfTwo = function(n) {
    if(n<1) return false;
    if(n === 1) return true;
    while(n !== 1 ) {
        let x = n/2;
        if(x % 2 !== 0 && x > 1) return false;
        n/=2;
    }
    return true;
};

:::

<br>

:::spoiler Bit manipulation

<br>

https://leetcode.com/problems/power-of-two/discuss/369024/100-fastest-0ms-one-line-solution-with-explanation-binary-trick



/**
 * Time complexity would be O(1).
 * Space complexity would be O(1).
 */

var isPowerOfTwo = function(n) {
    return n => n > 0 ? !(n & n-1) : false;
};

:::

### Everyone's

:::spoiler 東

// Time O(log(n)) | Space O(log(n)); where n is the input number
var isPowerOfTwo = function(n) {
    if (n < 1) return false;
    else if (n === 1) return true;
    else if (Number.isInteger(n/2)) return isPowerOfTwo(n/2)
    else return false;
};

:::

<br>

:::spoiler Hao

/**
 * Time complexity would be O(logn).
 * Space complexity would be O(logn).
 */

var isPowerOfTwo = function(n) {
    if (n < 1) return false;
    if (n === 1) return true;
    return isPowerOfTwo(n/2);
};

:::

<br>

:::spoiler YC

/**
 * time: O(log n)
 * space: O(log n)
 */
var isPowerOfTwo = function(n) {
    if(n === 0) return false;
    if(n === 1) return true;
    if(n % 2 === 1) return false;
    return isPowerOfTwo(n/2);
};

:::

<br>

:::spoiler Becky

:::

<br>

:::spoiler 月薪

// Time O(？) Space O(？)
var isPowerOfTwo = function(n) {
    if(n !== 0){
        if(n === 1) return true;
        if(!!n % 2) return isPowerOfTwo(n / 2);
    }
    return false;
};

:::

<br>

## Discussion

### Bit manipulation
#### Negative binary representation system
[Link](https://www.cs.drexel.edu/~src322/cs164/binarySec/negativebin.html)


##### How to represent number with the same absolute value but different sign?

+ 00000001 # +1
- 00000001 # -1

##### Sign Magnitude

- Use the Most Significant Bit (MSB), the leftmost bit in a number, to represent the sign.
- Only 7 bits remain for magnitude.
- Normally an 8 bit value would have the range of 0 to 255. **The range of a signed 8 bit number is now -127 to 127** because the `value of magnitude` here (0000001) is still the same, **which could cause error when we adding and subtracting values**.

0 0000001 # +1
1 0000001 # -1

##### One's Complement

- When representing negative numbers, you invert all the bits. The 1's become 0's and the 0's become 1's.
- Because the range of the system is -127 to 127, it has the same issue which Sign Magnitude system faces.

0 0000001 # +1
1 1111110 # -1

##### Two's Complement

- **Two's complement is much more widely used, including Javascript**, than one's complement.
- Like One's Complement, We first invert the bits, but the different things here is that **we would then add one**.

:::spoiler Example to find negative two's complement numbers

##### [Numbers and binary addition](https://www.bbc.co.uk/bitesize/guides/zjfgjxs/revision/5)

**Steps**

1. Find the positive binary value for the negative number you want to represent.
2. Add a 0 to the front of the number, to indicate that it is positive.
3. Invert or find the complement of each bit in the number.
4. Add 1 to this number.

**Let's find -1**

1 = 001
Adding 0 to the front becomes 0001
'Inverted' becomes 1110
Add 1 = 1111 (-8 + 4 + 2 + 1 = -1)

:::

<br>

- Signed two's complement number has a range of -128 to 127. Unlike one's complement and sign magnitude, **two's complement does not have addition and subtraction problems**.

0 0000001 # +1
1 1111111 # -1

#### Bitwise Operations

##### [W3school/JavaScript Bitwise Operations](https://www.w3schools.com/js/js_bitwise.asp)