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