趣题【高级的位运算】题解
ETOI_ 团队 原创题目，团队招人中…
U673078 Seeking
题目描述
已知x xx，求最小的y yy，使得x ⊕ y x \oplus yx⊕y和x & y x \& yx&y均不等于0 00。
输入格式
本题共有T TT组数据。
第一行T ( 1 ≤ T ≤ 10 5 ) T(1\leq T\leq 10^5)T(1≤T≤105)。
接下来的每一组数据，输入一个x xx以询问答案。
输出格式
对于每一个询问的答案，用换行隔开。
输入输出样例 #1
输入 #1
1 1输出 #1
3说明/提示
1 ≤ x ≤ 10 18 1\leq x\leq 10^{18}1≤x≤1018。
本题数据较水，欢迎各种解法。
题解
暴力
#include<iostream>#defineullunsignedlonglongusingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cin>>T;while(T--){ull x;cin>>x;ull y=1;// 暴力查找最小的ywhile(true){if((x^y)!=0&&(x&y)!=0){cout<<y<<"\n";break;}y++;}}return0;}结果：TLE。
显然暴力的方法是行不通的。
正解
看到亦或和与，知道这是一道位运算的题。暴力枚举浪费了很多时间，肯定是行不通的。
思路：位运算+分类讨论。
分类讨论
1.x = 1 x = 1x=1
- y = 1 y = 1y=1：1 & 1 = 1 1 \& 1 = 11&1=1✓，1 ⊕ 1 = 0 1 \oplus 1 = 01⊕1=0✗
- y = 2 y = 2y=2：1 & 2 = 0 1 \& 2 = 01&2=0✗
- y = 3 y = 3y=3：1 & 3 = 1 1 \& 3 = 11&3=1✓，1 ⊕ 3 = 2 1 \oplus 3 = 21⊕3=2✓
结论：x = 1 x = 1x=1时，y = 3 y = 3y=3
2.x > 1 x > 1x>1且为奇数
取y = 1 y = 1y=1：
- x & 1 = 1 ≠ 0 x \& 1 = 1 \neq 0x&1=1=0✓（最低位都是 1）
- x ⊕ 1 = x − 1 ≠ 0 x \oplus 1 = x - 1 \neq 0x⊕1=x−1=0✓（因为x > 1 x > 1x>1）
结论：奇数x > 1 x > 1x>1时，y = 1 y = 1y=1
3.x xx是 2 的幂（x = 2 k , k ≥ 1 x = 2^k, k \geq 1x=2k,k≥1）
取y = x + 1 y = x + 1y=x+1：
- x & ( x + 1 ) = x ≠ 0 x \& (x+1) = x \neq 0x&(x+1)=x=0✓
- x ⊕ ( x + 1 ) = 1 ≠ 0 x \oplus (x+1) = 1 \neq 0x⊕(x+1)=1=0✓
检查更小的y yy：
- y = 1 y = 1y=1：x & 1 = 0 x \& 1 = 0x&1=0✗
- 2 ≤ y < x 2 \leq y < x2≤y<x：这些数的最高位低于x xx，x & y = 0 x \& y = 0x&y=0✗
结论：x xx是 2 的幂时，y = x + 1 y = x + 1y=x+1
4. 一般偶数（非 2 的幂）
设lowbit ( x ) = x & ( − x ) \text{lowbit}(x) = x \& (-x)lowbit(x)=x&(−x)，即x xx的最低位的 1。
取y = lowbit ( x ) y = \text{lowbit}(x)y=lowbit(x)：
- x & y = y ≠ 0 x \& y = y \neq 0x&y=y=0✓
- 因为y < x y < xy<x，所以x ⊕ y ≠ 0 x \oplus y \neq 0x⊕y=0✓
检查比lowbit ( x ) \text{lowbit}(x)lowbit(x)更小的y yy：
这些数的二进制位都在lowbit ( x ) \text{lowbit}(x)lowbit(x)的右侧，而x xx在这些位上都是 0，因此x & y = 0 x \& y = 0x&y=0，不满足条件。
结论：一般偶数时，y = lowbit ( x ) y = \text{lowbit}(x)y=lowbit(x)
时间复杂度
每个查询O ( 1 ) O(1)O(1)，总复杂度O ( T ) O(T)O(T)，可轻松通过T ≤ 10 5 T \leq 10^5T≤105。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cin>>T;while(T--){longlongx;cin>>x;if(x==1){cout<<"3\n";continue;}longlonglowbit=x&-x;if(lowbit==x){// 2的幂且 >1cout<<x+1<<'\n';}else{cout<<lowbit<<'\n';}}return0;}//记得开 long long什么是 lowbit？
lowbit是一个常用的二进制运算术语，表示一个数在二进制表示中最低位的 1 所对应的数值。
数学定义
lowbit ( x ) = x & ( − x ) \text{lowbit}(x) = x \& (-x)lowbit(x)=x&(−x)
其中：
&是按位与运算-x是x的补码表示（即~x + 1）
直观理解
例如x = 12，二进制是1100：
- 最低位的 1 在第 3 位（从右往左数，第 1 位是 2⁰）
- 这对应数值 ( 2^2 = 4 )
所以lowbit(12) = 4
计算原理
x & (-x)为什么能得到最低位的 1？
以x = 12（1100）为例：
x的二进制：...1100-x的计算：先取反...0011，再加 1 得...0100x & (-x)：12: 1100 -12: 0100 (实际高位全是1，这里简写) 与运算: 0100 = 4
关键在于：-x保留了x最低位的 1，并将更高位全部取反，所以x & (-x)只剩下最低位的 1。
常见性质
| 性质 | 说明 |
|---|---|
lowbit(x)一定是 2 的幂 | 因为只保留了一个 1 |
lowbit(x) ≤ x | 最低位不会超过数本身 |
如果x是奇数，lowbit(x) = 1 | 最低位就是 2⁰ |
如果x是 2 的幂，lowbit(x) = x | 整个数只有一个 1 |
应用场景
- 树状数组（Fenwick Tree）：核心操作就是
lowbit - 二进制枚举子集：用于遍历所有子集
- 本题：找到最小的与
x有公共 1 位的数
例子对照表
| x (十进制) | x (二进制) | lowbit(x) | lowbit(x) 二进制 |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 10 | 2 | 10 |
| 3 | 11 | 1 | 1 |
| 4 | 100 | 4 | 100 |
| 5 | 101 | 1 | 1 |
| 6 | 110 | 2 | 10 |
| 7 | 111 | 1 | 1 |
| 8 | 1000 | 8 | 1000 |
| 10 | 1010 | 2 | 10 |
| 12 | 1100 | 4 | 100 |
| 14 | 1110 | 2 | 10 |
代码实现
// 方法1：直接运算longlonglowbit(longlongx){returnx&-x;}// 方法2：用位运算逐步演示longlonglowbit_demo(longlongx){returnx&(~x+1);// ~x + 1 就是 -x}总结
lowbit = 最低位的 1 所代表的数值
一句话记忆：lowbit(x) = x & (-x)，它能把一个数"砍"到只剩下最右边的一个 1。