611B.md (1475B)
1 Source: https://codeforces.com/problemset/problem/611/B 2 3 B. New Year and Old Property 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The year 2015 is almost over. 22 23 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. 24 25 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? 26 27 Assume that all positive integers are always written without leading zeros. 28 29 Input 30 31 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. 32 33 Output 34 35 Print one integer – the number of years Limak will count in his chosen interval. 36 37 Examples 38 39 Input 40 41 ``` 42 5 10 43 ``` 44 45 Output 46 47 ``` 48 2 49 ``` 50 51 Input 52 53 ``` 54 2015 2015 55 ``` 56 57 Output 58 59 ``` 60 1 61 ``` 62 63 Input 64 65 ``` 66 100 105 67 ``` 68 69 Output 70 71 ``` 72 0 73 ``` 74 75 Input 76 77 ``` 78 72057594000000000 72057595000000000 79 ``` 80 81 Output 82 83 ``` 84 26 85 ``` 86 87 Note 88 89 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.