定义法 $O(n)$

记

$$k = \lfloor log_2n \rfloor$$

即

$$\begin{aligned} k \le log_2n < k + 1 \end{aligned}$$

等价于

$$\begin{aligned} 2^k \le n < 2^{k + 1}\\\ \end{aligned}$$

由于 $log_2n$ 和 $\lfloor x \rfloor$ 都是单调增函数，则 $\lfloor log_2n \rfloor$ 也是，可用双指针优化。

for (int i = 2, j = 1; i <= n; i++) {
  while (1 << j + 1 <= i) j++;
  lg2[i] = j;
}

上述代码中，内层 while 总共执行 $\lfloor log_2n \rfloor$ 次，可忽略不计。

递推法 $O(n)$

由

$$\begin{aligned} log_2n &= log_2(\frac{n}{2} \times 2) \\\ &= log_2 \frac{n}{2} + log_22 \\\ &= log_2 \frac{n}{2} + 1 \end{aligned}$$

得

$$\begin{eqnarray} \lfloor log_2n \rfloor &= \lfloor log_2 \frac{n}{2} + 1 \rfloor \\\ &= \lfloor log_2 \frac{n}{2} \rfloor + 1 \\\ &= \lfloor log_2 \lfloor \frac{n}{2} \rfloor \rfloor + 1 \tag{1} \end{eqnarray}$$

关于式 $(1)$，若 $n$ 为偶数显然成立。若 $n$ 为奇数

设

$$n = 2k + 1, k \in \mathbb{N^{+}}$$

则

$$\begin{aligned} & \frac{n}{2} = k + \frac{1}{2} \\\ & \lfloor \frac{n}{2} \rfloor = k \end{aligned}$$

设

$$2^m \le k < 2^{m + 1}, m \in \mathbb{N}$$

则

$$2^m \le k + \frac{1}{2} < 2^{m + 1}$$

则

$$\lfloor log_2k \rfloor = \lfloor log_2(k + \frac{1}{2}) \rfloor = m$$

则

$$\lfloor log_2\lfloor \frac{n}{2} \rfloor \rfloor = \lfloor log_2\frac{n}{2} \rfloor$$

for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;