二进制与一 II 题解

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[65], t;

int sum(int x) {
	int ans = 0;
	while (x) {
		ans += x % 2;
		x /= 2;
	}
	return ans;
}

signed main() {
	int T;
	cin >> T;
	while (T--) {
		int n, k;
		cin >> n >> k;
		int x = n;
		if (sum(n) == k) {
			cout << 0 << "\n";
			continue;
		}
		t = 0;
		while (x) {
			a[++t] = x % 2;
			x /= 2;
		}
		if (t <= k)
			cout << (1LL << k) - 1 - n << "\n";
		else {
			int now = 0, one = 0, ans = (1LL << t) + (1LL << (k - 1)) - 1 - n;
			for (int i = t; i >= 1; i--) {
				bool e = (n & (1LL << i - 1));
				if (e) {
					int tmp = now * 2;
					if (i - 1 < k - one || one > k)
						continue;
					tmp *= (1LL << i - 1);
					tmp += (1LL << (i - 1)) - 1 - ((1LL << (i - 1 - (k - one))) - 1);
					one++;
					ans = min(ans, n - tmp);
				}
				now = now * 2 + e;
			}
			now = 0, one = 0;
			for (int i = t; i >= 1; i--) {
				bool e = (n & (1LL << i - 1));
				if (e)
					one++;
				else {
					int tmp = now * 2 + 1;
					if (i - 1 < k - one - 1 || one >= k)
						continue;
					tmp *= (1LL << i - 1);
					if (k - one - 1)
						tmp += (1LL << (k - one - 1)) - 1;
					ans = min(ans, tmp - n);
				}
				now = now * 2 + e;
			}
			cout << ans << "\n";
		}
	}
}