有一次面试官问了我一个“看起来很简单”的题目统计一个整数的二进制表示里有多少个 1。我当时的做法是先把整数转成二进制字符串再写个循环去数1的个数代码写了七八行还专门处理了负数的情况。面试官看完没说话随手在纸上写了六个字母n (n - 1)。那一瞬间我就知道位运算这一课我迟早得补上。今天这篇内容就是那之后我给自己做的一次系统梳理主题是 Java 位运算算法题目练习。我会从最基础的运算符开始讲到拆位、判奇偶、二进制 1 计数、异或找唯一数、子集枚举等经典题目每一题都尽量给出“暴力解法怎么想、位运算思路怎么来、代码长什么样、复杂度差多少”。如果你正在准备 Java 面试或者刷题遇到瓶颈尤其是看到位运算相关题目就头疼这篇文章应该能帮到你。这篇不是教科书式的位运算百科更像我在实际刷题和面试复盘之后的经验总结。我的原则是每个结论都给你讲清楚“为什么”每个代码都能直接跑、可以直接抄。1. 位运算在Java算法题里的地位为什么值得专门练1.1 面试和竞赛里位运算到底考什么很多人一听到位运算就觉得是偏门技巧实际完全不是。你去翻一翻算法面试题清单至少这几种题型都有非常浓的位运算味道一维数组里只有一个数出现一次其他数都出现两次找出这个数判断一个正整数是不是 2 的幂统计二进制中 1 的个数不用加减乘除做加法给定一个数组输出所有子集这些题用常规思路都能解但位运算解法往往代码最短、性能最高而且解法本身就是对二进制理解程度的考验所以面试官特别喜欢拿它们来考察候选人的基础功底。我面试别人的时候也一样一道异或找唯一数的题基本就能聊出候选人对“状态存储”这件事理解得深不深。说白了位运算题目练的是“二进制视角”。平时我们写代码默认都在用十进制思维但计算机内部全是二进制。位运算就是直接跟计算机“说二进制”这个视角一旦建立再看很多算法题会豁然开朗。1.2 Java 位运算和 C 语言的关键差异从 Java 本身说起有几个点跟其他语言不太一样面试也爱考无符号右移是 Java 和 C# 特有的C/C 里的对无符号数和有符号数行为不同但不能直接实现“无脑补 0”的右移。Java 的整型都是带符号位的int是 32 位long是 64 位最高位是符号位。Java 对移位运算有个特殊规定如果移动位数超过类型总位数实际会按移位数 % 类型位数来算。比如1 32因为 32 % 32 0所以结果等于1 0也就是 1。这个规则很容易被面试题拿来当陷阱。不理解这些差异直接把网上 C 语言的位运算代码搬到 Java 里很容易踩出莫名其妙的问题。1.3 工程底层到处都是位运算位运算不只是专门刷题才用的东西。HashMap 计算桶下标用(n - 1) hash因为当 n 是 2 的幂时取模和按位与等价但位运算更快AQS 里同步状态的高低位拆分、线程池几个核心状态字段的压缩也是位掩码的经典应用乃至 MD5、SHA 系列算法内部更是大量使用移位、异或、与或非。我个人刷题过程中的一个体会是只背题不理解底层用途遇到变种题还是会懵理解了这些工程场景位运算就成了一个通用思维工具解题时自然就有了方向。反过来把刷题里学到的位掩码思路带到工作中去读源码也会顺畅很多。2. 七个基础运算符一次讲透从拆位运算说起2.1 先理清“拆位运算”到底是拆什么我记得很多编程入门练习题是这个画风小丽在编程课上学会了拆位运算她已经可以拆出一个两位整数的十位和个位了她想知道…… 这里的“拆位”其实是十进制拆数位标准答案就是两行int tens n / 10; int ones n % 10;严格说这跟位运算没有直接关系但它引出了一个很好的二进制概念拆位。把思维切到二进制之后“拆出一个数的第 k 位”就变成了右移加按位与int bit (n k) 1;n k把第 k 位移到最低位 1把其它高位全部清零。这一步就是二进制拆位最核心的公式。你后面遇到的绝大多数位运算题本质上都是这一行的变体。2.2 七个运算符速查与典型用途在讲具体题目之前先把 Java 的七个位运算符和使用场景完整过一遍运算符名称典型用途示例按位与清零、取位、判断奇偶n 1判断 n 是否为偶数按位或置位、合并标志位^按位异或翻转、去重、交换a ^ a 0~按位取反配合与运算做清零n ~(1 k)左移乘以 2、构造掩码1 k带符号右移除以 2、取符号位附近的信息n 1无符号右移除以 2 的幂不考虑符号n 1这里最需要重点理解的是异或^。它有三个非常关键的性质归零律a ^ a 0恒等律a ^ 0 a交换律和结合律都成立a ^ b ^ a b异或的这点性质直接造成了“只出现一次的数字”这类题目的最优解。2.3 位掩码基本功取、置、清、翻位运算在算法题里最常见的价值就是操作二进制位这四种操作建议背到条件反射// 取位取出第 k 位是 0 还是 1 int get (n k) 1; // 置位把第 k 位置为 1 n n | (1 k); // 清位把第 k 位清为 0 n n ~(1 k); // 翻转把第 k 位取反 n n ^ (1 k);清位操作稍微绕一点~(1 k)先构造一个“只有第 k 位是 0其他位都是 1”的掩码再用与运算把 n 的对应位清零。打个比方掩码就像一张带孔的贴纸想保留哪一位就留孔想清零哪一位就把孔贴上。如果题目给出多个标志位组合使用也很常见。比如用 int 的低 16 位存一组状态高 16 位存另一组状态读写时直接用移位和掩码提取。这种压缩存储的思想后面讲状态压缩 DP 的时候还会用到。3. 三道高频题从暴力解到位运算解的完整思路3.1 统计二进制中 1 的个数很多人的第一反应是把整数转成二进制字符串然后遍历计数。这样写当然能通过但仔细想想面试官问这道题的时候其实期待的是位运算解法。最经典的方案就是利用n (n - 1)。这个操作每次能把二进制表示里最右边的那个 1 变成 0。为什么因为n - 1会把最低位的那个 1 借位变成 0同时把更低位所有 0 都变成 1。比如n 12二进制是1100n - 1 11是1011两者相与得到1000也就是 8。你看最右边的那个 1 消失了但其他位没有受影响。完整代码public int hammingWeight(int n) { int count 0; while (n ! 0) { n n (n - 1); count; } return count; }循环次数等于二进制中 1 的个数而不是固定的 32 次。这套思路同时也是下一步判断“2 的幂”的基础建议把它吃透。这里有一个实战注意点输入如果是负数用做逐位右移可能死循环因为负数右移高位补 1。用n (n - 1)就没有这个问题它对负数的处理依然正确。如果实在想用逐位移动建议用无符号右移。3.2 只出现一次的数字题目背景是这样一个非空整数数组里除了某个元素只出现一次以外其余每个元素都出恰好出现两次找出那个只出现一次的元素。源码我已经反复写过好几次了先上答案public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; }这个解法的原理完全建立在异或的性质上两个相同的数异或等于 0任何数和 0 异或还是它自己。把数组所有元素全部异或一遍所有出现两次的元素都会成对抵消最后剩下的就是落单的那个数。暴力思路是哈希表统计次数空间复杂度 O(n)。排序后两两比较也需要 O(n log n) 的时间。位运算解法把时间和空间都压到最优代码还最短。但我想强调面试时最好先说出暴力解再推导到位运算解这样显得思考过程完整而不是“背过答案”。这个题目有个很自然的进阶版数组中只有一个数出现一次其他数都出现三次怎么找这时候不能用简单的异或需要统计各个二进制位上 1 出现的次数然后对 3 取模。答案是设计一个状态机或者直接用两个变量模拟“出现一次”和“出现两次”的状态。如果基础题已经吃透不妨顺着这个方向想一想理解会更深。3.3 判断一个数是不是 2 的幂2 的幂在二进制里有一个很漂亮的特点只有一个 1其他位全是 0。所以判断方法就很直接先排除非正整数再看n (n - 1)是不是等于 0。因为如果 n 只有一个 1那么 n 减 1 之后正好把这个 1 变成 0低位全是 1两者相与必然是 0。public boolean isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }注意这行代码里括号不能省。Java 的优先级高于如果写成n (n - 1) 0实际上会被解析成n ((n - 1) 0)这在 Java 里是编译错误因为不能作用在布尔值上。就算你用的是某些弱类型语言能编译过逻辑也完全错了。这是位运算题里非常经典的一类陷阱下一节我会专门展开。另外也可以看看 Java 提供的现成 APIInteger.bitCount(n)可以统计二进制 1 的个数Integer.highestOneBit(n)可以拿到最高位对应的 1。工程里直接用这些 API 没问题但刷题时最好还是把底层原理写出来面试官想听的是你懂不懂原理。4. 位运算解题中的常见坑符号、优先级和溢出4.1 负数右移我差点死循环有段时间我写“逐位移动统计二进制位”时习惯用直到遇到负数才发现问题。-1的二进制补码是全 1-1 1结果还是-1因为带符号右移会在高位补符号位 1所以循环条件n ! 0永远成立直接死循环。打磨成正确写法应该用public int bitCountByMove(int n) { int count 0; while (n ! 0) { count n 1; n n 1; } return count; }无符号右移永远在高位补 0所以负数的边界情况也能正确处理。面试里如果让你说和的区别这就是最核心的答案一个有符号一个无符号对负数的行为完全不同。4.2 位运算符优先级加了括号才算稳位运算在 Java 中的优先级比关系运算符和等值运算符都要低。除了前面说的n (n - 1) 0问题还有一个非常常见的写法是if ((flags FLAG) 0) { // 该标志位未设置 }这个括号绝对不能省。不写括号的话和的优先级会让表达式含义变得非常奇怪尤其在代码评审时很容易被人盯上。我的规矩很简单只要表达式里混用了位运算和比较运算一律把位运算部分用括号包起来不给自己留翻车机会。4.3 溢出、边界值和前导零的教训位运算很容易碰到边界值。比如1 31在 int 范围内结果是 -2147483648因为左移把符号位占满了。如果题目要求构造 32 位掩码老老实实用1L 31转成 long否则结果会跟直觉完全相反。再比如取绝对值。网上流传一种位运算写法(n ^ (n 31)) - (n 31)它对普通整数有效但碰到Integer.MIN_VALUE会溢出因为Math.abs(Integer.MIN_VALUE)也还是负数。刷题时一旦涉及极值我建议直接使用Math.abs或者先把 int 转成 long 再处理别为了炫技把自己坑了。还有前导零的隐形问题。判断某一位是否为 1 的时候如果整数值很小比如n 4二进制是100你以为第 3 位是 1、第 0 位是 0但别忘了一个 int 在高位其实都是 0。这个不会影响(n k) 1的结果但如果你自己打印二进制字符串去核对位数很容易看花眼。用Integer.toBinaryString(n)输出时高位 0 会被省略别误判。4.4 异或交换两个变量不是哪都能用位运算教程里很喜欢展示这招a a ^ b; b a ^ b; a a ^ b;它的原理是异或的自反性确实能实现变量交换面试偶尔也会被问到原理。但工程里我不推荐使用。一方面可读性差别人一眼看不懂另一方面如果交换的是同一块内存就会翻车比如数组里arr[i]和arr[j]交换时恰好i j这段代码会把该位置的值直接清零。我印象里某个老项目的代码就出过这种 bug排查了大半天。日常写代码一个临时变量简简单单就够用了。5. 进阶套路子集枚举和状态压缩的二进制思维5.1 一个 mask 就是整个状态位运算在算法题里最惊艳的应用我觉得是子集枚举。给定一个数组输出所有子集。常规思路是回溯但位运算能给出很优雅的写法public ListListInteger subsets(int[] nums) { ListListInteger res new ArrayList(); int n nums.length; for (int mask 0; mask (1 n); mask) { ListInteger subset new ArrayList(); for (int i 0; i n; i) { if ((mask (1 i)) ! 0) { subset.add(nums[i]); } } res.add(subset); } return res; }原理很直观数组长度为 n一共有2^n个子集。每个数在不在子集里正好对应一个 n 位二进制数的某一位是 0 还是 1。比如 n 3 时mask 从000枚举到111每个 mask 都代表一个唯一的子集。新手建议把mask、二进制形式、对应的子集三者列一张表手写一遍 0 到 7 的映射基本就能彻底理解。我当时是靠 IDE 打印Integer.toBinaryString(mask)才真正开窍的。5.2 状态压缩 DP不只能枚举还能做规划子集枚举只是起点状态压缩 DP 的核心思想是“用一个 int 承载一组状态”。比如某些问题里每个位置有选/不选两种状态那么 n 个位置一共就有2^n种状态恰好能用 int 的低 n 位表示。状态转移时也常用位运算判断某个元素是否已包含(mask (1 i)) ! 0把某个元素加入状态mask | (1 i)把某个元素从状态中移除mask ~(1 i)这就是为什么前面第 2 章的四种基本功如此重要。等到真正写 N 皇后位运算版或者哈密顿路径状态压缩 DP 的时候你会发现自己每一步都在用这些基础操作。不过我还是要劝一句状态压缩 DP 不是每个初学者都应该立刻冲上去的内容它建立在位运算熟练和 DP 基础之上。先把基础题目练熟再逐步进入进阶否则容易劝退。5.3 我给不同基础读者的练习路线根据我自己的经历位运算刷题建议分三档走入门档判断奇偶、交换两个变量、拆位、判断 2 的幂。这部分主要是熟悉运算符和掩码基本功。提高档统计二进制 1 的个数、只出现一次的数字、整数反转、汉明距离。这些题开始体现位运算的算法价值。进阶档子集枚举、只出现一次的数字进阶版其他数出现三次、状态压缩 DP、N 皇后位运算版。把二进制真正当成状态容器来思考。汉明距离这里提一句它就是两个整数异或之后统计 1 的个数本质是把 3.1 和 3.2 两道题组合起来用。这类组合题特别适合用来检验自己是不是真的理解了位运算而不是只会背答案。最后说一点我的真实体会。位运算刷题有一个很典型的“顿悟时刻”我是在亲手把子集枚举的 mask 全部打印成二进制之后才彻底明白的。对于新手有两点建议。第一不要一上来就迷信位运算。如果暴力解法都写不出来位运算只会让你更混乱。先保证常规解法能跑通再考虑用位运算优化这样每一步都心里有数。第二调试位运算一定要把数字转成二进制打印。写代码时随手用Integer.toBinaryString(n)把中间结果打出来你会看到、|、^、这些原本抽象的操作突然变得非常直观。我踩过的很多坑最后都是靠这种“肉眼调试”解决的。这就是我梳理 Java 位运算题目练习的全部心得。如果你也能从“拆位运算”这五个字开始一路练到状态压缩不卡壳我相信你面试时再碰到位运算题会跟我现在一样打心眼里觉得它是个好工具而不是吓人的偏门技巧。