1. 位运算为什么能成为Java面试的“试金石”1.1 面试官考位运算到底在考什么不知道你有没有这种经历刷了三个月LeetCode数组、链表、哈希表、动态规划都过了一遍结果一进面试间面试官上来就抛一句“给你一个数组只有一个数出现一次其他数都出现两次怎么找出它”典型的位运算题。很多人第一反应是HashMap答案没错但面试官眉头一皱继续问“能不能不用额外空间”就是这一句“能不能不用额外空间”把位运算推上了Java面试高频考点的位置。它考察的绝不仅仅是“你会不会背公式”而是你对计算机底层数据存储的理解整数到底怎么存、补码的运算规则是什么、为什么异或满足交换律和结合律、位运算和算术运算在执行层面有哪些差异。这些知识点平时写业务代码可能三年都用不上一回但它恰恰是区分“背题型选手”和“真正理解型选手”的分水岭。我这几年面过不少人也帮朋友做过模拟面试一个很明显的规律是位运算题目如果候选人能在五分钟之内把思路讲清楚并且代码一次跑通那么他大概率对Java基础掌握得很扎实。反过来如果支支吾吾只记得“用异或”但说不出为什么那后面面Java内存模型、HashMap原理这些题多半也会露馅。所以面试官不是真要在生产环境里让你用位运算写业务而是借这几道小题目探测你的计算机基本功。更实际的一点是位运算题往往可以连续出变种从“只出现一次的数字”到“两个只出现一次的数字”从“统计1的个数”到“判断2的幂”从“位图判重”到“布隆过滤器”。一道基础题能牵出一串知识点面试官手里等于拿到了一个“连环炮”既能测深度又能测广度。这也是为什么标题里的“位图异或比特计数”这三个点几乎是Java位运算面试里绕不开的组合拳。1.2 必备基础Java位运算的常见写法先花三分钟把基础过一遍后面讲题目的时候不卡壳。Java里的位运算一共六类按位与、按位或|、按位异或^、按位取反~、左移、右移还有一个容易被忽略的无符号右移。这里有几个我经常提醒学生的细节。第一按位异或^的规则是“相同为0不同为1”它天然自带“消消乐”属性a ^ a 00 ^ a a而且满足交换律和结合律。这意味着你不管怎么调换运算顺序结果都一样这是后面所有异或题解法的理论根基。第二按位与可以用来取位、清位比如n (n - 1)这个经典操作的作用是“把整数最低位的1变成0”。第三Java的整数默认是int占32位高位是符号位所以负数用补码表示。补码这个东西面试官特别爱追问比如-1的二进制是全1取最低位1的写法n (-n)能直接拿到一个数最右边那个1的位置原理就藏在“取反加一”里。再补充一个实战中的优先级问题。Java里位运算符的优先级比相等运算符低比赋值运算符高很多初学者写if ((a b) 0)会漏括号编译直接报错。我的习惯是全加上括号宁可多写两个括号也不要让面试官在代码上看你犹豫。还有一个特别容易混淆的点和的区别。是带符号右移左边补的是符号位负数右移后还是负数是无符号右移左边一律补0。统计二进制1的个数时如果循环里写成n n 1遇到负数就死循环了必须用。这个坑我在面试现场见过不止一次后面“避坑清单”里我会再强调。2. 第一道高频题只出现一次的数字异或的经典战场2.1 题目与常规思路先看最经典的LeetCode 136题一个整型数组里除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现一次的元素。要求时间复杂度O(n)空间复杂度O(1)。不假思索的做法是哈希表遍历一遍把元素塞进HashMap第二次出现就删掉最后剩下的就是答案。代码好写思路也好懂但空间复杂度是O(n)。面试官让你优化九成是往“位运算”方向引导。另有解法是先排序再遍历时间复杂度O(n log n)通常面试官看一眼就不会让你往下写了。这道题我建议你从数学的角度再想一遍。异或满足交换律和结合律对于任意整数aa ^ a 0。那么多整数异或在一起出现偶数次的数全部“抵消”成0最后剩下的就是那个落单的数。这就像一群人两两分组跳舞最后一支舞跳完剩下没人配对的那个就是要找的人。2.2 异或解法推导与实现直接上代码public int singleNumber(int[] nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; }就这么简单五六行搞定。初始值为什么是0因为0 ^ x x不会影响异或结果的累积。遍历顺序无所谓因为异或满足交换律和结合律你把数组倒过来遍历答案也一样。我遇到不少人在看懂解法后有一个疑问如果数组是[1, 2, 3, 1, 2]那执行过程是不是要手动模拟一遍才知道最终结果是3其实不需要你只需要抓住一个核心结论异或运算在“统计奇偶次数”这件事上是精确的。三次异或同一个数等于它本身出现奇数次会留下痕迹出现偶数次会清零。所以哪怕是[1, 1, 1, 2, 2, 2, 3]最后结果依然是3因为这题三个1异或完等于1相当于奇数个1最终还是“有”三个2异或完等于2最后1 ^ 2 ^ 3等于啥你自己算反正原理是一样的。面试时我建议这样铺开讲先解释异或三条性质再说“因为其他数都出现两次异或后会归零最终结果就是唯一出现一次的数”最后补一句“时间复杂度O(n)空间复杂度O(1)”。注意要把空间复杂度O(1)主动说出来那才是这题的考点。2.3 追问点从1个到多个变种题怎么接面试官很少问完一题就放你走的他一定会顺藤摸瓜。第一问如果改成“只有一个数出现奇数次其他数出现偶数次”还适用吗适用因为异或只关心奇偶性跟“是不是出现一次”没本质区别。第二问如果改成“其他数都出现三次只有一个出现一次”异或还行不行这时候同样套路就行不通了因为三个一样的数异或完还是它本身抵消不掉。标准解法是统计每一位上1出现的次数对3取模。这其实就是“位计数”思想的变体和后面聊的比特计数是同一个家族。第三问如果改成“有两个数只出现一次其他数都出现两次”这就是LeetCode 260题我会在下一章专门讲。面试官通过这种连续追问能很快看出你是背了一道题还是真正理解了位运算。所以我的建议是刷题时把同一思路下的变种题一起刷比如136、137、260三题放在同一天做效果比单刷好得多。3. 第二道高频题两个单身狗异或分组进阶版3.1 题目描述与破题思路LeetCode 260题一个整型数组里恰好有两个元素只出现一次其余所有元素都出现两次。找出这两个只出现一次的元素。要求同样O(n)时间O(1)空间。很多人的第一反应是“能不能用两次singleNumber的解法”不行因为第一次异或完得到的不是某个数的值而是a和b两个数的异或结果xor a ^ b。你没法直接从xor同时还原出a和b。但这道题的精妙之处在于xor作为a ^ b它里面每一个为1的二进制位都意味着a和b在这一位上是不同的。我们把数组里的数按照这一位划分成两组这一位是0的一组这一位是1的一组。a和b必然被分到不同组而其他出现两次的数要么两个都在同一组且成对出现要么被分组后依然能两两抵消。所以对每一组分别做全员异或就能分别得到a和b。这个思路用生活类比解释就是一群人里有两个落单的你不知道具体是谁但你知道他俩在某个特征上不一样比如戴不戴帽子。让所有人按这个特征分成两队每队里落单的人就只剩一个了再用上一题的“全员异或”分别找出来。3.2 找出分组依据与完整代码问题来了怎么从xor里找一个“这一位不同”的特征位最常用的就是取最低位的1mask xor (-xor)。注意-xor就是取反加一这样写能直接保留最低位的1其他位全部清零。我见过有人写成mask 1那就错了因为a ^ b的最低位不一定就是1必须动态计算。完整代码如下public int[] singleNumber(int[] nums) { int xor 0; for (int num : nums) { xor ^ num; } // 取最低位的1作为分组依据 int mask xor (-xor); int a 0, b 0; for (int num : nums) { if ((num mask) 0) { a ^ num; } else { b ^ num; } } return new int[]{a, b}; }这里有几个细节要扣。第一mask可能为负数吗mask是int类型如果xor本身是Integer.MIN_VALUE取负会溢出回到自身但mask仍然等于xor分组依然正确所以不用担心。第二分组条件(n mask) 0表示这一位是0的分到a组注意这里必须加括号因为Java里优先级高于不写括号会先比较num和mask再对结果做与运算直接编译错。另外我建议你在面试时手动模拟一个小例子比如[1, 2, 1, 3, 2, 5]全部异或得到6二进制110最低位1是第1位从右往左数第0位为最低位mask 2。然后根据第1位分组1和3和5的第1位分别是0、1、02是1分组后a组是1、1、5异或得5b组是2、3、2异或得3答案就是5和3。这样讲面试官会觉得你是真懂而不是背代码。3.3 变式汉明距离与脑洞题260题常见的变形是LeetCode 461题汉明距离两个整数对应二进制位不同的个数。最直接的解法就是先将两个数异或然后统计结果中1的个数。统计1的个数用的就是下一章要讲的比特计数。我面试时还见过一个有意思的追问给你两个数不用加减乘除实现加法。那也是位运算的用武之地通过a ^ b算无进位和通过(a b) 1算进位循环直到进位为0。这道题作为附加题出现频率不低建议你顺手也刷了。刷位运算题有个经验别只刷“标准题”要配合“变形题”一起看。比如260题刷完可以立刻做一下“找出数组中缺失的那个数”268题它本质是异或的另一种应用把数组下标和数据本身全部异或剩下的就是缺失值。这种串法刷下来你脑子里会形成一张位运算“知识网”面试时不管从哪个角度切入都能接住。4. 第三道高频题比特计数——统计二进制中1的个数4.1 常见解法对比比特计数的经典题是LeetCode 191题统计无符号整数的比特位中1的个数以及LeetCode 338题给一个n返回0到n每个数的二进制中1的个数。这组题属于“一题多解”的典型面试素材解法至少四类面试官让你全部列出也不奇怪。解法核心思路时间复杂度额外空间循环右移逐位检查n 1然后n 1O(k)k是二进制位数O(1)Brian Kernighan反复执行n (n - 1)每执行一次消掉一个1O(m)m是1的个数O(1)查表法预先生成0~255的1的个数表按字节查表累加O(1)实际是常数轮查表O(256)内置APIInteger.bitCount(n)底层用分治法无动态规划count[i] count[i 1] (i 1)O(n)O(n)面试时怎么选我建议先答Brian Kernighan因为它代码短、原理典型还能顺便引出n (n - 1)这个高频操作。第二步再提Integer.bitCount但要强调它的底层是“每两位一组统计再逐级合并”的分治思想。第三步可以把查表法或循环右移作为补充展示一下知识面。4.2 Brian Kernighan算法是怎么来的很多人背下了n (n - 1)这个操作但不知道它为什么能去掉最低位的1。我用人话说一下。n - 1做的事情是把n从最低位开始遇到的第一个1变成0这个1后面所有0都变成1。比如n 12二进制是1100n - 1 11二进制是1011。把1100和1011做按位与得到1000正好把原数最低位的那个1消掉了而更高位保持不变。所以“反复执行n (n - 1)”的意思是每次消掉一个最低位的1循环次数就等于二进制中1的个数。代码极简public int hammingWeight(int n) { int count 0; while (n ! 0) { n (n - 1); count; } return count; }注意这里虽然函数参数经常写int n但LeetCode 191题目原意是按无符号处理。Java的int有符号如果是负数用n ! 0做循环条件依然能正确退出因为负数的二进制表示中1的个数也是有限多个消到0为止。不过如果你在循环体里写n n 1负数会高位补1永远不是0直接死循环。正确做法是用n 1做逐位检查。4.3 动态规划与查表法的实际取舍LeetCode 338题要求一次性返回0到n每个数的1的个数。如果对每个数都单独用Brian Kernighan总复杂度是O(n * m)还能接受但有更漂亮的递推count[i] count[i 1] (i 1)。原理很简单i右移一位二进制整体挪动最高位移掉一个i的最低位决定最后加不加1。public int[] countBits(int n) { int[] dp new int[n 1]; for (int i 1; i n; i) { dp[i] dp[i 1] (i 1); } return dp; }这个递推式在面试中写出来一般面试官会眼睛一亮因为它既展示了动态规划思想又用到位运算缩短代码。要注意的是dp[0]默认为0循环从i 1开始否则会越界。查表法的思路则是先把0到255每个数的1的个数存在一个长度为256的数组里然后对任意int拆成4个字节分别查表相加。查表法在极端性能要求下比逐位循环快因为循环次数固定为4次。柯南道尔说过一句话很适合这里排除所有不可能的剩下的就算再不可思议那也是真相。面试时你不需要真的把所有解法都写一遍但至少要对每种解法的取舍心中有数别被追问时卡住。5. 第四道高频题位图BitMap实现海量数据判重5.1 位图是什么内存怎么算位图BitMap是和位运算紧密相关的数据结构面试中出现频率不亚于纯异或题。它的核心思想是用一位二进制位表示一个“状态”通常0表示不存在1表示存在。你有一个巨大的整数集合想快速判断某个数是否出现过用HashSet当然可以但假设你有1亿个不重复的int要判重HashSet光是存这些元素就要约800MB内存4字节*1亿再加对象头等开销而如果用位图把数字范围映射到位数组的索引上1亿个bit只需要约12.5MB。用生活类比讲位图特别好懂想象你在火车站台上有一面墙上面有一万个小灯泡每个灯泡对应一个旅客编号灯亮就代表这个编号的旅客已经进站了。你不需要把所有旅客的名字列成一张大表只需要看一眼对应编号的灯泡亮没亮。位图就是这面灯泡墙每一位就是一个开关。位图的内存计算公式是所需字节数 (最大可能数值 1) / 8。对应到用long数组实现就是(最大数值 1 63) / 64个long。注意这里一般是按“数字本身的值”作为位索引来用如果数字范围很大比如几十亿那还是得靠哈希或分桶先压缩范围。位图擅长的是数字范围相对可控的判重场景。5.2 手写一个可用的BitMap面试中经常要求现场写一个简版BitMap我用long数组实现比int数组更常见因为每个long是64位能少算几次下标。public class BitMap { private final long[] words; private final int nbits; public BitMap(int nbits) { this.nbits nbits; this.words new long[(nbits 63) / 64]; } public void set(int pos) { checkRange(pos); words[pos 6] | (1L (pos 63)); } public boolean get(int pos) { checkRange(pos); return (words[pos 6] (1L (pos 63))) ! 0; } public void clear(int pos) { checkRange(pos); words[pos 6] ~(1L (pos 63)); } private void checkRange(int pos) { if (pos 0 || pos nbits) { throw new IndexOutOfBoundsException(pos: pos); } } }代码里有三个地方值得展开讲。第一pos 6就是pos / 64因为一个long占64位整除是除以64pos 63就是pos % 64因为64的二进制是1000000低位6位正好是余数。这两个位运算写出来性能更高但更重要的是展示了你对位运算的应用理解。第二1L (pos 63)中必须写1L而不是1因为int只有32位左移超过31位会出问题。这个坑我亲眼见人踩过super类面试一紧张就写错。第三clear操作里用~取反再与是为了把目标位清零其他位保持不变。如果面试官问“为什么选long而不是int”回答是用long能减少数组长度和定位次数64位一次能覆盖64个状态从内存上看两种实现差不多但long方案索引计算更简洁。要是位图还要支持非常大的范围可以考虑用int数组甚至分段位图但面试基本不会深挖到那一步。5.3 位图面试的扩展场景布隆过滤器位图讲完之后面试官大概率会追问一句“如果我要判重的不是整数而是URL字符串呢”这时候直接回答“先哈希成整数再用位图”因为URL本身不可能直接用下标索引。更进一步单个哈希函数冲突率较高用多个哈希函数映射到多个位置这就是布隆过滤器Bloom Filter。布隆过滤器的核心是用m个bit和k个哈希函数插入时对所有哈希函数结果置1查询时所有位置都是1才认为可能存在有一个位置是0就一定不存在。它的好处是极省内存代价是有一定的误判率。面试时能主动把这个扩展讲出来会明显加分因为这说明你不是只会背位图而是理解位图的能力边界。注意布隆过滤器返回“可能存在”而非“一定存在”这个语义要主动说清楚。还有一个常见扩展是“给一个很大的整数数组找出出现次数不为0且未被标记过的数字”这类“位图排序”题。位图天然可以用来做去重和存在性判断但要注意它不擅长处理“出现次数很多”的统计型需求那种场景要上Counter或两级位图。6. 第五道高频题2的幂与“奇技淫巧”矩阵6.1 判断2的幂一行代码背后的二进制原理LeetCode 231题给定一个整数n判断它是否是2的幂。最经典的答案就一行public boolean isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }原理很简单2的幂的二进制只有一个1例如1是12是104是1008是1000。让n的二进制只有一位是1那么n - 1会让这一位变成0后面全变1两者按位与结果为0。反过来如果n本来就有多个1n (n - 1)不可能为0。别忘了最前面的n 0因为0和负数都不可能是2的幂。面试官特别爱抠这个边界条件你主动提“还必须大于0”会显得严谨。我经常把这题和“判断4的幂”放一起讲。4的幂同样只有一个1但它那个1必须落在奇数位上。如果只用(n (n - 1)) 0判断1610000也能通过但16不是4的幂。正确做法是在此基础上再加上n 0x55555555 ! 0的掩码判断。0x55555555的二进制是0101...0101刚好把偶数位选出来。这个附加小知识不是必须的但能在一大波候选人里脱颖而出。6.2 高频变形题取位、清位、反转、大小写切换除了判断2的幂还有几条位运算“肌肉记忆”是面试高频里反复出现的建议你连同原理一起记牢。取一个整数最低位的1n (-n)。前面260题用过了。去掉最低位的1n (n - 1)。比特计数用过了。判断第k位是否为1(n k) 1。将第k位清0n ~(1 k)。将第k位置1n | (1 k)。字母大小写切换c ^ 32。因为大写A是65二进制01000001小写a是9701100001差32刚好是二进制100000异或32就能切换。二进制反转、判断二进制是否回文也是常见附加题。面试官为什么这么爱考这些边角料一方面代码极短适合现场快速验证候选人的“位感”另一方面这些操作在JDK源码和中间件里确实存在比如HashMap的hash值扰动、ThreadLocal的数组长度找最近2的幂、ConcurrentHashMap里扩容相关的位运算。能说出“这里的位运算在HashMap里怎么用的”面试官对你的评价会高一个层级。6.3 为什么面试官总在这块加一道附加题说到底位运算的五道高频题本身并不难难的是你能不能从“会写”跨到“理解原理并知道使用场景”。我曾经问过一个候选人“你觉得位运算在真实Java工程里有什么用处”他想了半天只憋出一句“算法题会考”。这个答案不算错但太单薄了。实际上权限系统里用int的每一位代表一个权限通过权限位相与、相或来增删查权限是后端常见的位图应用配置开关合并成int或long一次比较多个开关状态缓存和消息队列中为了节省内存也大量使用位标记。另外JDK源码里Integer.bitCount、HashMap的高位异或都是位运算的活例子。你如果能从一道算法题聊到JDK源码里的位运算应用再聊到工程中的权限位设计面试官这一块基本会给你高分。我建议你在面试前翻一翻HashMap源码里这段static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }。它就是典型的用异或和无符号右移把哈希值的高16位“扰动”到低16位减少哈希碰撞。看懂了这一段你会对位运算在工业级的地位有新的认识。7. 面试实战把5道题串起来复盘的几条经验7.1 题目组合与复杂度速查表把全文讲过的5道高频题整理成一个速查表方便你在面试前10分钟快速过一遍。高频题核心考点解题关键操作时间复杂度空间复杂度只出现一次的数字136异或性质ans ^ numO(n)O(1)两个只出现一次的数字260异或分组xor (-xor)取最低位1O(n)O(1)比特计数191/338n (n - 1) / DPwhile循环消除最低位1O(k)或O(n)O(1)或O(n)位图判重位运算实现索引pos 6与1L (pos 63)O(1)O(最大数/8)判断2的幂231二进制只含一个1n 0 (n (n - 1)) 0O(1)O(1)这五题的意义不只是“会写”它们覆盖了位运算面试的三个层次异或是“理解运算性质”比特计数是“掌握位操作技巧”位图是“把位运算当数据结构用”。面试官问完这三层基本就能判断你的位运算水平了。7.2 避坑清单与答题节奏根据我和大量候选人打交道的经验位运算题最容易在下面几个地方翻车你自查一下。第一右移用错。需要逐位检查时一定要用而不是否则负数会高位补1导致死循环。第二1L左移写成1。int左移超过31位就溢出位图里必须用long。第三优先级问题。if ((num mask) 0)的括号不能省Java的优先级高于不写括号先比较后按位与直接编译不过。第四边界条件忘写。判断2的幂忘了n 0负数直接返回true这题就白送了。第五写完代码不解释复杂度。面试官问完解法后你最好主动把时间复杂度、空间复杂度都说清楚这是一道送分题别浪费。答题节奏上我的建议是先把思路说完整再动笔写代码。位运算题代码普遍短但对逻辑正确性要求高先说清楚“为什么用异或”、“为什么分组”、“为什么mask取这个”能让面试官跟着你的思路走也给自己留出组织代码的时间。写完代码后口头模拟一个最简单的输入比如[2,4,3,2]或n12能当场验证逻辑。最后再分享一个我自己的小习惯面试前我会专门刷一遍“位运算专项题单”把136、137、231、260、338、461做One Shot每一题都要求自己边写边说出复杂度。坚持两轮之后面试时再遇到位运算题基本不会慌因为核心模式就那几个异或、分组、清位、计数。位运算这些题代码短、变化多、原理硬核确实是Java面试里少有的“性价比极高”的考点。希望这篇文章能帮你在这5道高频题上建立自己的理解体系而不是死记答案。刷题的时候多问自己一句“这个位运算为什么能成立”答得出来面试这一关就稳了。
Java面试必考位运算：异或、位图与比特计数全解析
1. 位运算为什么能成为Java面试的“试金石”1.1 面试官考位运算到底在考什么不知道你有没有这种经历刷了三个月LeetCode数组、链表、哈希表、动态规划都过了一遍结果一进面试间面试官上来就抛一句“给你一个数组只有一个数出现一次其他数都出现两次怎么找出它”典型的位运算题。很多人第一反应是HashMap答案没错但面试官眉头一皱继续问“能不能不用额外空间”就是这一句“能不能不用额外空间”把位运算推上了Java面试高频考点的位置。它考察的绝不仅仅是“你会不会背公式”而是你对计算机底层数据存储的理解整数到底怎么存、补码的运算规则是什么、为什么异或满足交换律和结合律、位运算和算术运算在执行层面有哪些差异。这些知识点平时写业务代码可能三年都用不上一回但它恰恰是区分“背题型选手”和“真正理解型选手”的分水岭。我这几年面过不少人也帮朋友做过模拟面试一个很明显的规律是位运算题目如果候选人能在五分钟之内把思路讲清楚并且代码一次跑通那么他大概率对Java基础掌握得很扎实。反过来如果支支吾吾只记得“用异或”但说不出为什么那后面面Java内存模型、HashMap原理这些题多半也会露馅。所以面试官不是真要在生产环境里让你用位运算写业务而是借这几道小题目探测你的计算机基本功。更实际的一点是位运算题往往可以连续出变种从“只出现一次的数字”到“两个只出现一次的数字”从“统计1的个数”到“判断2的幂”从“位图判重”到“布隆过滤器”。一道基础题能牵出一串知识点面试官手里等于拿到了一个“连环炮”既能测深度又能测广度。这也是为什么标题里的“位图异或比特计数”这三个点几乎是Java位运算面试里绕不开的组合拳。1.2 必备基础Java位运算的常见写法先花三分钟把基础过一遍后面讲题目的时候不卡壳。Java里的位运算一共六类按位与、按位或|、按位异或^、按位取反~、左移、右移还有一个容易被忽略的无符号右移。这里有几个我经常提醒学生的细节。第一按位异或^的规则是“相同为0不同为1”它天然自带“消消乐”属性a ^ a 00 ^ a a而且满足交换律和结合律。这意味着你不管怎么调换运算顺序结果都一样这是后面所有异或题解法的理论根基。第二按位与可以用来取位、清位比如n (n - 1)这个经典操作的作用是“把整数最低位的1变成0”。第三Java的整数默认是int占32位高位是符号位所以负数用补码表示。补码这个东西面试官特别爱追问比如-1的二进制是全1取最低位1的写法n (-n)能直接拿到一个数最右边那个1的位置原理就藏在“取反加一”里。再补充一个实战中的优先级问题。Java里位运算符的优先级比相等运算符低比赋值运算符高很多初学者写if ((a b) 0)会漏括号编译直接报错。我的习惯是全加上括号宁可多写两个括号也不要让面试官在代码上看你犹豫。还有一个特别容易混淆的点和的区别。是带符号右移左边补的是符号位负数右移后还是负数是无符号右移左边一律补0。统计二进制1的个数时如果循环里写成n n 1遇到负数就死循环了必须用。这个坑我在面试现场见过不止一次后面“避坑清单”里我会再强调。2. 第一道高频题只出现一次的数字异或的经典战场2.1 题目与常规思路先看最经典的LeetCode 136题一个整型数组里除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现一次的元素。要求时间复杂度O(n)空间复杂度O(1)。不假思索的做法是哈希表遍历一遍把元素塞进HashMap第二次出现就删掉最后剩下的就是答案。代码好写思路也好懂但空间复杂度是O(n)。面试官让你优化九成是往“位运算”方向引导。另有解法是先排序再遍历时间复杂度O(n log n)通常面试官看一眼就不会让你往下写了。这道题我建议你从数学的角度再想一遍。异或满足交换律和结合律对于任意整数aa ^ a 0。那么多整数异或在一起出现偶数次的数全部“抵消”成0最后剩下的就是那个落单的数。这就像一群人两两分组跳舞最后一支舞跳完剩下没人配对的那个就是要找的人。2.2 异或解法推导与实现直接上代码public int singleNumber(int[] nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; }就这么简单五六行搞定。初始值为什么是0因为0 ^ x x不会影响异或结果的累积。遍历顺序无所谓因为异或满足交换律和结合律你把数组倒过来遍历答案也一样。我遇到不少人在看懂解法后有一个疑问如果数组是[1, 2, 3, 1, 2]那执行过程是不是要手动模拟一遍才知道最终结果是3其实不需要你只需要抓住一个核心结论异或运算在“统计奇偶次数”这件事上是精确的。三次异或同一个数等于它本身出现奇数次会留下痕迹出现偶数次会清零。所以哪怕是[1, 1, 1, 2, 2, 2, 3]最后结果依然是3因为这题三个1异或完等于1相当于奇数个1最终还是“有”三个2异或完等于2最后1 ^ 2 ^ 3等于啥你自己算反正原理是一样的。面试时我建议这样铺开讲先解释异或三条性质再说“因为其他数都出现两次异或后会归零最终结果就是唯一出现一次的数”最后补一句“时间复杂度O(n)空间复杂度O(1)”。注意要把空间复杂度O(1)主动说出来那才是这题的考点。2.3 追问点从1个到多个变种题怎么接面试官很少问完一题就放你走的他一定会顺藤摸瓜。第一问如果改成“只有一个数出现奇数次其他数出现偶数次”还适用吗适用因为异或只关心奇偶性跟“是不是出现一次”没本质区别。第二问如果改成“其他数都出现三次只有一个出现一次”异或还行不行这时候同样套路就行不通了因为三个一样的数异或完还是它本身抵消不掉。标准解法是统计每一位上1出现的次数对3取模。这其实就是“位计数”思想的变体和后面聊的比特计数是同一个家族。第三问如果改成“有两个数只出现一次其他数都出现两次”这就是LeetCode 260题我会在下一章专门讲。面试官通过这种连续追问能很快看出你是背了一道题还是真正理解了位运算。所以我的建议是刷题时把同一思路下的变种题一起刷比如136、137、260三题放在同一天做效果比单刷好得多。3. 第二道高频题两个单身狗异或分组进阶版3.1 题目描述与破题思路LeetCode 260题一个整型数组里恰好有两个元素只出现一次其余所有元素都出现两次。找出这两个只出现一次的元素。要求同样O(n)时间O(1)空间。很多人的第一反应是“能不能用两次singleNumber的解法”不行因为第一次异或完得到的不是某个数的值而是a和b两个数的异或结果xor a ^ b。你没法直接从xor同时还原出a和b。但这道题的精妙之处在于xor作为a ^ b它里面每一个为1的二进制位都意味着a和b在这一位上是不同的。我们把数组里的数按照这一位划分成两组这一位是0的一组这一位是1的一组。a和b必然被分到不同组而其他出现两次的数要么两个都在同一组且成对出现要么被分组后依然能两两抵消。所以对每一组分别做全员异或就能分别得到a和b。这个思路用生活类比解释就是一群人里有两个落单的你不知道具体是谁但你知道他俩在某个特征上不一样比如戴不戴帽子。让所有人按这个特征分成两队每队里落单的人就只剩一个了再用上一题的“全员异或”分别找出来。3.2 找出分组依据与完整代码问题来了怎么从xor里找一个“这一位不同”的特征位最常用的就是取最低位的1mask xor (-xor)。注意-xor就是取反加一这样写能直接保留最低位的1其他位全部清零。我见过有人写成mask 1那就错了因为a ^ b的最低位不一定就是1必须动态计算。完整代码如下public int[] singleNumber(int[] nums) { int xor 0; for (int num : nums) { xor ^ num; } // 取最低位的1作为分组依据 int mask xor (-xor); int a 0, b 0; for (int num : nums) { if ((num mask) 0) { a ^ num; } else { b ^ num; } } return new int[]{a, b}; }这里有几个细节要扣。第一mask可能为负数吗mask是int类型如果xor本身是Integer.MIN_VALUE取负会溢出回到自身但mask仍然等于xor分组依然正确所以不用担心。第二分组条件(n mask) 0表示这一位是0的分到a组注意这里必须加括号因为Java里优先级高于不写括号会先比较num和mask再对结果做与运算直接编译错。另外我建议你在面试时手动模拟一个小例子比如[1, 2, 1, 3, 2, 5]全部异或得到6二进制110最低位1是第1位从右往左数第0位为最低位mask 2。然后根据第1位分组1和3和5的第1位分别是0、1、02是1分组后a组是1、1、5异或得5b组是2、3、2异或得3答案就是5和3。这样讲面试官会觉得你是真懂而不是背代码。3.3 变式汉明距离与脑洞题260题常见的变形是LeetCode 461题汉明距离两个整数对应二进制位不同的个数。最直接的解法就是先将两个数异或然后统计结果中1的个数。统计1的个数用的就是下一章要讲的比特计数。我面试时还见过一个有意思的追问给你两个数不用加减乘除实现加法。那也是位运算的用武之地通过a ^ b算无进位和通过(a b) 1算进位循环直到进位为0。这道题作为附加题出现频率不低建议你顺手也刷了。刷位运算题有个经验别只刷“标准题”要配合“变形题”一起看。比如260题刷完可以立刻做一下“找出数组中缺失的那个数”268题它本质是异或的另一种应用把数组下标和数据本身全部异或剩下的就是缺失值。这种串法刷下来你脑子里会形成一张位运算“知识网”面试时不管从哪个角度切入都能接住。4. 第三道高频题比特计数——统计二进制中1的个数4.1 常见解法对比比特计数的经典题是LeetCode 191题统计无符号整数的比特位中1的个数以及LeetCode 338题给一个n返回0到n每个数的二进制中1的个数。这组题属于“一题多解”的典型面试素材解法至少四类面试官让你全部列出也不奇怪。解法核心思路时间复杂度额外空间循环右移逐位检查n 1然后n 1O(k)k是二进制位数O(1)Brian Kernighan反复执行n (n - 1)每执行一次消掉一个1O(m)m是1的个数O(1)查表法预先生成0~255的1的个数表按字节查表累加O(1)实际是常数轮查表O(256)内置APIInteger.bitCount(n)底层用分治法无动态规划count[i] count[i 1] (i 1)O(n)O(n)面试时怎么选我建议先答Brian Kernighan因为它代码短、原理典型还能顺便引出n (n - 1)这个高频操作。第二步再提Integer.bitCount但要强调它的底层是“每两位一组统计再逐级合并”的分治思想。第三步可以把查表法或循环右移作为补充展示一下知识面。4.2 Brian Kernighan算法是怎么来的很多人背下了n (n - 1)这个操作但不知道它为什么能去掉最低位的1。我用人话说一下。n - 1做的事情是把n从最低位开始遇到的第一个1变成0这个1后面所有0都变成1。比如n 12二进制是1100n - 1 11二进制是1011。把1100和1011做按位与得到1000正好把原数最低位的那个1消掉了而更高位保持不变。所以“反复执行n (n - 1)”的意思是每次消掉一个最低位的1循环次数就等于二进制中1的个数。代码极简public int hammingWeight(int n) { int count 0; while (n ! 0) { n (n - 1); count; } return count; }注意这里虽然函数参数经常写int n但LeetCode 191题目原意是按无符号处理。Java的int有符号如果是负数用n ! 0做循环条件依然能正确退出因为负数的二进制表示中1的个数也是有限多个消到0为止。不过如果你在循环体里写n n 1负数会高位补1永远不是0直接死循环。正确做法是用n 1做逐位检查。4.3 动态规划与查表法的实际取舍LeetCode 338题要求一次性返回0到n每个数的1的个数。如果对每个数都单独用Brian Kernighan总复杂度是O(n * m)还能接受但有更漂亮的递推count[i] count[i 1] (i 1)。原理很简单i右移一位二进制整体挪动最高位移掉一个i的最低位决定最后加不加1。public int[] countBits(int n) { int[] dp new int[n 1]; for (int i 1; i n; i) { dp[i] dp[i 1] (i 1); } return dp; }这个递推式在面试中写出来一般面试官会眼睛一亮因为它既展示了动态规划思想又用到位运算缩短代码。要注意的是dp[0]默认为0循环从i 1开始否则会越界。查表法的思路则是先把0到255每个数的1的个数存在一个长度为256的数组里然后对任意int拆成4个字节分别查表相加。查表法在极端性能要求下比逐位循环快因为循环次数固定为4次。柯南道尔说过一句话很适合这里排除所有不可能的剩下的就算再不可思议那也是真相。面试时你不需要真的把所有解法都写一遍但至少要对每种解法的取舍心中有数别被追问时卡住。5. 第四道高频题位图BitMap实现海量数据判重5.1 位图是什么内存怎么算位图BitMap是和位运算紧密相关的数据结构面试中出现频率不亚于纯异或题。它的核心思想是用一位二进制位表示一个“状态”通常0表示不存在1表示存在。你有一个巨大的整数集合想快速判断某个数是否出现过用HashSet当然可以但假设你有1亿个不重复的int要判重HashSet光是存这些元素就要约800MB内存4字节*1亿再加对象头等开销而如果用位图把数字范围映射到位数组的索引上1亿个bit只需要约12.5MB。用生活类比讲位图特别好懂想象你在火车站台上有一面墙上面有一万个小灯泡每个灯泡对应一个旅客编号灯亮就代表这个编号的旅客已经进站了。你不需要把所有旅客的名字列成一张大表只需要看一眼对应编号的灯泡亮没亮。位图就是这面灯泡墙每一位就是一个开关。位图的内存计算公式是所需字节数 (最大可能数值 1) / 8。对应到用long数组实现就是(最大数值 1 63) / 64个long。注意这里一般是按“数字本身的值”作为位索引来用如果数字范围很大比如几十亿那还是得靠哈希或分桶先压缩范围。位图擅长的是数字范围相对可控的判重场景。5.2 手写一个可用的BitMap面试中经常要求现场写一个简版BitMap我用long数组实现比int数组更常见因为每个long是64位能少算几次下标。public class BitMap { private final long[] words; private final int nbits; public BitMap(int nbits) { this.nbits nbits; this.words new long[(nbits 63) / 64]; } public void set(int pos) { checkRange(pos); words[pos 6] | (1L (pos 63)); } public boolean get(int pos) { checkRange(pos); return (words[pos 6] (1L (pos 63))) ! 0; } public void clear(int pos) { checkRange(pos); words[pos 6] ~(1L (pos 63)); } private void checkRange(int pos) { if (pos 0 || pos nbits) { throw new IndexOutOfBoundsException(pos: pos); } } }代码里有三个地方值得展开讲。第一pos 6就是pos / 64因为一个long占64位整除是除以64pos 63就是pos % 64因为64的二进制是1000000低位6位正好是余数。这两个位运算写出来性能更高但更重要的是展示了你对位运算的应用理解。第二1L (pos 63)中必须写1L而不是1因为int只有32位左移超过31位会出问题。这个坑我亲眼见人踩过super类面试一紧张就写错。第三clear操作里用~取反再与是为了把目标位清零其他位保持不变。如果面试官问“为什么选long而不是int”回答是用long能减少数组长度和定位次数64位一次能覆盖64个状态从内存上看两种实现差不多但long方案索引计算更简洁。要是位图还要支持非常大的范围可以考虑用int数组甚至分段位图但面试基本不会深挖到那一步。5.3 位图面试的扩展场景布隆过滤器位图讲完之后面试官大概率会追问一句“如果我要判重的不是整数而是URL字符串呢”这时候直接回答“先哈希成整数再用位图”因为URL本身不可能直接用下标索引。更进一步单个哈希函数冲突率较高用多个哈希函数映射到多个位置这就是布隆过滤器Bloom Filter。布隆过滤器的核心是用m个bit和k个哈希函数插入时对所有哈希函数结果置1查询时所有位置都是1才认为可能存在有一个位置是0就一定不存在。它的好处是极省内存代价是有一定的误判率。面试时能主动把这个扩展讲出来会明显加分因为这说明你不是只会背位图而是理解位图的能力边界。注意布隆过滤器返回“可能存在”而非“一定存在”这个语义要主动说清楚。还有一个常见扩展是“给一个很大的整数数组找出出现次数不为0且未被标记过的数字”这类“位图排序”题。位图天然可以用来做去重和存在性判断但要注意它不擅长处理“出现次数很多”的统计型需求那种场景要上Counter或两级位图。6. 第五道高频题2的幂与“奇技淫巧”矩阵6.1 判断2的幂一行代码背后的二进制原理LeetCode 231题给定一个整数n判断它是否是2的幂。最经典的答案就一行public boolean isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }原理很简单2的幂的二进制只有一个1例如1是12是104是1008是1000。让n的二进制只有一位是1那么n - 1会让这一位变成0后面全变1两者按位与结果为0。反过来如果n本来就有多个1n (n - 1)不可能为0。别忘了最前面的n 0因为0和负数都不可能是2的幂。面试官特别爱抠这个边界条件你主动提“还必须大于0”会显得严谨。我经常把这题和“判断4的幂”放一起讲。4的幂同样只有一个1但它那个1必须落在奇数位上。如果只用(n (n - 1)) 0判断1610000也能通过但16不是4的幂。正确做法是在此基础上再加上n 0x55555555 ! 0的掩码判断。0x55555555的二进制是0101...0101刚好把偶数位选出来。这个附加小知识不是必须的但能在一大波候选人里脱颖而出。6.2 高频变形题取位、清位、反转、大小写切换除了判断2的幂还有几条位运算“肌肉记忆”是面试高频里反复出现的建议你连同原理一起记牢。取一个整数最低位的1n (-n)。前面260题用过了。去掉最低位的1n (n - 1)。比特计数用过了。判断第k位是否为1(n k) 1。将第k位清0n ~(1 k)。将第k位置1n | (1 k)。字母大小写切换c ^ 32。因为大写A是65二进制01000001小写a是9701100001差32刚好是二进制100000异或32就能切换。二进制反转、判断二进制是否回文也是常见附加题。面试官为什么这么爱考这些边角料一方面代码极短适合现场快速验证候选人的“位感”另一方面这些操作在JDK源码和中间件里确实存在比如HashMap的hash值扰动、ThreadLocal的数组长度找最近2的幂、ConcurrentHashMap里扩容相关的位运算。能说出“这里的位运算在HashMap里怎么用的”面试官对你的评价会高一个层级。6.3 为什么面试官总在这块加一道附加题说到底位运算的五道高频题本身并不难难的是你能不能从“会写”跨到“理解原理并知道使用场景”。我曾经问过一个候选人“你觉得位运算在真实Java工程里有什么用处”他想了半天只憋出一句“算法题会考”。这个答案不算错但太单薄了。实际上权限系统里用int的每一位代表一个权限通过权限位相与、相或来增删查权限是后端常见的位图应用配置开关合并成int或long一次比较多个开关状态缓存和消息队列中为了节省内存也大量使用位标记。另外JDK源码里Integer.bitCount、HashMap的高位异或都是位运算的活例子。你如果能从一道算法题聊到JDK源码里的位运算应用再聊到工程中的权限位设计面试官这一块基本会给你高分。我建议你在面试前翻一翻HashMap源码里这段static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }。它就是典型的用异或和无符号右移把哈希值的高16位“扰动”到低16位减少哈希碰撞。看懂了这一段你会对位运算在工业级的地位有新的认识。7. 面试实战把5道题串起来复盘的几条经验7.1 题目组合与复杂度速查表把全文讲过的5道高频题整理成一个速查表方便你在面试前10分钟快速过一遍。高频题核心考点解题关键操作时间复杂度空间复杂度只出现一次的数字136异或性质ans ^ numO(n)O(1)两个只出现一次的数字260异或分组xor (-xor)取最低位1O(n)O(1)比特计数191/338n (n - 1) / DPwhile循环消除最低位1O(k)或O(n)O(1)或O(n)位图判重位运算实现索引pos 6与1L (pos 63)O(1)O(最大数/8)判断2的幂231二进制只含一个1n 0 (n (n - 1)) 0O(1)O(1)这五题的意义不只是“会写”它们覆盖了位运算面试的三个层次异或是“理解运算性质”比特计数是“掌握位操作技巧”位图是“把位运算当数据结构用”。面试官问完这三层基本就能判断你的位运算水平了。7.2 避坑清单与答题节奏根据我和大量候选人打交道的经验位运算题最容易在下面几个地方翻车你自查一下。第一右移用错。需要逐位检查时一定要用而不是否则负数会高位补1导致死循环。第二1L左移写成1。int左移超过31位就溢出位图里必须用long。第三优先级问题。if ((num mask) 0)的括号不能省Java的优先级高于不写括号先比较后按位与直接编译不过。第四边界条件忘写。判断2的幂忘了n 0负数直接返回true这题就白送了。第五写完代码不解释复杂度。面试官问完解法后你最好主动把时间复杂度、空间复杂度都说清楚这是一道送分题别浪费。答题节奏上我的建议是先把思路说完整再动笔写代码。位运算题代码普遍短但对逻辑正确性要求高先说清楚“为什么用异或”、“为什么分组”、“为什么mask取这个”能让面试官跟着你的思路走也给自己留出组织代码的时间。写完代码后口头模拟一个最简单的输入比如[2,4,3,2]或n12能当场验证逻辑。最后再分享一个我自己的小习惯面试前我会专门刷一遍“位运算专项题单”把136、137、231、260、338、461做One Shot每一题都要求自己边写边说出复杂度。坚持两轮之后面试时再遇到位运算题基本不会慌因为核心模式就那几个异或、分组、清位、计数。位运算这些题代码短、变化多、原理硬核确实是Java面试里少有的“性价比极高”的考点。希望这篇文章能帮你在这5道高频题上建立自己的理解体系而不是死记答案。刷题的时候多问自己一句“这个位运算为什么能成立”答得出来面试这一关就稳了。
