LeetCode / Power of Two

https://leetcode.com/problems/power-of-two/

Given an integer, write a function to determine if it is a power of two.

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

Example 2:
Input: 16
Output: true
Explanation: 24 = 16

Example 3:
Input: 218
Output: false

与えられた値が２の階乗かどうかを判定する問題。ビット演算を使った解法を初めて知ったときにはほーっと思いました。

解法1

ビット演算で解く方法。
2進法で表すと、2の階乗の値となるごとに桁が上がることを利用します。以下の通りですね。

0    0
1    1
2   01
3   11
4  100
5  101
6  110
7  111
8 1000

具体的には、値nとn-1をAND演算すると、nが2の階乗のときのみ0となることを利用します。3&4や7&8は0になりますね。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 0:
            return False
        elif n & (n-1) != 0:
            return False
        else:
            return True

解法2

シンプルなIterativeな解法も示しておきます。これでもTLEにはなりません。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 0:
            return False
        else:
            while n % 2 == 0:
                n /= 2
        return n == 1