有的时候我们为了方便对于低位进行操作，我们要把二进制数翻转过来，这样可以避免使用大量的取模操作。

直接入正题

思想解释+具体代码

我们要求 $[0,2^{len})$ 的区间中的每一个翻转。

首先要知道的是什么叫一个 $a$ 进制数的翻转。

我们以 $2$ 进制为例，$(x_{n}…x_{2}x_{1}x_{0})_{2}$ ,

它的翻转就是

\[rev(x_{n}...x_{2}x_{1}x_{0})_{2}=(x_{0}...x_{n-2}x_{n-1}x_{n})\]

我们考虑线性求解这个东西。

发现对于一个数 $t$，其翻转

\[rev(x_{t}...x_{2}x_{1}x_{0})_{2}=(x_{0}<<t)\mid (rev(0x_{t}...x_{2}x_{1})>>1)\]

相当于是把已求出的答案，通过在高位加数的方式得到新的答案

可以发现下方的公式，那么显然我们就可以从小到大线性求了

Code:

for(int i=0;i<n;++i){
	rev[i]=(rev[i>>1]>>1)\mid ((i&1)?n>>1:0);
}

需要注意的是，$n$ 需要是二的整数幂次，不然就不能获得能让人能理解的答案。