面试必刷！Java 位运算 5 道高频题精讲（位图+异或+比特计数）

面试必刷Java 位运算 5 道高频题精讲位图异或比特计数位运算堪称算法面试中的空间优化神器其核心优势在于直接操作二进制比特位运算速度远超普通算术运算且能以 O(1) 常数空间高效解决哈希判重、数字查找、加减求和等经典问题是大厂面试中不可或缺的高频考点也是区分普通开发者与算法高手的关键。全程使用Java 语言精讲 5 道经典位运算面试题从解题思路拆解、核心技巧应用到完整代码实现一次性吃透位运算的核心玩法。一、位运算核心技巧Java 版位运算的所有解题思路本质上都是基于以下 5 个基础操作的组合与延伸先熟练掌握这些基础再做面试题就能事半功倍 按位与两个二进制位均为 1 时结果为 1否则为 0。核心用途是判断某一位是否为 1也可用于提取指定比特位比如判断奇数x 1 1。|按位或两个二进制位任意一个为 1 时结果为 1否则为 0。核心用途是将某一位设置为 1不影响其他比特位的原有值。^异或两个二进制位相同为 0不同为 1自带“消消乐”特性——相同数字异或后会抵消x ^ x 00 异或任何数字都等于该数字本身0 ^ x x这是解决“唯一数字”“缺失数字”问题的核心。左移将二进制位整体向左移动指定位数右边补 0等价于对数字乘以 2 的 n 次方n 为移动位数运算效率远高于乘法。右移将二进制位整体向右移动指定位数左边补符号位正数补 0负数补 1等价于对数字除以 2 的 n 次方n 为移动位数向下取整。二、5 道高频位运算题Java 完整代码1. 判定字符是否唯一面试题 01.01题目判断一个字符串中的所有字符是否都唯一要求不使用额外的数据结构如 HashSet、HashMap 等尽量节省空间。核心思路利用 Java 中 int 类型的 32 个比特位实现“位图”功能——假设字符串仅包含小写字母共 26 个用每一个比特位对应一个字母比特位为 1 表示该字母已出现为 0 表示未出现无需额外空间即可完成判重。同时利用鸽巢原理若字符串长度超过 26必然存在重复字符可直接返回 false提升效率。class Solution { public boolean isUnique(String astr) { // 鸽巢原理小写字母共26个长度超过26必重复直接返回false if (astr.length() 26) { return false; } // 位图用int的32个比特位记录每个小写字母是否出现初始值为0所有位均为0 int bitMap 0; // 遍历字符串的每一个字符 for (int i 0; i astr.length(); i) { // 计算当前字符对应的比特位索引a对应0b对应1...z对应25 int x astr.charAt(i) - a; // 右移x位后与1按位与判断该比特位是否已为1即字符是否已出现 if (((bitMap x) 1) 1) { return false; } // 将该比特位置为1标记字符已出现1左移x位后与bitMap按位或 bitMap | 1 x; } // 遍历结束未发现重复返回true return true; } }2. 丢失的数字268题目给定一个包含 [0, n] 中 n 个整数的数组 nums找出 [0, n] 这个范围内没有出现在数组中的那个数字要求尽量优化时间和空间复杂度。核心思路利用异或的“消消乐”特性解题——将数组中所有元素与 [0, n] 范围内的所有数字全部异或由于相同数字异或后会抵消为 0最终剩余的结果就是缺失的数字。该方法时间复杂度为 O(n)空间复杂度为 O(1)是最优解法。class Solution { public int missingNumber(int[] nums) { // 初始化结果变量用于存储最终缺失的数字 int ret 0; // 第一步异或数组中的所有元素相同元素会相互抵消 for (int x : nums) { ret ^ x; } // 第二步异或0到n的所有数字nums长度为n故范围是0~nums.length for (int i 0; i nums.length; i) { ret ^ i; } // 最终ret即为缺失的数字所有重复数字抵消仅剩缺失的数字 return ret; } }3. 两整数之和371题目不使用、-运算符计算两个整数 a 和 b 的和要求仅使用位运算实现。核心思路位运算模拟加法的核心的是拆分“无进位加法”和“进位”两部分循环处理直到进位为 0异或^实现无进位加法即两个数字相加时不考虑进位的结果比如 110101000。与 左移1计算进位——两个数字的对应比特位均为 1 时才会产生进位按位与后左移 1 位即为进位值。循环更新无进位结果和进位值直到进位为 0此时无进位结果就是两个数字的和。class Solution { public int getSum(int a, int b) { // 循环处理进位直到进位为0此时a即为最终和 while (b ! 0) { // x存储无进位加法的结果 int x a ^ b; // 计算进位按位与获取需要进位的位左移1位得到进位值 // 此处用int接收即可Java中会自动处理符号位 int carry (a b) 1; // 更新a为无进位结果b为进位值 a x; b carry; } // 进位为0时a就是两数之和 return a; } }4. 只出现一次的数字 II137题目给定一个整数数组 nums其中除了一个数字只出现一次之外其余每个数字都恰好出现 3 次找出那个只出现一次的数字要求优化空间复杂度。核心思路利用比特位统计法解题——int 类型有 32 个比特位遍历每一个比特位统计数组中所有数字在该位上 1 的总个数由于除目标数字外其余数字均出现 3 次因此总个数对 3 取余后若余数为 1说明目标数字的该比特位为 1若余数为 0说明该比特位为 0最终将所有比特位组合起来即可得到目标数字。class Solution { public int singleNumber(int[] nums) { // 初始化结果变量用于存储只出现一次的数字 int ret 0; // 遍历int类型的32个比特位从最低位到最高位 for (int i 0; i 32; i) { // 统计当前比特位上1的总个数 int sum 0; for (int x : nums) { // 右移i位将当前比特位移到最低位与1按位与判断是否为1 if (((x i) 1) 1) { sum; } } // 对3取余余数为1则目标数字该比特位为1否则为0 sum % 3; if (sum 1) { // 将该比特位置为1更新结果 ret | 1 i; } } // 最终ret即为只出现一次的数字 return ret; } }5. 消失的两个数字面试题 17.19题目给定一个包含 1~N 中 N-2 个数字的数组 nums找出 1~N 中缺失的两个数字要求时间复杂度为 O(N)空间复杂度为 O(1)。核心思路基于异或特性延伸分三步拆解问题实现无额外空间查找两个缺失数字全部异或将数组中所有元素与 1~N此处 N 数组长度 2的所有数字异或最终得到的结果是两个缺失数字的异或值a^b因为其他数字均出现两次会相互抵消。找最低位不同的位 diff两个不同数字的异或值中至少有一位为 1找到最右边的那一位diff该位表示两个缺失数字在这一位上的值不同一个为 0一个为 1。按 diff 位分组异或将数组元素和 1~N 的数字按 diff 位的值0 或 1分成两组每组内异或最终两组的结果分别就是两个缺失数字相同数字抵消仅剩缺失数字。class Solution { public int[] missingTwo(int[] nums) { // tmp用于存储两个缺失数字的异或值a^b int tmp 0; // 1. 异或数组所有元素 1~n2n为数组长度N n2的所有数字 for (int x : nums) { tmp ^ x; } int n nums.length; for (int i 1; i n 2; i) { tmp ^ i; } // 2. 找到两个缺失数字最低位不同的位置diff int diff 0; while (true) { // 右移diff位与1按位与判断该位是否为1即两个数字该位不同 if (((tmp diff) 1) 1) { break; } diff; } // 3. 按diff位分组异或分离两个缺失数字 int[] ret new int[2]; // 存储两个缺失数字 // 先分组异或数组元素 for (int x : nums) { if (((x diff) 1) 1) { ret[1] ^ x; } else { ret[0] ^ x; } } // 再分组异或1~n2的数字抵消重复项得到缺失数字 for (int i 1; i n 2; i) { if (((i diff) 1) 1) { ret[1] ^ i; } else { ret[0] ^ i; } } // 返回两个缺失数字顺序不影响题目无要求 return ret; } }三、位运算解题总结Java 开发者必看字符重复/存在性问题→ 用位图int 比特位利用 int 32 个比特位的空间高效记录元素是否出现无需额外数据结构空间复杂度直接优化到 O(1)适合字符、小范围数字的判重场景。找缺失数字/唯一数字→ 用异或消消乐核心利用“相同数字异或为 0、0 异或任何数为自身”的特性抵消重复元素快速定位唯一或缺失的数字时间复杂度 O(n)空间复杂度 O(1)。不使用加减求和→ 异或无进位 与移位进位用位运算模拟加法的两个核心步骤循环处理进位直到进位为 0即可得到最终和完美避开加减运算符的限制。按次数找数字→比特位统计 取余针对“一个数字出现 k 次其余出现 m 次”的问题统计每一位 1 的个数对 m 取余余数对应目标数字的比特位精准定位目标数字。以上 5 道题覆盖了位运算 90% 的面试场景无论是基础的位图应用、异或特性还是进阶的分组异或、比特位统计都是大厂面试中高频出现的考点。吃透这些题目掌握背后的解题思路和技巧面试遇到位运算相关题目就能直接秒杀轻松拿下加分项