题解 P6861 【[RC-03] 难题】

· · 题解

位运算的题都挺有意思的。

分析：

给一个数 n ,求 x \text{xor} n + x or n 最大， (1\leq x\leq n) 。

首先根据样例分析：

5\to 0101(\text{bin}) 2\to 0010(\text{bin})

异或得 7\to0111(\text{bin}) ， 或得 7\to0111(\text{bin}) ， 和为 14\to1110(\text{bin}) 。

看不出什么 ， 再来想一组样例：

8\to01000(\text{bin}) 7\to00111(\text{bin})

异或得 15\to01111(\text{bin}) ， 或得 15\to01111(\text{bin}) ， 和为 30\to11110(\text{bin}) 。

所以就找到了规律：

找到与 n 异或的值和或的值相等的数。

也就是在二进制下每一位都与 n 不同的数。

换言之，最终的答案就是二进制下 n 的每一位都为 1 的数再乘以 2 。

代码：

#include "cstdio"
#define ull unsigned long long//不开ull见祖宗
ull n, k, ans;
int main() {
    scanf("%llu", &n);
    k = n;
    while (k) {
        k >>= 1;
        ans = ans << 1 | 1;
    }
    printf("%llu", ans << 1);
}