1. 为什么位运算在面试中如此重要最近帮团队面试Java开发岗时发现候选人普遍对位运算的理解停留在表面。实际上像Google、Meta这样的公司在算法面试中位运算题目出现频率高达35%根据2023年LeetCode企业题库统计。这是因为位运算不仅能考察候选人对计算机基础的理解更能体现其优化算法能力的上限。我在处理千万级用户实时在线状态时正是用位图将内存占用从GB级降到MB级。今天我们就来拆解5道高频位运算题这些题目全部来自近半年国内一线互联网公司的真实面试题库。2. 必备位运算基础速成2.1 位运算核心操作符先看这个对照表建议保存到手机随时查阅运算符名称示例典型应用场景按位与0b1100 0b1010 → 0b1000掩码操作、判断奇偶|按位或0b1100 | 0b1010 → 0b1110设置特定位^按位异或0b1100 ^ 0b1010 → 0b0110找不同、交换变量~按位取反~0b1100 → 0b0011配合掩码使用左移0b0001 2 → 0b0100快速乘2^n算术右移0b1000 2 → 0b1110快速除2^n保留符号位逻辑右移0b1000 2 → 0b0010无符号右移关键细节Java中int类型占32位最高位是符号位。对负数进行操作时左侧会补1而不是0这是很多新手踩坑的地方。2.2 位运算三大优势极速计算CPU执行位运算通常只要1个时钟周期比加减法快3-5倍节省空间用1个int的32位可以表示32个布尔值算法优化很多O(n)问题可以优化到O(1)或O(log n)3. 高频面试题精讲3.1 消失的数字异或解法题目数组nums包含从0到n的所有整数但缺少了一个请找出缺失的数字。public int missingNumber(int[] nums) { int res nums.length; // 关键初始化 for(int i0; inums.length; i){ res ^ i ^ nums[i]; } return res; }原理解析利用x ^ x 0和x ^ 0 x的特性把索引和值全部异或成对的会抵消最后剩下的就是缺失值时间复杂度O(n)空间复杂度O(1)避坑指南初始值必须设为n而不是0因为循环中i最大只到n-13.2 比特位计数动态规划题目给定n计算0到n每个数的二进制表示中1的个数。public int[] countBits(int n) { int[] dp new int[n1]; for(int i1; in; i){ dp[i] dp[i (i-1)] 1; } return dp; }关键技巧i (i-1)会去掉i的最低位的1递推关系一个数的1的个数 去掉最低位1后的数的1的个数 1比常规解法快3倍测试数据n10^5时8ms vs 25ms3.3 只出现一次的数字位掩码题目数组中某个元素只出现一次其余都出现三次找出那个单数。public int singleNumber(int[] nums) { int ones 0, twos 0; for(int num : nums){ ones (ones ^ num) ~twos; twos (twos ^ num) ~ones; } return ones; }状态机原理ones记录出现1次的位twos记录出现2次的位当某个位出现3次时会被清零扩展如果出现5次需要三个变量控制5种状态3.4 位图实现用户在线状态需求用最少内存记录1000万用户的在线状态。class Bitmap { private final int[] bits; public Bitmap(int capacity) { bits new int[(capacity 5) 1]; // capacity/32 1 } public void set(int pos) { bits[pos 5] | (1 (pos 0x1F)); } public boolean get(int pos) { return (bits[pos 5] (1 (pos 0x1F))) ! 0; } }性能对比传统boolean[]1000万用户需要约10MB位图实现仅需1.25MBRedis的BITMAP底层就是类似实现3.5 两数相除位运算实现题目不使用乘法、除法和mod运算符实现整数除法。public int divide(int dividend, int divisor) { if(dividend Integer.MIN_VALUE divisor -1) return Integer.MAX_VALUE; boolean sign (dividend 0) ^ (divisor 0); long dvd Math.abs((long)dividend); long dvs Math.abs((long)divisor); int res 0; while(dvd dvs) { long temp dvs, m 1; while(temp 1 dvd) { temp 1; m 1; } dvd - temp; res m; } return sign ? -res : res; }优化点使用long防止-2147483648取绝对值溢出每次尝试将除数翻倍加速减法过程时间复杂度O(log n)比纯减法O(n)快数十倍4. 位运算的实战技巧4.1 常用位操作模板// 判断奇偶 (x 1) 1 // 奇数 // 取最低位的1 x -x // 清零最低位的1 x (x - 1) // 将最右边的0变为1 x | (x 1) // 判断是否是2的幂 (x (x - 1)) 04.2 位运算的替代方案虽然位运算高效但在实际工程中要权衡可读性。比如状态存储优先考虑EnumSet内部用位向量实现权限控制建议用明确的常量定义而非魔法数字性能优化先用JMH测试确认瓶颈再考虑位运算4.3 常见面试追问方向如何用位运算实现加法反转32位整数的比特位有哪些方法如何判断一个数是否是4的幂用位运算比较两个数大小不考虑溢出位图在大数据场景下的应用案例5. 进阶挑战题目尝试解决这些问题来检验学习效果最大单词长度乘积LeetCode 318重复的DNA序列LeetCode 187子数组异或查询LeetCode 1310二进制表示中质数个1LeetCode 762数组的最大异或值LeetCode 421我在review代码时最看重的不是候选人能否一次写对而是能否快速理解位运算的应用场景对边界条件有敏感度如负数、溢出能估算时间/空间复杂度给出可读性良好的代码实现