趣题【高级的位运算】题解

ETOI_ 团队 原创题目团队招人中…U673078 Seeking题目描述已知x xx求最小的y yy使得x ⊕ y x \oplus yx⊕y和x y x \ yxy均不等于0 00。输入格式本题共有T TT组数据。第一行T ( 1 ≤ T ≤ 10 5 ) T(1\leq T\leq 10^5)T(1≤T≤105)。接下来的每一组数据输入一个x xx以询问答案。输出格式对于每一个询问的答案用换行隔开。输入输出样例 #1输入 #11 1输出 #13说明/提示1 ≤ x ≤ 10 18 1\leq x\leq 10^{18}1≤x≤1018。本题数据较水欢迎各种解法。题解暴力#includeiostream#defineullunsignedlonglongusingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cinT;while(T--){ull x;cinx;ull y1;// 暴力查找最小的ywhile(true){if((x^y)!0(xy)!0){couty\n;break;}y;}}return0;}结果TLE。显然暴力的方法是行不通的。正解看到亦或和与知道这是一道位运算的题。暴力枚举浪费了很多时间肯定是行不通的。思路位运算分类讨论。分类讨论1.x 1 x 1x1y 1 y 1y11 1 1 1 \ 1 1111✓1 ⊕ 1 0 1 \oplus 1 01⊕10✗y 2 y 2y21 2 0 1 \ 2 0120✗y 3 y 3y31 3 1 1 \ 3 1131✓1 ⊕ 3 2 1 \oplus 3 21⊕32✓结论x 1 x 1x1时y 3 y 3y32.x 1 x 1x1且为奇数取y 1 y 1y1x 1 1 ≠ 0 x \ 1 1 \neq 0x110✓最低位都是 1x ⊕ 1 x − 1 ≠ 0 x \oplus 1 x - 1 \neq 0x⊕1x−10✓因为x 1 x 1x1结论奇数x 1 x 1x1时y 1 y 1y13.x xx是 2 的幂x 2 k , k ≥ 1 x 2^k, k \geq 1x2k,k≥1取y x 1 y x 1yx1x ( x 1 ) x ≠ 0 x \ (x1) x \neq 0x(x1)x0✓x ⊕ ( x 1 ) 1 ≠ 0 x \oplus (x1) 1 \neq 0x⊕(x1)10✓检查更小的y yyy 1 y 1y1x 1 0 x \ 1 0x10✗2 ≤ y x 2 \leq y x2≤yx这些数的最高位低于x xxx y 0 x \ y 0xy0✗结论x xx是 2 的幂时y x 1 y x 1yx14. 一般偶数非 2 的幂设lowbit ( x ) x ( − x ) \text{lowbit}(x) x \ (-x)lowbit(x)x(−x)即x xx的最低位的 1。取y lowbit ( x ) y \text{lowbit}(x)ylowbit(x)x y y ≠ 0 x \ y y \neq 0xyy0✓因为y x y xyx所以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 0xy0不满足条件。结论一般偶数时y lowbit ( x ) y \text{lowbit}(x)ylowbit(x)时间复杂度每个查询O ( 1 ) O(1)O(1)总复杂度O ( T ) O(T)O(T)可轻松通过T ≤ 10 5 T \leq 10^5T≤105。代码实现#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cinT;while(T--){longlongx;cinx;if(x1){cout3\n;continue;}longlonglowbitx-x;if(lowbitx){// 2的幂且 1coutx1\n;}else{coutlowbit\n;}}return0;}//记得开 long long什么是 lowbitlowbit是一个常用的二进制运算术语表示一个数在二进制表示中最低位的 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 121100为例x的二进制...1100-x的计算先取反...0011再加 1 得...0100x (-x)12: 1100 -12: 0100 (实际高位全是1这里简写) 与运算: 0100 4关键在于-x保留了x最低位的 1并将更高位全部取反所以x (-x)只剩下最低位的 1。常见性质性质说明lowbit(x)一定是 2 的幂因为只保留了一个 1lowbit(x) ≤ x最低位不会超过数本身如果x是奇数lowbit(x) 1最低位就是 2⁰如果x是 2 的幂lowbit(x) x整个数只有一个 1应用场景树状数组Fenwick Tree核心操作就是lowbit二进制枚举子集用于遍历所有子集本题找到最小的与x有公共 1 位的数例子对照表x (十进制)x (二进制)lowbit(x)lowbit(x) 二进制11112102103111141004100510111611021071111181000810001010102101211004100141110210代码实现// 方法1直接运算longlonglowbit(longlongx){returnx-x;}// 方法2用位运算逐步演示longlonglowbit_demo(longlongx){returnx(~x1);// ~x 1 就是 -x}总结lowbit 最低位的 1 所代表的数值一句话记忆lowbit(x) x (-x)它能把一个数砍到只剩下最右边的一个 1。