MZVRK - Whirligig number


By removing all digits left of the rightmost digit one in the binary representation of some integer, we get what is called the "whirligig" of that number. For example, the whirligig of 6 i.e. (110)2 is 2 i.e. (10)2, and the whirligigof 40 i.e. (101000)2 is 8 i.e. (1000)2. Write a program that will calculate the sum of the whirligig of all numbers between two given numbers A and B (inclusive).

Input

First and only line of input contains two integers A and B, 1 ≤ A ≤ B ≤ 10^15.

Output

First and only line of output should contain the sum from the problem statement.

Note: the result will fit into the 64-bit signed integer type.

Sample

input
176 177

output 
17

input
5 9

output
13

input
25 28

output
8

hide comments
janina: 2015-04-28 19:53:41

AC in 1st go!!!...nice one

Anjaan: 2014-10-01 08:45:06

Last edit: 2014-10-01 08:51:54
Anjaan: 2014-10-01 08:44:56

Last edit: 2014-10-01 09:11:34
AASTHA ANAND: 2014-09-30 08:20:07

can u plez suggest some time optimization technique.my soloution is giving tle for running judge 10...ID http://www.spoj.com/files/src/12498455/

Smriti Vashisth: 2014-05-17 11:36:30

getting tle again n again, also got SIGFPE once, unable to understand where the prob is, plz help!
here is my code
https://ideone.com/yhKm9X

hitesh091: 2014-04-03 14:55:18

any hint about how to solve this problem?

ওয়াসী (Wasi): 2013-11-13 20:46:46

Thanks @numerix

numerix: 2013-11-13 20:31:02

@Wasi: Explanation is simple. Those three submissions listed as Python 3.2 are in fact Python 2.6 submissions. This problem seems to have 10 different input sets, each time the interpreter startup time is added. Python 2.6 had a slightly shorter startup time than Python 2.5 (the fastest Python 2.7 submissions - except my latest Python 2.7 submission on top of the list - are in fact Python 2.5 submissions as you can conclude from the memory usage), so the fastest Python submissions for that problem are those old Python 2.6 submissions. So: The fastest Python 3.2 code so far is yours.

Last edit: 2013-11-13 20:32:14
ওয়াসী (Wasi): 2013-11-12 14:54:30

I am a bit curious about the best three submissions of python 3.
0.17s with python 3 !
which is faster than the best python 2 submission.
:O

Mahesh Mishra: 2013-10-18 15:00:42

AC :) my 150th..


Added by:~!(*(@*!@^&
Date:2009-02-28
Time limit:0.241s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 05