slt
首先明确1点,负数和零不可能是 power of two
Solution1 不断 * 2 比较
时间复杂度 O(logn)
空间复杂度 O(1)
Solution2 bit
时间复杂度 O(1)
空间复杂度 O(1)
n为2的幂次方,则恒有:
n 二进制最高位为 1,其余所有位为 0
n−1 二进制最高位为 0,其余所有位为 1
-> n & (n-1) == 0
2^x | n | n-1 | n&(n-1) |
2^0 | 1 | 0 | 0 |
2^1 | 10 | 01 | 0 |
2^2 | 100 | 011 | 0 |
2^3 | 1000 | 0111 | 0 |
但是注意思路2跑的时间实际上大于思路1哦
Last updated