二进制翻转
有一些奇怪的用处
有的时候我们为了方便对于低位进行操作,我们要把二进制数翻转过来,这样可以避免使用大量的取模操作。
直接入正题
思想解释+具体代码
我们要求 $[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$ 需要是二的整数幂次,不然就不能获得能让人能理解的答案。