# XOR_EQ_SUM - Editorial

Author: emptypromises
Tester and Editorialist: iceknight1093

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.

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.

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.

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.

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.

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].

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)

3 Likes

This problem can also be solved using digit dp. At first I thought it would get TLEd because it performs 3.84*1e8 operations and time limit is 1sec, but somehow it passed.

2 Likes

beautiful Question, Broâ€¦, It took me 36 hrs to make final observationâ€¦

2 Likes