位运算求解LeetCode--2 的幂

2的幂

https://leetcode.cn/problems/power-of-two/description/

思路

如果一个数是2的幂，那么该数的二进制表示形式一定是最高位为1，其余位为0，且最高位的1即为该数字全部

不可能有多个1的原因：若有多个1，且还是2的倍数，那这些1应该合并为更高位的1个1，而不是以多个1的形式出现，矛盾，所以不可能有多个1

代码

方法1：取最高位，和原数字比较，相等则是2的幂，不相等则不是

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

方法2：把最右侧的1（最高位的1）删掉，结果为0则是2的幂，不为0则不是

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

复杂度

时间复杂度：O(1)

本题算法核心

本题解题时可能更容易想到循环、递归，但循环和递归的时间复杂度较高，使用位运算解决不仅代码简洁，而且时间复杂度大大降低。本题主要用到的知识点：

1. 使用位运算获取最右侧的1：n&(-n)
2. 使用位运算消除最右侧的1：n&(n-1)