New Year and Old Property 位运算

New Year and Old Property

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 —2015₁₀= 11111011111₂. 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 integersa andb (1 ≤ a ≤ b ≤ 10¹⁸) — 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.

Example
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 numbers5₁₀= 101₂,6₁₀= 110₂,7₁₀= 111₂,8₁₀= 1000₂,9₁₀= 1001₂and10₁₀= 1010₂. Two of them (101₂and110₂) have the described property.

题意是给定一个区间，求在这区间内满足二进制只有一个0的数。由于是二进制，自如而然我就想到了位运算，推了下，其实每个满足二进制只有一个0的数

可以表示为:(1<<i) - 1 - (1<<j) {j < i-1}。

一开始是用c++写的，不过c++的位运算只是整数型，1<<60就会出错，而这里是长整数型，可能还有其它方法进行长整数型的位运算，可惜我菜菜的，就只能用python写了。

不多说。见代码！！！

1 a,b = map(int,raw_input().strip().split())
2 ans = 0
3 for i in range(2,63):
4     for j in range(0,i-1):
5         x = (1 << i) - 1 - (1 << j)
6         if(a <= x and x <= b):
7             ans += 1
8 print(ans)

-------------------更新线-----------------------------

c++可以进行长整数的位运算，只是1变成了1LL.

原文链接: https://www.cnblogs.com/xingkongyihao/p/6719644.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍