Leetcode: Power of Two

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: 20 = 1
```

**Example 2**:

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

**Example 3**:

```
Input: n = 3
Output: false
```

**Constraints**:

```
-231 <= n <= 231 - 1
```

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

**Solution**

Loops/Recursion seems quite straight forward. We use a bitwise approach here. Let’s take a look at the some numbers that are the power of two and their binary representation.

Decimal | Binary |
---|---|

2 | 10 |

4 | 100 |

8 | 1000 |

16 | 10000 |

32 | 100000 |

For all numbers, the first bit are `true`

and all the remaining bits are `false`

. You can check the
binary representation based on that condition, but it’s still a loop on the binary string.

If we minus each number by 1, we get a new number with all bits are `true`

(all bits are inverted).

Decimal | Binary |
---|---|

2-1 | 1 |

4-1 | 11 |

8-1 | 111 |

16-1 | 1111 |

32-1 | 11111 |

If we use `&`

bitwise operator between `n`

and `n-1`

, the result will be `0`

.

Decimal | Binary | Result |
---|---|---|

2 & 1 | 10 & 01 | 00 |

4 & 3 | 100 & 011 | 000 |

8 & 7 | 1000 & 0111 | 0000 |

16 & 15 | 10000 & 01111 | 00000 |

32 & 31 | 100000 & 011111 | 000000 |

Working code in C#

```
public class Solution {
public bool IsPowerOfTwo(int n)
{
return n > 0 && (n & (n - 1)) == 0;
}
}
```

Who the hell could think of this bitwise solution?