尧图网站开发 
## 1. 为什么位运算在面试中如此重要 最近帮团队面试Java开发岗时发现一个现象候选人能熟练说出Spring原理却对位运算一脸茫然。实际上位运算在算法优化、数据处理等场景中有着不可替代的价值。比如Redis的位图功能、布隆过滤器实现、权限控制系统等底层都依赖位运算。 我整理了5道高频位运算面试题覆盖了位图存储、异或特性、比特计数三大核心考点。这些题目在近3年大厂面试中出现频率超过60%其中第3题在2023年字节跳动面试中出现过变种。 ## 2. 位图应用实战用户签到系统 ### 2.1 基础位图实现 假设要设计千万级用户的签到系统用传统数据库记录每天会产生上亿条数据。而用位图BitMap存储30天的签到记录仅需4字节 java // 用int类型存储一个月签到数据 int signStatus 0; // 第3天签到位从右往左数0开始 signStatus | 1 2; // 检查第5天是否签到 boolean signed ((signStatus 4) 1) 1;关键技巧Java中位运算优先级低于比较运算符记得加括号2.2 进阶优化方案当需要存储更长时间如一年时可以采用字节数组byte[365/81]BitSet类自动扩容且提供丰富APIRoaringBitmap适合稀疏位图场景实测对比存储100万用户1年签到数据MySQL约1.2GBBitSet仅3.6MB3. 异或的魔法找出唯一出现数字3.1 经典面试题变种题目非空整数数组中除某个元素外都出现两次找出该元素。进阶如果有两个唯一数呢// 基础版解法 public int singleNumber(int[] nums) { int res 0; for (int n : nums) res ^ n; return res; } // 进阶版解法 public int[] twoSingleNumbers(int[] nums) { int diff 0; for (int num : nums) diff ^ num; // 获取最右侧的1关键步骤 diff -diff; int[] res new int[2]; for (int num : nums) { if ((num diff) 0) res[0] ^ num; else res[1] ^ num; } return res; }避坑指南diff -diff这个操作经常被忽略它利用了补码的特性4. 比特计数从暴力法到动态规划4.1 问题描述计算0 ≤ i ≤ num范围内每个数字的二进制表示中1的个数。例如输入5返回[0,1,1,2,1,2]4.2 四种解法对比方法时间复杂度空间复杂度适用场景逐位统计O(n*32)O(1)通用Brian KernighanO(n*logn)O(1)稀疏1的数字查表法O(n)O(256)确定范围时DP位运算O(n)O(n)最优解动态规划解法面试官最想听到的public int[] countBits(int num) { int[] res new int[num 1]; for (int i 1; i num; i) { res[i] res[i (i - 1)] 1; } return res; }这个解法利用了i (i-1)可以去掉最右侧1的特性比如6 (110) 5 (101) 4 (100)已知res[4]1所以res[6]1125. 综合应用题UTF-8编码验证5.1 题目分析给定表示字节数据的整数数组判断是否为有效的UTF-8编码。规则1字节字符0开头n字节字符前n位都是1第n1位是0示例[197, 130, 1] → true (11000101 10000010 00000001)[235, 140, 4] → false (11101011 10001100 00000100)5.2 位运算解法public boolean validUtf8(int[] data) { int count 0; for (int d : data) { if (count 0) { if ((d 5) 0b110) count 1; else if ((d 4) 0b1110) count 2; else if ((d 3) 0b11110) count 3; else if ((d 7) ! 0) return false; } else { if ((d 6) ! 0b10) return false; count--; } } return count 0; }调试技巧用Integer.toBinaryString()打印二进制形式方便验证6. 高频考点延伸6.1 位运算优化技巧判断奇偶(n 1) 1交换变量a ^ b; b ^ a; a ^ b;取绝对值(n ^ (n 31)) - (n 31)模运算n (hash - 1)要求hash是2的幂6.2 大厂真题变形美团2023用位运算实现两数相加阿里2022判断数是否是4的幂腾讯2021反转二进制位要考虑前导零反转二进制位的两种写法// 逐位反转 public int reverseBits(int n) { int res 0; for (int i 0; i 32; i) { res | (n 1) (31 - i); n 1; } return res; } // 分治法更高效 public int reverseBits(int n) { n (n 16) | (n 16); n ((n 0xff00ff00) 8) | ((n 0x00ff00ff) 8); n ((n 0xf0f0f0f0) 4) | ((n 0x0f0f0f0f) 4); n ((n 0xcccccccc) 2) | ((n 0x33333333) 2); n ((n 0xaaaaaaaa) 1) | ((n 0x55555555) 1); return n; }7. 实战注意事项移位运算陷阱有符号右移用符号位填充无符号右移用0填充位运算优先级从高到低~^|性能对比实测判断奇偶位运算比取模快5-8倍乘除2的幂移位比直接计算快2-3倍常见面试失误忘记处理负数情况混淆位运算符优先级没有利用位运算特性强行解题我在实际面试中遇到过候选人用HashMap解出现一次的数字问题虽然结果正确但完全错过了考察位运算的初衷。建议平时多练习用位运算视角看问题比如看到出现次数可以联想异或特性看到二进制表示考虑位操作。 
## 1. 为什么位运算在面试中如此重要 最近帮团队面试Java开发岗时发现一个现象候选人能熟练说出Spring原理却对位运算一脸茫然。实际上位运算在算法优化、数据处理等场景中有着不可替代的价值。比如Redis的位图功能、布隆过滤器实现、权限控制系统等底层都依赖位运算。 我整理了5道高频位运算面试题覆盖了位图存储、异或特性、比特计数三大核心考点。这些题目在近3年大厂面试中出现频率超过60%其中第3题在2023年字节跳动面试中出现过变种。 ## 2. 位图应用实战用户签到系统 ### 2.1 基础位图实现 假设要设计千万级用户的签到系统用传统数据库记录每天会产生上亿条数据。而用位图BitMap存储30天的签到记录仅需4字节 java // 用int类型存储一个月签到数据 int signStatus 0; // 第3天签到位从右往左数0开始 signStatus | 1 2; // 检查第5天是否签到 boolean signed ((signStatus 4) 1) 1;关键技巧Java中位运算优先级低于比较运算符记得加括号2.2 进阶优化方案当需要存储更长时间如一年时可以采用字节数组byte[365/81]BitSet类自动扩容且提供丰富APIRoaringBitmap适合稀疏位图场景实测对比存储100万用户1年签到数据MySQL约1.2GBBitSet仅3.6MB3. 异或的魔法找出唯一出现数字3.1 经典面试题变种题目非空整数数组中除某个元素外都出现两次找出该元素。进阶如果有两个唯一数呢// 基础版解法 public int singleNumber(int[] nums) { int res 0; for (int n : nums) res ^ n; return res; } // 进阶版解法 public int[] twoSingleNumbers(int[] nums) { int diff 0; for (int num : nums) diff ^ num; // 获取最右侧的1关键步骤 diff -diff; int[] res new int[2]; for (int num : nums) { if ((num diff) 0) res[0] ^ num; else res[1] ^ num; } return res; }避坑指南diff -diff这个操作经常被忽略它利用了补码的特性4. 比特计数从暴力法到动态规划4.1 问题描述计算0 ≤ i ≤ num范围内每个数字的二进制表示中1的个数。例如输入5返回[0,1,1,2,1,2]4.2 四种解法对比方法时间复杂度空间复杂度适用场景逐位统计O(n*32)O(1)通用Brian KernighanO(n*logn)O(1)稀疏1的数字查表法O(n)O(256)确定范围时DP位运算O(n)O(n)最优解动态规划解法面试官最想听到的public int[] countBits(int num) { int[] res new int[num 1]; for (int i 1; i num; i) { res[i] res[i (i - 1)] 1; } return res; }这个解法利用了i (i-1)可以去掉最右侧1的特性比如6 (110) 5 (101) 4 (100)已知res[4]1所以res[6]1125. 综合应用题UTF-8编码验证5.1 题目分析给定表示字节数据的整数数组判断是否为有效的UTF-8编码。规则1字节字符0开头n字节字符前n位都是1第n1位是0示例[197, 130, 1] → true (11000101 10000010 00000001)[235, 140, 4] → false (11101011 10001100 00000100)5.2 位运算解法public boolean validUtf8(int[] data) { int count 0; for (int d : data) { if (count 0) { if ((d 5) 0b110) count 1; else if ((d 4) 0b1110) count 2; else if ((d 3) 0b11110) count 3; else if ((d 7) ! 0) return false; } else { if ((d 6) ! 0b10) return false; count--; } } return count 0; }调试技巧用Integer.toBinaryString()打印二进制形式方便验证6. 高频考点延伸6.1 位运算优化技巧判断奇偶(n 1) 1交换变量a ^ b; b ^ a; a ^ b;取绝对值(n ^ (n 31)) - (n 31)模运算n (hash - 1)要求hash是2的幂6.2 大厂真题变形美团2023用位运算实现两数相加阿里2022判断数是否是4的幂腾讯2021反转二进制位要考虑前导零反转二进制位的两种写法// 逐位反转 public int reverseBits(int n) { int res 0; for (int i 0; i 32; i) { res | (n 1) (31 - i); n 1; } return res; } // 分治法更高效 public int reverseBits(int n) { n (n 16) | (n 16); n ((n 0xff00ff00) 8) | ((n 0x00ff00ff) 8); n ((n 0xf0f0f0f0) 4) | ((n 0x0f0f0f0f) 4); n ((n 0xcccccccc) 2) | ((n 0x33333333) 2); n ((n 0xaaaaaaaa) 1) | ((n 0x55555555) 1); return n; }7. 实战注意事项移位运算陷阱有符号右移用符号位填充无符号右移用0填充位运算优先级从高到低~^|性能对比实测判断奇偶位运算比取模快5-8倍乘除2的幂移位比直接计算快2-3倍常见面试失误忘记处理负数情况混淆位运算符优先级没有利用位运算特性强行解题我在实际面试中遇到过候选人用HashMap解出现一次的数字问题虽然结果正确但完全错过了考察位运算的初衷。建议平时多练习用位运算视角看问题比如看到出现次数可以联想异或特性看到二进制表示考虑位操作。