题意:给定$a,b∈[1,10^9]$,求[a,b]间有多少个数转换为二进制后0的个数比1多(转换后二进制数最高位为1)

思路:先来看几个栗子:如果求[1xxxxx]2有多少满足要求,那么答案$ans=\sum\limits_{i=3}^{5}C\limits_{5}^{i}$,因为只需在xxxxx中有5或4或3个0即可

那么对于任何一个二进制数,我们都可以这样求出比他小或者相等的二进制数有多少满足要求。1.所有位数比他少的都可以。2.与他同位的,对于他每一个是1的数位,这一位之前的数位不变,自己变为0,之后的随便填,可以达到要求的可以。

对于第二类,这样讨论会补充不漏地得到所有可行数。

比如对于1001011,属于第一类的数有:1xxxxx,1xxxx,1xxx,1xx,1x,1,属于第二类的数有:1000xxx,100100x,1001011(←这个数就是本身,也要算进来)然后再用例子中的组合数学方法求出有多少种填法。