PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Akshit Monga
Preparer: Tejas Pandey
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
2001
PREREQUISITES:
Bitwise operations
PROBLEM:
You are given N and X. Find the number of integers K such that 0 \leq K \lt N and ((N \oplus K) \And X) = 0.
EXPLANATION
Since this task deals with bitwise operations, it makes sense to look at things bit by bit.
If the binary representation of a number y has a 1 in the i-th position, we say the i-th bit is set in y.
Now, we want the bitwise and of N\oplus K with X to be 0. This means that if a bit is set in X, it will be set in K if and only if it is set in N. In other words, if some bit of X is set, there is exactly one choice for such a bit in K.
After this, we apply a classical technique when counting things that must be lexicographically smaller than something else. Iterate over the positions, and fix the one that is the first to be strictly less, then we have complete freedom in all following positions.
That is, iterate bits from 30 down to 0. Suppose we are currently at the i-th bit. We will assume that the bits from 30 to (i+1) of both N and K are equal, and the i-th bit of K is strictly less than the i-th bit of N (of course, note that this is only possible when the i-th bit of N is 1, and the i-th bit of X is not 1).
Now, bits 0 to i-1 are totally free (except for the restriction on set bits of X mentioned before), and each of these have 2 choices (can be 0 or 1). So, if there are c such free bits, we add 2^c to the answer.
The final algorithm looks like this:
- Iterate i from 30 down to 0.
- If the i-th bit is either set in X or not set in N, do nothing
- Otherwise, count the number of bits from 0 to i-1 that are not set in X. If this number is c, add 2^c to the answer.
This can be implemented in \mathcal{O}(\log N) by maintaining the running sum of bits that are not set in X; however a more naive implementation in \mathcal{O}(\log^2 N) will still be fast enough.
TIME COMPLEXITY:
\mathcal{O}(\log N) per test case.
CODE:
Setter's code (Python)
t=int(input())
for _ in range(t):
n,x=map(int,input().split())
ans=p=0
for i in range(0,30):
if not x&(1<<i):
if n&(1<<i):ans+=(1<<p)
p+=1
print(ans)
Tester's code (C++, tabr)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, x;
cin >> n >> x;
int ans = 0;
for (int i = 29; i >= 0; i--) {
if (~x & (1 << i)) {
ans *= 2;
if (n & (1 << i)) {
ans += 1;
}
}
}
cout << ans << endl;
}
return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, x; cin >> n >> x;
int ans = 0, ct = 31 - __builtin_popcount(x);
for (int bit = 30; bit >= 0; --bit) {
if ((x >> bit) & 1) continue;
--ct;
if ((~n >> bit) & 1) continue;
// Let this be the first bit that is strictly less than n
ans += 1 << ct;
}
cout << ans << '\n';
}
}
