Problem#
給你一個 32-bit 的無號整數，要你回傳有幾個 1 (又稱作 Hamming weight)。
想法#
Naive: 每個 bit 都檢查是不是 1 然後記數。
Improve: 每次找最右邊的 1-bit，可以把數字 $n$ 與 $n-1$ 做 AND 運算，因為減一的話最右邊的 1 就會被消滅，經過 and 運算就會消失，直到變成 0。
或是可以用編譯器內建的 __builtin_popcount()
AC Code#
- 時間複雜度: $\mathcal{O}(1)$
- 空間複雜度: $\mathcal{O}(1)$
- 時間複雜度: $\mathcal{O}(1)$
- 空間複雜度: $\mathcal{O}(1)$