在C++中，除了使用<cmath>中的log或log2函數求對數，也可以通過遞推求出所有可能用到的$?{\log }_{2}i?,i\in [1,n]$

證明：$?{\log }_{2}i?=?{\log }_2?\frac{i}{2}??+1$
由于${\log }_{2}i={\log }_2(\frac{i}{2}?2)={\log }_2\frac{i}{2}+{\log }_{2}2={\log }_2\frac{i}{2}+1$
等號兩邊都向下取整，得：
$?{\log }_{2}i?=?{\log }_2\frac{i}{2}?+1$

• 如果$i$是偶數，則$\frac{i}{2}=?\frac{i}{2}?$，因此有
  $?{\log }_{2}i?=?{\log }_2\frac{i}{2}?+1=?{\log }_2?\frac{i}{2}??+1$
• 如果$i$是奇數，則$\frac{i?1}{2}=?\frac{i}{2}?$
  設$?{\log }_2\frac{i?1}{2}?=x$
  那么$x\le {\log }_2\frac{i?1}{2}<x+1$
  $2^x\le \frac{i?1}{2}<2^{x+1}$
  由于$\frac{i?1}{2}$是整數，$2^{x+1}$也是整數，較小的整數加上$\frac{1}{2}$后，一定小于較大的整數。
  因此有$2^x\le \frac{i?1}{2}<\frac{i?1}{2}+\frac{1}{2}=\frac{i}{2}<2^{x+1}$
  所以$x\le {\log }_2\frac{i}{2}<x+1$
  因此$?{\log }_2\frac{i}{2}?=x=?{\log }_2\frac{i?1}{2}?=?{\log }_2?\frac{i}{2}??$
  因此$?{\log }_{2}i?=?{\log }_2\frac{i}{2}?+1=?{\log }_2?\frac{i}{2}??+1$
  證畢。

已知$?{\log }_{2}1?=0$，結合遞推式$?{\log }_{2}i?=?{\log }_2?\frac{i}{2}??+1$即可遞推得到所有可能用到的$?{\log }_{2}i?,i\in [1,n]$。

代碼如下：

const int N = 1000005;//N設為n可能達到的最大值
int lg[N];//lg[i]：floor(log_2{i})
void initLg(int n)//生成lg[1]~lg[n]
{//全局變量初值為0，已經設好lg[1] = 0for(int i = 2; i <= n; ++i)lg[i] = lg[i/2]+1;
}

預處理lg數組的時間復雜度為$O(n)$