求最小的正整数 y,使得 (x AND y) + (x OR y) = 2025;不存在则输出 −1。
给定整数 x,找最小的正整数 y,使得
其中 AND 是按位与(&),OR 是按位或(|)。如果不存在满足条件的 y,输出 −1。
(x AND y) + (x OR y) = x + y。等式一旦化简,答案就一目了然了。按位与按位或位运算恒等式化简
| 项目 | 说明 |
|---|---|
| 输入 | 一行一个整数 x |
| 输出 | 最小的正整数 y,或 −1 |
| 数据范围 | 0 ≤ x < 2025 |
| 关键恒等式 | (x & y) + (x | y) = x + y |
x + y,方程立刻变成 x + y = 2025y = 2025 − x,答案唯一2025 − x ≤ 0 时(本题数据保证 x < 2025,所以总是有解)位运算的特点是可以逐位拆开看。对某一位,设 x 的该位是 a、y 的该位是 b,两者都只能取 0 或 1。把四种情况全部列出来:
| x 的该位 a | y 的该位 b | a AND b | a OR b | AND + OR | a + b | 是否相等 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | ✅ |
| 0 | 1 | 0 | 1 | 1 | 1 | ✅ |
| 1 | 0 | 0 | 1 | 1 | 1 | ✅ |
| 1 | 1 | 1 | 1 | 2 | 2 | ✅ |
四种情况全部成立,说明每一位都满足;而位与位之间没有进位干扰(这一位的结果不依赖其它位),所以整体相加也相等:
样例输入 x = 1025,输出 1000。我们用两种方式对照。
x + y = 2025 → y = 2025 − 1025 = 1000
✅ y = 1000
1025 的二进制 = 10000000001₂
1000 的二进制 = 1111101000₂
AND = 10000000000₂ = 1024
OR = 1111101001₂ = 1001
1024 + 1001 = 2025 ✓
✅ 恒等式成立,答案正确
| x | 计算 2025 − x | 输出 |
|---|---|---|
| 0 | 2025 | 2025 |
| 1025 | 1000 | 1000 |
| 2024 | 1 | 1 |
| 2025(超范围) | 0 → 不是正整数 | −1 |
把左边化简为 x + y,直接解出 y = 2025 − x
y = target − x,若 y ≤ 0 则输出 −1。本题把 target 换成任意数都成立。从 y = 1 开始逐个试 (x AND y) + (x OR y)
| 方案 | 运算量 | 代码量 |
|---|---|---|
| 套恒等式 | 1 次减法 | 3 行 |
| 枚举验证 | 上界不明 | 10 行以上 |
输入 x,程序会给出 y = 2025 − x,并逐位展示 (x AND y) + (x OR y) 确实等于 2025。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int main() { int x; scanf("%d", &x); // 利用恒等式 (x & y) + (x | y) = x + y // 原式等价于 x + y = 2025 int y = 2025 - x; if (y >= 1) printf("%d\n", y); else printf("-1\n"); return 0; }
2025 − x ≥ 1 恒成立。但把判断写上更稳妥——万一数据范围变了,代码依然正确。这是"防御性编程"的好习惯。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
int y = 2025 - x; | 直接求解 | 恒等式化简后的唯一解 |
if (y >= 1) | 判断是否为正整数 | y = 0 不是正整数 |
printf("-1\n") | 输出无解 | 题目要求的特殊值 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1025 | 1000 | 题面样例 |
0 | 2025 | x = 0 时 y 取到最大 |
2024 | 1 | y 取到最小的正整数 1 |
1 | 2024 | 普通情况 |
2025 | −1 | 超出数据范围,验证 −1 分支 |
2025 − x = 0 时要输出 −1。只用 x、y 两个整数变量。
✅ 这题的价值不在效率,而在发现并运用位运算恒等式——把一道看起来要搜索的题变成一行减法。
// 常用位运算恒等式(都很有用) // (x & y) + (x | y) = x + y AND + OR 抵消 // (x | y) - (x & y) = x ^ y 异或 = 或 - 与 // x & y = (x + y - (x ^ y)) / 2 由上面两式推得 // x | y = (x + y + (x ^ y)) / 2 // 常用位运算操作 int lowbit = x & (-x); // 取最低位的 1 int cnt1 = __builtin_popcount(x); bool pow2 = (x > 0) && ((x & (x - 1)) == 0); // 判断 2 的幂
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 位运算逐位分析 | 把每一位的 4 种情况列全 | 所有位运算等式/不等式的证明 |
| 恒等式化简 | (x&y)+(x|y) → x+y | 位运算与算术混合的题目 |
| 防御性编程 | 把 −1 分支写上以防万一 | 所有有"无解"输出的题目 |
(x AND y) − (x OR y) = 2025,还能化简吗?先用逐位表格列出四种情况,你会发现 AND − OR 只能取 0 或 −1,所以左边永远是非正数,绝不可能等于正的 2025 —— 答案直接是"无解"。