# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* emptypromises

*iceknight1093*

**Tester and Editorialist:**# DIFFICULTY:

2577

# PREREQUISITES:

Familiarity with bitwise operations and binary representations

# PROBLEM:

Given L and R, find the number of integers x such that there exist L \leq a \leq b \leq R satisfying a+b = a\oplus b = x.

# EXPLANATION:

First off, a + b = a\oplus b means that a and b must have completely disjoint binary representations, i.e, a\ \&\ b = 0.

With that in mind, letâ€™s go over the subtasks.

## Subtask 1

The limits here are very small, simply iterate over all pairs of (a, b), and if they satisfy the condition insert their sum into a set.

The answer is the size of the set.

The trivial implementation of this takes \mathcal{O}((R - L)^2 \log {(R - L)}) time, which is good enough.

## Subtask 2

Here, we have L = 0 and R = 2^k - 1, i.e, all numbers with at most k significant bits.

Itâ€™s possible to make every number from L to R here, since to make x we can choose a = 0 and b = x.

Making anything \gt R is impossible, because the xor of two k-bit numbers cannot have \gt k significant bits.

So, the answer is the length of the range [0, R], which is R+1.

Note that R+1 = 2^k, so the answer essentially says we can make all k-bit strings.

## Subtask 3

Here, we still have L = 0, though we might not have R = 2^k - 1.

With the same logic as the previous subtask, we can certainly make all x in the range [0, R].

However, we might now be able to reach x \gt R as well (for example, if R = 2 we can reach 3 = 1+2 = 1\oplus 2).

In fact, if R is a k-bit number, we can reach all the k-bit numbers!

## Proof

Let R be a k-bit number, i.e, k is the smallest integer such that R \leq 2^k - 1.

Then, certainly we must have 2^{k-1} \leq R.

Any k-bit integer x\geq 2^{k-1} can be reached by choosing b = 2^{k-1} and a = x - b.

Note that this works because a \lt 2^{k-1}.

Numbers \leq R can be formed trivially by (0, x) as noted eariler; and this method allows us to form all the numbers from R+1 to 2^k - 1, so weâ€™re done.

This gives us a simple solution: if R is a k-bit integer, the answer is just 2^k.

Finding k requires us to find the highest set bit in R, which can be done by just iterating k from 0 â€” itâ€™ll take \mathcal{O}(\log R) time which is good enough.

## Subtask 4

The constraints here allow for a linear (or close to linear) solution.

Note that any valid x must be \leq 2R.

So, letâ€™s iterate over each x from 0 to 2R and see if we can make it.

If x = 0, then we can make it with (0, 0) if L = 0, and canâ€™t make it otherwise.

If x \gt 0, then we can write its binary representation as x = 2^{p_1} + 2^{p_2} + \ldots + 2^{p_m} where p_1 \gt p_2 \gt \ldots \gt p_m.

To write x = a\oplus b = a + b, we need to distribute the bits p_1, p_2, \ldots, p_m to a and b.

Clearly, since b is the larger one, it must receive 2^{p_1}.

After this, itâ€™s best to give all remaining 2^{p_i} to a, since:

- Increasing b too much might make it exceed R
- Keeping a too small might leave it \lt L

So, the best chance we have is with a = 2^{p_2} + 2^{p_3} + \ldots + 2^{p_m} and b = 2^{p_1}.

That is, b = 2^{p_1} and a = x \oplus b.

Form these a and b, and check if they both lie in [L, R].

If they do, increase the answer by 1.

The check for each x can be done in \mathcal{O}(1) or \mathcal{O}(\log x), and we check upto 2R different values of x so this takes \mathcal{O}(R\log R) time, which is good enough.

## Subtask 5

Now, L and R are too large for any linear-type solutions to work.

Letâ€™s look back at how we solved subtask 4:

- We fixed a value of x between 1 and 2R (0 was special-cased out)
- We found the highest bit of x and gave it to b; and gave all the other bits of x to a
- Then, we checked if this a and b were in range [L, R].

Notice the second point in particular: the only b we care about are powers of 2.

So, letâ€™s fix b as a power of 2 in the range [L, R] and see which values of a are valid, as per our algorithm.

- First off, by our construction we must have a \lt b.
- We also must have a \geq L.
- Itâ€™s not hard to see that
*any*such a is valid; i.e, we can choose any a in the range [L, b-1].

The length of this range is b - L.

This gives us a pretty simple algorithm:

- Fix the value of b to some power of 2 that lies in [L, R].
- Then, add b - L to the answer.

If L = 0, add 1 to the answer since we can also form x = 0.

Since we only care about powers of 2 that donâ€™t exceed R, we check \log R of them.

So, this algorithm takes \mathcal{O}(\log R) time, which is fast enough to get AC.

# TIME COMPLEXITY

\mathcal{O}(\log R) per test case.

# CODE:

## Author's code (C++)

```
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
assert(1 <= T && T <= 1e5);
while (T--) {
long long l, r;
cin >> l >> r;
assert(0 <= l && l <= r && r <= 1e18);
long long ans = 0;
for (int b = 0; b < 60; b++) {
long long msb = (1LL << b);
if (l <= msb && msb <= r) {
ans += msb - l;
}
}
if (l == 0) {
ans++;
}
cout << ans << '\n';
}
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
l, r = map(int, input().split())
ans = 1 if l == 0 else 0
for pw in range(60):
if 2**pw > r: break
if 2**pw < l: continue
ans += 2**pw - l
print(ans)
```