最近连着两次遇到了该类问题，这类问题看上去挺简单，但是想要非暴力破解还是挺复杂的，我每次都是做2个多小时才能做出来，实际上这早就超时了。 我们只能做出已经学过的题目，而对于没有思路的这类题目，几乎不可能在半小时内做完。所以这里总结下，可能以后还会遇到。

统计从a到b（包含a，b），区间所有二进制数中1的个数。比如，从1到3的全部二进制包括1(1B),2(10B),3(11B)，所有1的个数就是1+1+2=4.a,b的取值范围1E9.

本质上是数[0,n)所有整数上二进制中1的个数cnt(n)，题目所求cnt_between(a,b)=cnt(b)-cnt(a)+cnt_one_num(b),其中cnt_one_num(b)表示b二进制表示时1的个数。 其中cnt(n)怎么求呢？这个得拆解，现举例说明，求[0,1011B)区间整数所有1的个数。当然暴力的方法虽然思路简单，但是复杂度太高，不合要求。先拆解成子问题，按数位拆分，最高位1表示1000B，那么子问题可以是[0,1000B),同理也会拆分为其余的[1000B,1010B),[1010B,1011)，这样就可以了。 那么[0,1000B)如何计算呢？ 这类问题可以概括为[0,1),[0,10B),[0,100B),[0,1000B)等一系列问题。然后由简单到复杂去求解即可得到通用的思路。 定义函数cnt_bit(b)来计算 [ 0 , 2 b ) [0,2^b ) [0,2b) 所有整数上二进制中1的个数，容易得知cnt_bit(0)=0，cnt_bit(1)=1,然后cnt_bit(2)表示[00,11B]中1的个数，它分为高位和低位分别来统计。低位有2cnt_bit(b-1)个1，因为高位有2种情况（0和1），所以是2cnt_bit(b-1)，b=2就是有2个，即01B和11B这里的低位都是1；高位有 1 ∗ ( 2 b − 1 ) 1*(2^{b-1} ) 1∗(2b−1)个,也就是说，高位为1的时候，有 2 b − 1 2^{b-1} 2b−1个数，在b=2的时候，就是有2个即10B和11B，这里的高位都是1.所以总结会有 c n t _ b i t ( b ) = { 0 i f b = 0 1 i f b = 1 2 × c n t _ b i t ( b − 1 ) + 2 b − 1 i f b > 1 cnt\_bit(b)=\begin{cases} 0 & if\quad b=0 \\ 1 & if\quad b=1 \\ 2 \times cnt\_bit(b-1)+2^{b-1} & if\quad b>1 \end{cases} cnt_bit(b)=⎩ ⎨ ⎧​012×cnt_bit(b−1)+2b−1​ifb=0ifb=1ifb>1​ 现在来求cnt(n),回到原来的问题，求[0,1011B)区间整数所有1的个数，子问题是[0,1000B),[1000B,1010B),[1010B,1011)中1的个数，[0,1000B)是cnt_bit(3)个1.[1000B,1010B)要聚焦到第1位的1，它前面有1个1，这个1会出现[00,10B)次，也就是 2 1 2^1 21次；其余部分有cnt_bit(1)个1，加起来即可。[1010B,1011)这部分同理，左边有 2 × 2 0 = 2 2\times2^0=2 2×20=2个，右边有cnt_bit(0)=0个，加起来就是2个也就是1010B左侧有2个。 整理下思路，我们需要从左往右数（高位到低位），需要知道左侧有多少个1，这个变量用left_cnt表示，这时来尝试解一下。

接下来处理下边界值，cnt_one_num(n)，这个函数用来数数字n的二进制形式中1的个数，由于这里只有1个数字，直接数即可。

基本思路就是这样。 完整代码参考如下：