# 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