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: