Good Bye 2015 B. New Year and Old Property —

Good Bye 2015 B. New Year and Old Property —— dfs 数学

题目链接：http://codeforces.com/problemset/problem/611/B

The year 2015 is almost over.

Limak is a little polar bear. He has recently learnt about the binary system. He noticed that the passing year has exactly one zero in its representation in the binary system — 201510 = 111110111112. Note that he doesn't care about the number of zeros in the decimal representation.

Limak chose some interval of years. He is going to count all years from this interval that have exactly one zero in the binary representation. Can you do it faster?

Assume that all positive integers are always written without leading zeros.

Input

The only line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 1018) — the first year and the last year in Limak's interval respectively.

Output

Print one integer – the number of years Limak will count in his chosen interval.

Examples

input
5 10
output
2
input
2015 2015
output
1
input
100 105
output
0
input
72057594000000000 72057595000000000
output
26

Note

In the first sample Limak's interval contains numbers 510 = 1012, 610 = 1102, 710 = 1112, 810 = 10002, 910 = 10012 and 1010 = 10102. Two of them (1012 and 1102) have the described property.

题解：

自己想到的办法是从a到b遍历以便，逐个判断，结果…… 毕竟过于缺乏思考。其实如果把二进制的数写下来观察一下，就可以找到规律的。

解法：其实二进制中只有一个0的数是很少的，那怎么推呢？可以知道10符合，101，1011,10111…… 以及110,1101,11011……等等，都是只有一个0的。那么就要从中找规律了。就比如1，它自己不符合，但是1<<1=10 就符合了，那么接下来（10<<1）+1==101，（101<<1）+1==1011……等都可以推下去。但是这组数据的都知识放在第2个位置，那么0在第三第四第n个位置的数又怎么推导呢？可知当(1<<1)+1==11,然后就可以推出110,1101了。所以就可以得出一个结论：当k的二进制数全为1，那么可以通过k生成一个符合和不符合的数。符合的数就直接*2+1继续推出一个符合的数就行了，他们的0全在同一个位置，且称他们在同一组吧；而不符合的又可以生成一个符合的数和一个不符合的数，同时创造了两个新组，符合的数只能生成同一组的数，而不符合的数可以一直生成不同的组。一个递归的过程。

代码如下：

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 long long  a,b,sum = 0;
 5 
 6 void dfs(long long i, int flag)
 7 {
 8     if(i>b)
 9         return ;
10 
11     if(!flag)
12     {
13         dfs(i*2,1);
14         dfs(i*2+1,0);
15     }
16     else
17     {
18         if(i>=a && i<=b)
19             sum++;
20         dfs(i*2+1, 1);
21     }
22 }
23 
24 int main()
25 {
26     scanf("%lld%lld",&a,&b);
27     dfs(1,0);
28     printf("%lld
",sum);
29     return 0;
30 }

View Code