Logarithms and Bit Manipulation (Powers of 2)

The number of bits needed to represent $n$ in binary is $\lfloor \log_2(n) \rfloor + 1$. For example, $n = 8 = 1000_2$ needs $4$ bits, and $\log_2(8) = 3$.

Why? Because $2^{k-1} \leq n < 2^k$, so $k - 1 \leq \log_2(n) < k$, giving $k = \lfloor \log_2(n) \rfloor + 1$. This is why $32$-bit integers can hold values up to $2^{32} - 1$.

Bit manipulation algorithms often run in $O(\log n)$ time because they process one bit per step, and there are $O(\log n)$ bits.