CF-484A Bits 题解

题目大意

给你一个范围$[l,r]$，问在这个范围中二进制中1最多且最小的数是什么。

解题思路

想了几种方法都是错的。。

想到了可以用全是1的数来计算。

但是没想到这个方法。。

感觉写题就总是抓不住那重要的一点。。

不过写题还是有好处，确实位运算不是很熟悉。

暴露了很多自己的弱点。

先假设一个全是1的数，如果这个数在范围中，那么这个数就是答案。

如果把第i位换成0，这个数会小于l，则这一位是不能换的。

否则就将这一位换成0。

这个方法真的好妙啊。

完整代码

#include <iostream>
#include <string>
#include <queue>
#include <stack>
using namespace std;

typedef long long ll;

int main() {
	int t;
	cin >> t;
	while (t--) {
		ll l, r;
		cin >> l >> r;
		ll ans = (1LL << 63) - 1LL;
		for (int i = 62; ~i; i--) {
			if (ans >= l && ans <= r)	break;
			if ((ans ^ (1LL << i)) < l)	continue;
			ans ^= (1LL << i);
		}
		cout << ans << endl;
	}
}