信息技术大学
位运算与数学
数据结构与算法·面试高频 · 第 4 章 算法思想
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
位运算与数学
数据结构与算法·面试高频 · 第 4 章 算法思想
异或性质应用
异或是「不同为真」：自反、交换、结合，成对出现就互相抵消。
三大性质
a^a=0、a^0=a，交换结合可任意重排
找单个
全员异或，成对消光后只剩孤儿
分组找双
按某位 0/1 分两拨，各自再异或出两个
n & (n-1) 技巧
消去最右边的 1：一位一位消，消几次就是 1 的个数。
消除末 1
n&(n−1) 精准抹掉最低位的 1
计数
循环到 0，执行次数即 1 位个数
判 2 的幂
2 的幂仅一位 1，n&(n−1)==0 即是
快速幂
幂次折半：平方一次指数减半，O(log n) 算大幂，负指数取倒数。
折半
x^n = (x²)^(n/2)，奇数额外乘一个 x
取模
每乘一次取一次模，防溢出并保表达式
推广
矩阵快速幂加速线性递推计算
数字溢出处理
加法先移项再比，乘法先除后比：溢出要在发生之前拦截。
加法
a+b>MAX 判 a>MAX−b，先移项防溢出
乘法
a×b>MAX 转 a>MAX/b 的除法预判
中点
mid = l+(r−l)/2，防 (l+r) 先溢出
本节要点
- ✓异或：成对消失，分组找双孤
- ✓n&(n−1)：消末位 1，数 1 判幂
- ✓快速幂：折半取模，log n 量级
- ✓溢出：移项预判，中点偏移
延伸主题：刷只出现一次的数字实现一遍 pow(x,n)
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1两个孤儿数字的题，为什么要按位分组？
参考答案全员异或得到两孤儿的异或值 x，x 任意为 1 的位说明两数在该位不同；按该位把全体分两组，组内成对相消，两组各剩一个孤儿。
2快速幂为什么比连乘快？快在哪？
参考答案连乘是 O(n) 次乘法；折半让指数每次砍半，只需 O(log n) 次。指数 2^30 时从十亿次乘法降到三十次，量级差距随指数指数级拉开。
3mid=(l+r)/2 在什么场景会真的溢出？
参考答案l、r 都接近类型上限时 l+r 先溢出。l+(r−l)/2 数学等价且中间量不超界，是防御性写法——不是每题都触发，但成本为零。