A+B or A-B? (Problem A, CS3233 Midterm Contest 2024, 2024)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement
Alice believes that a friendly mid-term contest should start with an $A + B$ problem. But Bob disagrees. To increase creativity, he thinks an $A - B$ problem should be used instead.

To settle the dispute, the contest organizers have decided to use both problems. Given two integers $A$ and $B$, the contestants are required to output the value of $(A + B)$ or $(A - B)$, where or is the bitwise OR operator.

However, Alice still thinks her $A + B$ idea is superior. She decides to design the sample input of the problem so that the sample output is identical to $A + B$, that is, $A$ and $B$ satisfies the equality $(A + B)$ or $(A - B) = A + B$. Furthermore, her choice of $A$ and $B$ should satisfy $L \le B \le A \le R$ for some given range $[L, R]$.

How many possible choices of the pair $(A, B)$ are there?

For example, if $L = 5$ and $R = 7$, then the possible choices are $(5, 5), (6, 5), (6, 6), (7, 6),$ and $(7, 7)$, for a total of 5 choices.

# Input

The only line of input contains two integers $L$ and $R$ ($0 \le L \le R \le 2 \times 10^9$).

# Output

Output a single integer, the number of possible choices of the pair $(A, B)$ such that $L \le B \le A \le R$ and $(A + B)$ or $(A - B) = A + B$.


# Sample Input #1
```
5 7
```
# Sample Output #1
```
5
```

Sample inputs:
5 7

Sample outputs:
5

# Solution Analysis

Denote $f(R_A, R_B)$ be the number of possible pairs $(A, B)$ such that $B \le A,\ A \le R_A$ and $B \le R_B$. Then we are finding  
$f(R, R) - f(L - 1, R) - f(R, L - 1) + f(L - 1, L - 1)$.

$f(R_A, R_B)$ can be found by dynamic programming with bitmasks. We have to maintain the following states:

- **current_bit**: The number of bits for $A$ and $B$ filled so far. We will fill the bits from the most significant to the least significant one.
- **A < R_A**: Whether the most significant `current_bit` bits of $A$ is already less than the corresponding bits of $R_A$. Otherwise, those bits of $A$ will be exactly same as the corresponding bits in $R_A$.
- **B < R_B**: Same as above, but now we’re comparing $B$ and $R_B$.
- **carry**: Whether there will be a carry from the next less significant bit in $A + B$.
- **borrow**: Whether we will be borrowing 1 to the next less significant bit in $A - B$.

By including **carry** and **borrow** in the states, we are maintaining the interaction between bits in $A + B$ and $A - B$ so we do not need to worry about them anymore.

This solution runs in $\mathcal{O}(\log R)$, with a large constant. The transition formula is left as exercise.


Special judge (C++ scorer):