二进制哪几位是1

原理：借助$lowbit$的思想，每次得到最后一个$1$的位置并减去。

由$lowbit(n)（100...0）$到这是第几位，需要取对数$log_2(lowbit(n))$即可。

但是$C++\ math.h$库的$log$是以$e$为底数的实数运算且复杂度常数较大，故采用哈希思想，$H[i]$的值为$log_2i$。

于是有：

 

还有稍微复杂一点但效率更高的方法，不需要使用$2^{20}\approx10^6$的数组，利用一个数学小技巧：$\forall k\in[0,35], 2^k\ mod\ 37$互不相等且恰好取遍整数$1\sim36$。

$H[i]=k$说明$2^k%37=i$，修改后如下：