企业官网建设流程全解析

1. 位运算为什么能成为Java面试的“试金石”

1.1 面试官考位运算，到底在考什么

不知道你有没有这种经历：刷了三个月LeetCode，数组、链表、哈希表、动态规划都过了一遍，结果一进面试间，面试官上来就抛一句“给你一个数组，只有一个数出现一次，其他数都出现两次，怎么找出它？”典型的位运算题。很多人第一反应是HashMap，答案没错，但面试官眉头一皱，继续问：“能不能不用额外空间？”

就是这一句“能不能不用额外空间”，把位运算推上了Java面试高频考点的位置。它考察的绝不仅仅是“你会不会背公式”，而是你对计算机底层数据存储的理解：整数到底怎么存、补码的运算规则是什么、为什么异或满足交换律和结合律、位运算和算术运算在执行层面有哪些差异。这些知识点，平时写业务代码可能三年都用不上一回，但它恰恰是区分“背题型选手”和“真正理解型选手”的分水岭。

我这几年面过不少人，也帮朋友做过模拟面试，一个很明显的规律是：位运算题目如果候选人能在五分钟之内把思路讲清楚，并且代码一次跑通，那么他大概率对Java基础掌握得很扎实。反过来，如果支支吾吾只记得“用异或”，但说不出为什么，那后面面Java内存模型、HashMap原理这些题，多半也会露馅。所以面试官不是真要在生产环境里让你用位运算写业务，而是借这几道小题目探测你的计算机基本功。

更实际的一点是，位运算题往往可以连续出变种：从“只出现一次的数字”到“两个只出现一次的数字”，从“统计1的个数”到“判断2的幂”，从“位图判重”到“布隆过滤器”。一道基础题能牵出一串知识点，面试官手里等于拿到了一个“连环炮”，既能测深度又能测广度。这也是为什么标题里的“位图+异或+比特计数”这三个点，几乎是Java位运算面试里绕不开的组合拳。

1.2 必备基础：Java位运算的常见写法

先花三分钟把基础过一遍，后面讲题目的时候不卡壳。Java里的位运算一共六类：按位与（&）、按位或（|）、按位异或（^）、按位取反（~）、左移（<<）、右移（>>），还有一个容易被忽略的无符号右移（>>>）。

这里有几个我经常提醒学生的细节。第一，按位异或^的规则是“相同为0，不同为1”，它天然自带“消消乐”属性：a ^ a = 0，0 ^ 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)，通常面试官看一眼就不会让你往下写了。

这道题我建议你从数学的角度再想一遍。异或满足交换律和结合律，对于任意整数a，a ^ 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里找一个“这一位不同”的特征位？最常用的就是取最低位的1：mask = 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、0，2是1，分组后a组是1、1、5，异或得5；b组是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的个数）。这组题属于“一题多解”的典型面试素材，解法至少四类，面试官让你全部列出也不奇怪。

面试时怎么选？我建议先答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，二进制是1100，n - 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位，整除是除以64；pos & 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是1，2是10，4是100，8是1000。让n的二进制只有一位是1，那么n - 1会让这一位变成0，后面全变1，两者按位与结果为0。反过来，如果n本来就有多个1，n & (n - 1)不可能为0。别忘了最前面的n > 0，因为0和负数都不可能是2的幂。面试官特别爱抠这个边界条件，你主动提“还必须大于0”，会显得严谨。

我经常把这题和“判断4的幂”放一起讲。4的幂同样只有一个1，但它那个1必须落在奇数位上。如果只用(n & (n - 1)) == 0判断，16（10000）也能通过，但16不是4的幂。正确做法是在此基础上再加上n & 0x55555555 != 0的掩码判断。0x55555555的二进制是0101...0101，刚好把偶数位选出来。这个附加小知识不是必须的，但能在一大波候选人里脱颖而出。

6.2 高频变形题：取位、清位、反转、大小写切换

除了判断2的幂，还有几条位运算“肌肉记忆”是面试高频里反复出现的，建议你连同原理一起记牢。

• 取一个整数最低位的1：n & (-n)。前面260题用过了。
• 去掉最低位的1：n & (n - 1)。比特计数用过了。
• 判断第k位是否为1：(n >> k) & 1。
• 将第k位清0：n & ~(1 << k)。
• 将第k位置1：n | (1 << k)。
• 字母大小写切换：c ^= 32。因为大写A是65（二进制01000001），小写a是97（01100001），差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分钟快速过一遍。

这五题的意义不只是“会写”，它们覆盖了位运算面试的三个层次：异或是“理解运算性质”，比特计数是“掌握位操作技巧”，位图是“把位运算当数据结构用”。面试官问完这三层，基本就能判断你的位运算水平了。

7.2 避坑清单与答题节奏

根据我和大量候选人打交道的经验，位运算题最容易在下面几个地方翻车，你自查一下。

第一，右移用错。需要逐位检查时一定要用>>>而不是>>，否则负数会高位补1导致死循环。第二，1L左移写成1。int左移超过31位就溢出，位图里必须用long。第三，优先级问题。if ((num & mask) == 0)的括号不能省，Java的==优先级高于&，不写括号先比较后按位与，直接编译不过。第四，边界条件忘写。判断2的幂忘了n > 0，负数直接返回true，这题就白送了。第五，写完代码不解释复杂度。面试官问完解法后，你最好主动把时间复杂度、空间复杂度都说清楚，这是一道送分题，别浪费。

答题节奏上，我的建议是先把思路说完整，再动笔写代码。位运算题代码普遍短，但对逻辑正确性要求高，先说清楚“为什么用异或”、“为什么分组”、“为什么mask取这个”，能让面试官跟着你的思路走，也给自己留出组织代码的时间。写完代码后，口头模拟一个最简单的输入，比如[2,4,3,2]或n=12，能当场验证逻辑。

最后再分享一个我自己的小习惯：面试前我会专门刷一遍“位运算专项题单”，把136、137、231、260、338、461做One Shot，每一题都要求自己边写边说出复杂度。坚持两轮之后，面试时再遇到位运算题基本不会慌，因为核心模式就那几个：异或、分组、清位、计数。

位运算这些题，代码短、变化多、原理硬核，确实是Java面试里少有的“性价比极高”的考点。希望这篇文章能帮你在这5道高频题上建立自己的理解体系，而不是死记答案。刷题的时候多问自己一句“这个位运算为什么能成立”，答得出来，面试这一关就稳了。