Round Numbers

Interview

Time limit1sMemory limit128 MB

Summary

Count integers in [Start, Finish] whose binary form has at least as many zeroes as ones.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics, Math
Solved: No attempts yet

Problem

Cows have no fingers or thumbs, so they cannot play 'Rock, Paper, Scissors' to make arbitrary decisions such as who gets to be milked first. They can't even flip a coin, because it is so hard to toss one with hooves.

So they have resorted to matching round numbers. The first cow picks an integer less than two billion, and the second cow does the same. If both numbers are round numbers, the first cow wins; otherwise the second cow wins.

A positive integer $N$ is a round number if its binary representation (written without leading zeroes) has as many or more zeroes than ones. For example, $9$ in binary is $1001$ ; it has two zeroes and two ones, so $9$ is a round number. The integer $26$ is $11010$ in binary; it has two zeroes and three ones, so it is not a round number.

Converting numbers to binary takes cows a while, so deciding the winner also takes a while. Bessie thinks she will have an advantage if she knows how many round numbers lie in a given range.

Write a program that reports how many round numbers appear in the inclusive range from $Start$ to $Finish$ ( $1 \le Start < Finish \le 2{,}000{,}000{,}000$ ).

Input

Line 1: Two space-separated integers $Start$ and $Finish$ .

Output

Line 1: A single integer, the count of round numbers in the inclusive range $Start \ldots Finish$ .

Hint

The table below shows, for each integer from $2$ to $12$ , whether it is a round number. (Columns: decimal, binary, zeroes x0 + ones x1, verdict.)

 2    10  1x0 + 1x1  ROUND
 3    11  0x0 + 2x1  NOT round
 4   100  2x0 + 1x1  ROUND
 5   101  1x0 + 2x1  NOT round
 6   110  1x0 + 2x1  NOT round
 7   111  0x0 + 3x1  NOT round
 8  1000  3x0 + 1x1  ROUND
 9  1001  2x0 + 2x1  ROUND
10  1010  2x0 + 2x1  ROUND
11  1011  1x0 + 3x1  NOT round
12  1100  2x0 + 2x1  ROUND

Examples3

Example 1
Input
```
2 12
```
Expected output
```
6
```
Example 2
Input
```
1 2
```
Expected output
```
1
```
Example 3
Input
```
7 9
```
Expected output
```
2
```