CWOI S C0327 B 或

題意

U2FsdGVkX1+D4A6QfCouIQBuNbTwssLV3uusFcpmbnb5RSEe4lLnhIgliMrCJZQP
or6+uBxEqSKqU8YRPzzrIEs/knK5/Y/T/Mdp9BGdq37PaMf80RJBtza1waVZv2uf
s7kALpfRDqlLO9umT0DGFbsUW492vwDb0rcPXrAceN6tNYacsBv0+Uk61mlo+7ng

解析

假設 L 和 R 的二進位制表示中，有共同的一段字首，則可以把這段字首忽略掉，因為不管怎麼取，這段字首的值都是一樣的。為了方便，不妨把這段相同字首全部變成 0。

假設 L 和 R 最高的不同位為 k，即 L 的第 k 位為 0 且 R 的第 k 位為 1，且比 k 更高的位全部為 0。我們分別考慮一下幾段對答案的貢獻：

• $[L, 2^{k}-1]$：這一段能表示出來的值顯然是 $[L, 2^{k}-1]$。
• $[2^{k}, R]$：下界顯然是 $2^{k}$，因為任意兩個正整數或起來一定不小於原來那兩個正整數。對於上界，假設 R 第二高的為 1 的位是 p，那麼 p 以下的所有位都可以任意取，就是 $2^{k}+2^{p+1}-1$。如果 $R=2^{k}$，即沒有第二高的為 1 位，可以在實現的時候把 p 當作 -1，式子仍然成立。所以能表示出來的值是 $[2^{k}, 2^{k} +2^{p+1}-1]$。
• 以上兩個組合到一起：把 $2^{k}$ 和第一個區間裡每個數組合，可以得到：$[2^{k} +2^{k+1}-1]$。

把這三段區間求並即可。

實現

int main()
{
	u64 l, r;
	std::cin >> l >> r;

	if (l == r) {
		std::cout << 1 << std::endl;
		return 0;
	}

	int k = 63;
	while (k >= 0) {
		if (((l >> k) & 1) != ((r >> k) & 1)) break;
		l &= (-1ull) ^ (1ull << k);
		r &= (-1ull) ^ (1ull << k);
		k--;
	}

	int p = k - 1;
	while (p >= 0) {
		if ((r >> p) & 1) break;
		p--;
	}

	u64 ans = (1ull << (k + 1)) - l;
	if (l > (1ull << (p + 1))) ans -= l - (1ull << (p + 1));
	std::cout << ans << std::endl;
}