# XORRY2 - Editorial

Author: munch_01
Tester: raysh_07
Editorialist: iceknight1093

TBD

None

# PROBLEM:

You’re given an integer X.
Find the number of pairs (A, B) such that:

• 0 \leq A \leq B \leq X
• A\oplus B = X
• (B-A) is as small as possible across all pairs satisfying the first two conditions.

# EXPLANATION:

It is recommended to read the editorial of XORRY1 first, since this will continue from there.

As before, let x_1 \lt x_2 \lt\ldots\lt x_k be the set bits in the binary representation of X.
We observed that:

• One solution is obtained by setting B = 2^{x_k} and A = 2^{x_1} + 2^{x_2} + \ldots + 2^{x_{k-1}}.
• Moving any of these x_i from A over to B will increase the difference, and so isn’t optimal.
• For all bits that aren’t one of the x_i, they must be set in either both A and B, or they must not be.
However, whether they are set or not doesn’t affect the difference (B-A) at all.

So, each bit other than the x_i has a choice: it can be either set or unset.
However, we need to ensure that A and B don’t exceed X while doing this.
To that end, observe that:

• Setting any bit higher than x_k will cause both A and B to exceed X, so we can’t do this.
• Setting any bit between x_{k-1} and x_k will cause B to exceed X so we can’t do this either.
• Setting any bit lower than x_{k-1} won’t cause any issues, since even if all of them were set, B's value is bounded above by 2^{x_k} + 2^{x_{k-1}} which can’t exceed X.

This means, if there are m bits below x_{k-1} that are ‘free’, the answer is simply 2^m — for each of them, we can independently choose whether to set it or not.
Finding the number of such bits is easy in \mathcal{O}(\log X) since you can just iterate each bit to check.

# TIME COMPLEXITY:

\mathcal{O}(\log X) per testcase.

# CODE:

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}

assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}

string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int minv, int maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
}
return v;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

input_checker inp;

const int T = 1e5;
const int N = 1e9;

void Solve()
{
int ans = 1;
int cnt = 0;
for (int i = 31; i >= 0; i--){
if (n >> i & 1){
cnt++;
} else {
if (cnt >= 2) ans *= 2;
}
}

cout << ans << "\n";
}

int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in",  "r", stdin);
// freopen("out", "w", stdout);

for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}

auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
x = int(input())
a, b = 0, 0
for i in range(30):
if x & 2**i:
a += b
b = 2**i
ans = 1
for i in range(30):
if 2**i <= a and (x & 2**i == 0): ans *= 2
print(ans)