中 进阶
位运算技巧#
一句话答案#
常用位运算：n&(n-1) 去最低位 1、异或找唯一数、n&1 判奇偶、移位代替乘除 2。
核心要点
| 操作 | 表达式 | 用途 |
|---|---|---|
| 判断奇偶 | n&1 | 代替 n%2 |
| 去最低位1 | n&(n-1) | 计数1的个数 |
| 找唯一数 | 全部异或 | 成对抵消 |
| 2的幂判断 | n>0 && (n&(n-1))==0 |
面试回答（2分钟版）
位运算在工程中用得比想象多。最常见的三个技巧：第一，n&1判奇偶，等价于n%2但更快；第二，n&(n-1)可以去掉n二进制表示中最低位的1，反复执行就能统计1的个数，而且判断2的幂也靠它——2的幂二进制只有一个1，n&(n-1)结果为0就是2的幂；第三，全部异或找唯一数，因为相同数异或抵消为0，最后剩下的就是那个只出现一次的。工程层面，HashMap的tableSizeFor用位运算找最近的2的幂，雪花算法通过位移拼接时间戳+机器ID+序列号，Linux文件权限rwx本质也是位运算。不过位运算不是万能的，现代编译器对n/2这类操作会自动优化成移位，所以不必为了性能牺牲可读性。
追问与易错
追问方向：
- “n&(n-1) 的原理？”→ 将 n 的二进制最低位的 1 变为 0；因为 n-1 会使最低位 1 及其右边所有位取反，与 n 做 AND 正好消掉这个 1，常用于统计 1 的个数
- “位运算在实际工程中哪里用到？”→ 权限系统用位掩码（Linux 文件权限 rwx）、布隆过滤器的位数组、HashMap 用 n&(n-1)==0 判断容量是否为 2 的幂、位图统计海量数据去重
- “怎么用位运算判断 2 的幂？”→ n > 0 && (n & (n-1)) == 0；2 的幂的二进制只有一个 1，n&(n-1) 消掉这个 1 后结果为 0
易错点：
- ❌ 位运算总是更快——可读性差且编译器会自动优化
- ❌ 位运算只在算法题中用——HashMap/权限管理等广泛使用