Problem#
給你一個整數 n
問你它是不是 $2^x$?
Follow up: 不用 loop/recursion?
測資限制#
- $-2^{31} \le n \le 2^{31}-1$
想法#
naive: 小於等於 0 一定不是(因為負數),去數(0~31)有幾個 bit,看是不是 1 個。
improve: popcount()
, log2, 移除最右 bit 等解法
這幾種做法複雜度都是 $O(1)$
- 時間複雜度: $\mathcal{O}(1)$
- 空間複雜度: $\mathcal{O}(1)$
AC Code#
Naive:
popcount:
log2:
移除最右邊 bit: