Counting Ones in a Range

Interview

Time limit1sMemory limit128 MB

Summary

Add up the number of 1 bits in the binary form of every integer from A to B.

Level: Medium5 of 10
Topics: Bit manipulation, Math
Solved: No attempts yet

Problem

You are given two natural numbers $A$ and $B$ . Write every integer $x$ with $A \le x \le B$ in binary, count the 1 digits in each one, and add all of those counts together.

Let $f(x)$ be the number of 1 digits in the binary representation of $x$ . Compute the value below.

$\sum_{x=A}^{B} f(x)$

Input

The first line contains two natural numbers $A$ and $B$ , separated by a space. ( $1 \le A \le B \le 10^{16}$ )

Output

Print the sum of the 1 counts on the first line.

Examples1

Example 1
Input
```
2 12
```
Expected output
```
21
```