LeetCode 每日一题231. 2 的幂

古城微笑少年丶 2022-10-16 14:25 160阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70]

## 常规解法 ##

最简单也是最容易想到的，递归将目标数一直 除以 2 如果 = 1 则代表是2的幂，递归终止条件为目标数对2 取余不为 0,其次要注意是2的幂肯定大于0  
编码实现：

class Solution { 
        public boolean isPowerOfTwo(int n) { 
            if (n <= 0) return false;
            while (n % 2 == 0) n /= 2;
            return n == 1;
        }
    }

*  时间复杂度: O(logn)
 *  空间复杂的: O(1)

## 目前来说的最优解 ##

若 n = 2^x 且 x 为自然数（即 n 为 2 的幂），则一定满足以下条件：

1.  恒有 n & (n - 1) == 0，这是因为

*  n 二进制最高位为 1，其余所有位为 0；
 *  n−1 二进制最高位为 0，其余所有位为 1；

1.  一定满足 n > 0

所以可以通过 `通过 n > 0 且 n & (n - 1) == 0 即可判定是否满足 n = 2^x`

代码实现

class Solution { 
        public boolean isPowerOfTwo(int n) { 
            return n > 0 && (n & (n - 1)) == 0;
        }
    }

> 这种解法我没想到，这里给出原作者连接,[链接][Link 1]

*  时间复杂度：O(1)
 *  空间复杂度：O(1)

## 硬编码 ##

在评论区还看到了一种硬编码解法，不推荐，不过也可以看看，图一乐

public static boolean isPowerOfTwo(int n) { 
            int[] pow = { 
                1,
                2,
                4,
                8,
                16,
                32,
                64,
                128,
                256,
                512,
                1024,
                2048,
                4096,
                8192,
                16384,
                32768,
                65536,
                131072,
                262144,
                524288,
                1048576,
                2097152,
                4194304,
                8388608,
                16777216,
                33554432,
                67108864,
                134217728,
                268435456,
                536870912,
                1073741824,
            };
            for(int i : pow){ 
                if(n == i){ 
                    return true;
                }
            }
            return false;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70]: /images/20221014/d5b57e69827f4344a26fb7bd894b4d03.png
[Link 1]: https://leetcode-cn.com/problems/power-of-two/solution/power-of-two-er-jin-zhi-ji-jian-by-jyd/