题目理解

给定一个正整数 $x$，要求找到一个正整数 $y$，使得：

1. $(x \ \& \ y) > 0$（即 $x$ 和 $y$ 在二进制下至少有一位同时为 $1$）
2. $(x \ \oplus \ y) > 0$（即 $x$ 和 $y$ 在二进制下至少有一位不同）

要求输出任意一个满足条件的 $y$。

提示解析

题目提示将 $x$ 分为两种情况：

• $x = 2^k$（即 $x$ 是 $2$ 的幂次）
• $x \neq 2^k$

解题思路

设 $p_i$ 表示 $x$ 的第 $i$ 位（从 $0$ 开始），$q_i$ 表示 $y$ 的第 $i$ 位。

条件翻译：

• $(x \ \& \ y) > 0 \iff \exists i, p_i = q_i = 1$
• $(x \ \oplus \ y) > 0 \iff \exists i, p_i \neq q_i$

情况一：$x \neq 2^k$

此时 $x$ 的二进制表示中至少有两个 $1$。

1. 找到最低位 $k$ 使得 $p_k = 1$（即 $x$ 的最低位 $1$ 的位置）
2. 令 $q_k = 1$，这样满足了第一个条件（$(x \ \& \ y) > 0$）
3. 由于 $x$ 还有另外的 $1$，而 $y$ 只有这一位是 $1$，所以 $x \neq y$，因此 $(x \ \oplus \ y) > 0$ 自动成立

所以此时 $y = 2^k$ 就是一个解。

情况二：$x = 2^k$

此时 $x$ 的二进制表示中只有一个 $1$。

1. 先令 $q_k = 1$，这样满足了第一个条件
2. 但如果 $y$ 只有这一位是 $1$，那么 $y = x$，此时 $x \ \oplus \ y = 0$，不满足第二个条件
3. 因此需要再找一个最低位 $j$ 使得 $p_j = 0$（即 $x$ 在该位为 $0$），令 $q_j = 1$
4. 此时 $y$ 有两位为 $1$，$(x \ \& \ y) = 2^k > 0$，$(x \ \oplus \ y) = 2^j > 0$，满足条件

所以此时 $y = 2^k + 2^j$ 是一个解。

算法实现

标程使用了 lowbit 函数（x & -x）来找到最低位的 $1$。

int w = lowbit(x);  // w = 2^k，其中 k 是最低位 1 的位置
while (!(w ^ x) || !(w & x)) w++;

解释：

• 初始 $w = 2^k$
• 如果 $w \oplus x = 0$，即 $w = x$，说明 $x$ 是 $2$ 的幂，需要进入情况二
• 否则，直接输出 $w$ 即可（情况一）
• 循环中的条件 !(w & x) 实际上永远不会成立（因为 $w$ 始终是 $x$ 的某个位），这个写法可能是为了处理边界情况

更简洁的实现：

int lowbit = x & -x;
if (x != lowbit) {
    cout << lowbit << endl;
} else {
    // x 是 2 的幂，找一个最低的 0 位
    int ans = lowbit;
    for (int j = 0; j < 31; j++) {
        if (!((x >> j) & 1)) {
            ans += (1 << j);
            break;
        }
    }
    cout << ans << endl;
}

时间复杂度

$O(1)$ 每次查询，因为只需检查固定的位数（$32$ 或 $64$ 位）。

完整代码（带注释）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int x;
        cin >> x;
        
        // lowbit = x 的最低位的 1 所表示的值
        int lowbit = x & -x;
        
        if (x != lowbit) {
            // 情况一：x 不是 2 的幂
            cout << lowbit << endl;
        } else {
            // 情况二：x 是 2 的幂
            // 找到最低的 0 位
            int ans = lowbit;
            for (int j = 0; j < 31; j++) {
                if (!((x >> j) & 1)) {
                    ans += (1 << j);
                    break;
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

举例验证