面试中算法(2的整数次幂）

我会带着你远行 2024-05-28 10:22 74阅读 0赞

### 判断一个正整数是否是2的整数次幂（如16是2的4次方，返回true;18不是2的整数次幂，则返回false），要求性能尽可能高。 ###

> 使用一个整型变量，让它从1开始不断乘以2，将每一次乘2的结果和 目标整数进行比较。

def power2(a):
        temp=1
        #循环
        while temp<=a:
            #如果相等，就是2的整数次幂
            if a==temp:
                return True
            #每次乘以2
            # temp*=2
            #可以修改成,向左移1位
            temp=temp<<1
        return False
    
    
    if __name__ == '__main__':
        print(power2(16))
        print(power2(19))

**这样确实有一定优化。但目前算法的时间复杂度仍然是O (logn），本质上没有变。**

**如果把2的整数次幂转换成二进制数，会有什么样的共同点?**

![92f5e464ebb94597aa11c19062a33177.png][]

> 上面都是一个整数是2的整数次幂，当它转化成二进制数时，只有最高位是1，其他位都是0

**减1**

![a29ac9f16a7142b7a4ba19e7cd13bd1a.png][]

> 发现： 2的整数次幂一旦减1，它的二进制数的数字就全部变成了1!

![435f89e27cf7413ebe9e7d634d80c746.png][]

> 发现： 0和1按位与运算的结果是0，所以凡是2的整数次幂和它本身减1的结果进行与运 算，结果都必定是0。反之，如果一个整数不是2的整数次幂，结果一定不是0

**对于一个整数n，只需要计算n& (n-1)的结果是不是0。这个方法的时间复杂度只有O (1）。**

def power2_proirity(a):
        return a &(a-1)==0

[92f5e464ebb94597aa11c19062a33177.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/0c90e0bccff54aff8f7e913f6888184e.png
[a29ac9f16a7142b7a4ba19e7cd13bd1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/3c11bb0cfcb24438ad31e136d3d10109.png
[435f89e27cf7413ebe9e7d634d80c746.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/f4a17625ba5b4c83b8bf42fac778135b.png