1. 一次线上性能压测让我重新评估位运算的价值位运算技巧这东西我用一个词形容就是真香。早些年我对它的态度和大多数业务开发者一样就是面试和算法竞赛里才会碰到的东西日常写 CRUD 用不上。直到有一次优化内部网关服务我被一个权限校验函数卡住性能才意识到位运算在真实生产环境里根本不是冷门技巧而是实打实的性能武器。那次压测经历后来成了我整理位运算技巧的起点也让我发现很多人包括当时的我对它的理解都停留在背结论层面完全没有吃透背后的二进制原理。当时出问题的接口逻辑很简单每次请求进来都要把用户拥有的权限集合和当前资源要求的权限集合各转成一个 Set再做一次 retainAll 求交集。单看代码没有任何问题可并发一上来QPS 就卡在一个很尴尬的位置。用 profiler 抓热点罪魁祸首就是那段权限判断——它每次都要新建临时集合对象、跑循环、触发垃圾回收压力几乎全打在堆上。后来我试着换了一个看上去有点原始的方案把权限定义成位掩码。读权限占第 0 位写权限占第 1 位删除权限占第 2 位用户的权限不再是一堆字符串而是一个 int。校验用户是否拥有某个权限只需要算一次(userPerms requiredPerms) ! 0。没有循环、没有临时集合、没有内存分配压测结果直接差了接近一倍GC 频率也肉眼可见地降了下来。就这么一个改动让我彻底转变了对位运算的态度。这篇总结整理的是我这些年真正用过的位运算技巧覆盖算法刷题、状态压缩、权限系统、海量数据过滤几个方向。每一个技巧我都会尽量讲清推导过程和边界条件而不是只丢一行代码让你背因为只记住结论很容易在负数、溢出、运算符优先级这些地方翻车。适合后端开发者、算法竞赛选手还有每一个看到位运算题解就一头雾水、想真正弄懂的人。2. 七个高频技巧记住推导比记住结论更重要位运算的核心运算符其实就六个与 、或 |、异或 ^、取反 ~、左移 、右移 。难的不是认识它们而是把这些简单的运算组合成能解决问题的技巧。下面这七个是我使用频率最高的我会按结论 - 原理 - 边界的顺序挨个讲明白。2.1 奇偶判断用 x 1 而不是 x % 2判断一个整数是奇数还是偶数大多数人第一反应是写x % 2。这个写法没错但如果愿意贴近底层x 1是更直接的做法它把整数的最低一个比特位取出来。二进制里最低位是 1这个数一定是奇数最低位是 0就一定是偶数。与运算本身就是两个位都为 1 结果才是 1所以x 1天然就是在问最低位是不是 1。这里要特别说明的是负数也没问题。无论是 C/C 还是 Java负整数都以补码形式存储补码的最低比特位依然准确表示奇偶性所以x 1对负数同样成立。而x % 2在 C 语言里对负数的结果是 -1、0、1 三种可能判断时还得小心。真的要在热路径上判断奇偶我建议直接用(x 1) 0表示偶数语义明确也不用担心负数的取模问题。不过这里藏着一个 C 语言老手都容易踩的坑的优先级比低。如果写成x 1 0编译器会先算1 0结果是 0再算x 0恒为 0。这个 if 判断永远不会成立。所有的位运算参与比较时一定要加括号这几乎可以算作位运算的第一条军规。2.2 交换两数异或的魔法与陷阱算法题解里经常出现这样三行让人印象深刻的代码a a ^ b; b a ^ b; a a ^ b;推导过程很简洁。异或满足自反性x ^ y ^ y等于x。第一行执行后a变成a ^ b第二行用这个值去异或b得到(a ^ b) ^ b a赋给b第三行再用它异或现在的a得到(a ^ b) ^ a b赋给a。三步完成交换全程没有引入临时变量。但这个技巧在实战里有个隐蔽的致命陷阱如果a和b指向同一个内存单元第一步就会把这块内存变成 0后面两步全错。比如写了swap(arr[i], arr[i])或者两个引用指向同一个对象。所以我的建议很直接这种交换写法只适合算法竞赛中双方来源明确不同的场景生产代码里老老实实用一个temp变量更稳妥。编译器对经典交换的优化早就做到极致了位运算交换在性能上并不会赢只是看起来酷而已。2.3 判断 2 的幂x (x - 1) 的经典用途判断一个正整数是不是 2 的幂流传最广的写法是boolean isPowerOfTwo(int x) { return x 0 (x (x - 1)) 0; }原理要从二进制结构说起。2 的幂在二进制里只有一个 1比如 8 是1000。当它减去 1 后变成0111原来那个唯一的 1 变成了 0低位的 0 全部变成 1。这样的两个数做与运算每一位都不相同结果必然是 0。反过来一个数如果不是 2 的幂二进制里至少有两个 1减 1 会改变最低那个 1 及其右边的位高位那个 1 依然存在与运算的结果就不会是 0。我第一次在树状数组的 lowbit 相关代码里看到这个判断时也是一脸懵后来自己手动列了几组二进制才真正接受。使用时要特别注意第一句话的正整数x 0这个条件不能省。0 的二进制里没有 10 (-1)的结果也是 0但它显然不是 2 的幂。2.4 lowbit 与清除最低位的 1x (-x)可以取出一个数最低位的 1这个操作用处极大通常被称为 lowbit。比如12的二进制是1100它的 lowbit 是100也就是 4。为什么补码能做到这一点因为-x等价于~x 1取反加一的效果是从最低位开始第一个遇到的 1 保持不变它右边原本全是 0取反后变成 1加一进位后又变回 0它左边所有位取反。这样x与-x相与低位的 1 保留了下来其他位全部抵消成 0。lowbit 是树状数组的核心操作。树状数组更新和查询时依赖i i (-i)、i - i (-i)来移动索引没有 lowbit 就没有这个数据结构。与 lowbit 互补的另一个操作是x (x - 1)它用来清除最低位的 1其他位不受影响。这两兄弟一个取出最低位的 1一个删掉最低位的 1是很多位运算技巧的基石务必亲手在纸上推演一遍补码变化。2.5 统计二进制中 1 的个数Brian Kernighan 算法算法竞赛里有一道非常经典的题统计一个整数的二进制表示中有多少个 1。最朴素的做法是循环 32 次每次都右移一位再与 1 相与。但还有一个更优雅的算法利用x (x - 1)每执行一次就消掉一个最低位的 1int countOnes(int x) { int count 0; while (x ! 0) { x x (x - 1); count; } return count; }这个算法的循环次数等于二进制中 1 的个数而不是固定的 32 次。如果一个数的二进制只有两三个 1效率会明显高于固定循环。它的正确性建立在 2.4 小节讲的清除最低位 1上每轮都删掉一个 1删到 0 为止删了几次就有几个 1。Java 标准库里虽然提供了Integer.bitCount底层用的是更复杂的分组查表法但理解这个经典算法对建立位运算直觉很有帮助。2.6 异或去重只出现一次的数字异或运算有三个基本性质值得刻进脑子里a ^ a 0a ^ 0 a异或满足交换律和结合律。靠这三条性质可以轻松解决一类成对消去的题目。最典型的一道题是一个数组里所有数字都出现两次只有一个数字出现一次把它找出来。直接的做法是把所有数字全部异或起来。出现两次的数字会两两抵消变成 0剩下的唯一数字与 0 异或还是它自己答案自然就出来了int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; }这个技巧还可以升级成找两个出现一次的数字先把所有数字异或得到的是两个目标数字的异或结果再找到这个结果中最低位的 1用这个位把原数组分成两组同一组内再次异或就能分别得到这两个数字。核心思想始终不变——异或就是天然的消消乐成对的数据会被自动消除。2.7 第 k 位的读取、置位、清零与翻转最后这四个操作几乎是所有位运算场景的基本功单独列出来讲清楚。假设 k 从 0 开始计数即第 0 位是最右边的比特位那么一组完整的基础操作如下读取第 k 位int bit (x k) 1;将第 k 位置为 1x x | (1 k);将第 k 位清零x x ~(1 k);翻转第 k 位x x ^ (1 k);读取的原理是先把目标位移到最低位再用与 1 运算只留下这一位。置位靠1 k构造一个只在第 k 位为 1的掩码用|强制置 1。清零则相反先对掩码取反得到除了第 k 位是 0其他位全是 1再与x相与就能在不影响其他位的前提下把第 k 位清掉。翻转用异或x ^ (1 k)会让第 k 位 0 变 1、1 变 0其他位原样保留。为了便于日常查阅我把前面这些高频技巧整理成一张速查表目标表达式说明判断奇偶(x 1) 1最低位为 1 是奇数判断 2 的幂x 0 (x (x - 1)) 0减 1 后相与为 0取最低位的 1x (-x)树状数组 lowbit清除最低位的 1x (x - 1)循环可统计 1 的个数读取第 k 位(x k) 1k 从 0 开始置第 k 位为 1x | (1 k)掩码构造清第 k 位为 0x ~(1 k)取反后相与翻转第 k 位x ^ (1 k)0 变 1、1 变 03. 状态压缩的完整玩法从集合映射到 DP 优化如果你只在单个数值上使用位运算它的上限就停留在第 2 部分的那些小技巧上。但位运算真正能拉开差距的地方是把一个整数当成一个集合来用这种思路叫状态压缩。它不只在算法竞赛里发光发热在真实的高性能业务场景中同样非常有价值。3.1 集合与位运算的一一映射假设我们有一个集合元素都是非负整数且数量不超过 32 个。这时候一个 int 的每一位就能表示一个元素是否出现第 i 位为 1 表示 i 在集合中为 0 表示不在。在这种表示下集合运算可以直接变成位运算映射关系非常漂亮集合运算位运算典型应用交集a b两组权限共有的部分并集a | b权限合并差集a ~b拥有 a 但没有 b判断子集(a b) aa 的所有元素都在 b 中求元素个数统计 1 的个数也就是 Kernighan 算法的活这个映射最直接的价值是原本需要一个对象数组才能表达的东西现在压缩成一个数字。无论内存占用还是比较速度都是数量级上的提升。比如判断两个权限集合是否存在包含关系原来要遍历一个 Set现在一行位运算完成而且完全不会有对象分配。当你习惯了整数即集合的思考方式很多问题的表达会瞬间变得简洁。3.2 枚举子集一个 for 循环搞定所有非空子集状态压缩最常用的操作之一是枚举某个集合的所有子集。假设我们有一个掩码mask表示集合想枚举它的所有非空子集经典写法长这样for (int sub mask; sub 0; sub (sub - 1) mask) { // 处理子集 sub }第一次看这段代码确实有点魔幻。它的执行过程是这样的sub从mask本身开始每次减 1 相当于往较小的数退再用 mask把不在集合里的位全部清掉。这样得到的序列会跳过大量无效状态只落在mask的真实子集上。循环直到sub变成 0 结束0 是空集通常单独处理。需要注意(sub - 1) mask这段逻辑在sub 0时没有意义所以循环条件要限定sub 0。如果确实需要把空集也纳入处理就在循环结束后把sub 0的情况单独算一遍。这个枚举技巧在暴力搜索和动态规划中出场率极高熟练掌握后复杂度从不知道怎么写变成一行循环搞定。3.3 实例旅行商问题的状态压缩 DP光谈理论很难体会到状态压缩的威力我拿一个经典问题来说明。假设有 n 个城市n 不超过 16给出任意两个城市之间的距离要求从 0 号城市出发每个城市恰好访问一次最后回到 0求最短路径。朴素搜索的复杂度是 n 的阶乘n 16 时完全不可行。但用状态压缩 DP 可以降到大约 O(2^n * n^2)。定义dp[mask][i]表示已经访问过mask集合中的城市并且当前停在城市 i 的最短距离。转移时枚举下一个城市 j它必须不在mask中for (int mask 0; mask (1 n); mask) { for (int i 0; i n; i) { if ((mask (1 i)) 0) continue; for (int j 0; j n; j) { if ((mask (1 j)) ! 0) continue; int next mask | (1 j); dp[next][j] min(dp[next][j], dp[mask][i] dist[i][j]); } } }这个 dp 数组就是建立整数即集合这个核心思想上的。如果不给每个城市配一个比特位你根本不可能用 65536 种状态去表达 16 个城市的访问情况。刷题时只要看到 n 不超过 20 这类限制条件心里就应该自动映射出这题多半要用位运算压状态。状态压缩 DP 的典型特征就是把一个布尔数组压缩进一个整数的比特位理解集合映射之后再看这类题解会有种豁然开朗的感觉。4. 业务代码里的位运算权限、位图、过滤器有些朋友可能会说我不打竞赛位运算对业务开发到底有什么用我负责任地说用处不小。权限系统、海量数据统计、缓存设计与哈希运算这些日常领域都有位运算的深度参与而且都不是什么冷门场景。4.1 权限系统的位掩码设计把权限定义成 2 的幂是真实系统里非常好用的一套权限模型。比如const int READ 1 0; // 二进制 001 const int WRITE 1 1; // 二进制 010 const int DELETE 1 2; // 二进制 100一个用户的权限集合就是一个 int比如同时拥有读写权限就是 3。判断是否有权限、添加权限、移除权限分别对应与、或、与非boolean hasPermission(int userPerms, int required) { return (userPerms required) ! 0; } int addPermission(int userPerms, int permission) { return userPerms | permission; } int removePermission(int userPerms, int permission) { return userPerms ~permission; }其中移除权限的写法很典型先对permission取反得到除了这一位是 0、其他位全是 1 的掩码再与userPerms相与就把对应位清零了其他权限不受任何影响。判断是否拥有某一组权限中的任意一种直接把整个 required 集合与一下非零即通过如果需要全部拥有判断(userPerms required) required。这套模型另一个诱人的地方是存储友好。一个 int 字段就能存下所有权限查询时不需要拆字符串、不需要多次关联查询数据库里一个整数搞定。前提是权限总数不超过 32如果超过就换 long 支持 64 个。不少权限管理系统就是这么设计的既省空间又省 CPU代价仅仅是第一次理解位掩码需要花点时间。4.2 BitMap用 1 个比特表示一条记录BitMap 的核心思想是用一个 bit 表示一个元素是否存在在数据量大、值域相对集中的场景下非常省内存。举个例子有 1 亿个用户 ID范围在 0 到 1 亿之间需要判断某个 ID 是否存在。如果用 HashSet 存 Integer内存占用要几百 MB换成 BitMap每一位对应一个 ID总共只要 1 亿 bit约 12.5MB差了不止一个量级。实现思路不复杂。假设一个 long 有 64 位第 i 位落在数组下标i / 64的那个 long 里字节内偏移是i % 64。置位bitmap[index] | (1L offset);查询boolean exists (bitmap[index] (1L offset)) ! 0;这套思路在我处理超大规模日活统计时救过场把内存占用从 GB 级压到百 MB 级而且置位和查询都是常数时间性能上完全不吃亏。很多开源缓存组件的 bitmap 功能、大数据去重方案底层本质都是这么实现的。Redis 的 bitmap 命令就是典型代表虽然它可以处理更大的位数组但核心算法和这里没什么区别。4.3 布隆过滤器与哈希加速布隆过滤器本质上是一个位数组加多个哈希函数。插入时用 k 个哈希函数算出 k 个位置把这些位置置 1查询时检查这 k 个位置是否全为 1。这里的置位和判断靠的就是和|这些位运算。布隆过滤器允许误判但能非常高效地回答肯定不存在或者可能存在作为海量数据场景的前置过滤器非常有用能挡掉大部分查询压力真正需要精确判断的再落到存储层。哈希表内部也大量使用位运算。很多高性能哈希表实现会用hash (capacity - 1)来计算桶的位置前提是容量是 2 的幂。这样取模运算就变成了位运算在频繁访问的热路径上更可控。我自己实现简易缓存结构时就让数组长度始终是 2 的幂实测高频读写场景下确实有可感知的收益。网络协议解析更不用说了IP 地址与子网掩码相与判断网段、数据包的标志位提取全是位运算的直接应用。搞懂位运算之后再看这些底层源码会顺畅很多。5. 这些位运算的坑我每个都踩过位运算的代码看起来短小精悍但正因为短小结合运算符优先级、有符号数和溢出问题特别容易埋雷。下面的坑我全部踩过有些还排查了很久写出来希望你能直接绕开。5.1 优先级陷阱 比 低括号不能省这是新手最容易踩的坑。在 C/C 和 Java 里位运算符的优先级都比关系运算符低具体来说的优先级低于。所以前面提到的if (x 1 0) { // 你以为在判断偶数 // 实际是 x (1 0) }编译器先计算1 0结果是 0再算x 0恒为 0这个 if 条件永远为假。我曾在一次代码评审中见过类似的写法同行们盯着代码看了半天没发现问题最后跑单元测试才发现逻辑根本不对。解决办法没有技术含量所有位运算参与比较时一律加括号没有例外。宁可多写一对括号也不要指望自己记住优先级。5.2 有符号右移与逻辑右移的区别右移运算在不同的语言里语义不完全一样。C/C 对 signed int 的右移通常是算术右移也就是高位补符号位Java 里是算术右移才是逻辑右移。这个区别在处理负数时非常关键。比如 -2 的补码是111...1110算术右移一位得到111...1111也就是 -1而逻辑右移一位得到011...1111是一个很大的正数。如果你的目的是把二进制位整体右移、高位补 0必须使用逻辑右移或者操作无符号类型否则结果会完全超出预期。写跨语言代码时尤其要留意C 语言没有 Java 的这个坑在项目从一种语言迁移到另一种语言时很容易爆发。5.3 右移一位不等价于除以 2很多初学者把x 1当作x / 2的位运算优化这在正数时确实成立但负数就完全不是一回事。C/C 的除法结果向 0 舍入而算术右移结果向下舍入。举个例子-3 / 2在 C 中的结果是 -1但-3 1的结果是 -2两者相差 1。所以写通用算法时不能粗暴地用替代/除非你能保证操作数非负或者你明确需要向下取整的语义。同理x % 2对负数的语义在不同语言里也不一致而(x 1)永远是取最低位语义清晰无歧义。我的经验是位运算替代算术运算之前先想清楚操作数会不会是负数。5.4 左移溢出与 INT_MIN 陷阱左移也可能翻车。对于 int 类型1 31在二进制上是第 31 位为 1而这个位置的 1 恰恰是补码的符号位所以它对应的 int 值会是一个负数。如果你期望得到正数来表示第 31 位那就错了。想要表示完整的 32 位建议使用 unsigned int 或者直接上 long。还有 INT_MIN 这个极端值。INT_MIN 的绝对值在补码表示下没有对应的正数对它取负会溢出。很多位运算取绝对值的技巧在它面前都会失效比如下面的写法int abs(int x) { int mask x 31; return (x mask) ^ mask; }这个公式看起来巧妙但在x INT_MIN时溢出行为未定义。所以这类位运算取绝对值的技巧只适合确认输入不会越界的场景。写通用代码时老老实实用条件判断反而更安全。很多面试题喜欢考位运算但边界条件恰恰是考验位运算功底的地方。6. 实操心得什么时候该用位运算什么时候别硬上最后聊一点比较主观的判断标准。位运算不是万能的也不是越花哨越好。经过这些年反复使用我给自己定了三条原则想分享给你参考。第一优先用在空间敏感、数据量大的场景。海量数据去重、布隆过滤器、状态压缩 DP这些是位运算不可替代的价值所在。当内存占用从 GB 级降到 MB 级只有位运算能轻松做到其他方案都差着数量级。这类场景不需要犹豫该上就上。第二用在热路径上的简单判定。像权限校验、标志位检查、哈希桶定位一秒内执行几十万次位运算一条指令完成比其他写法更可控。但前提是代码可读性不能崩我会在关键表达式旁边写清楚注释比如标注这一步等价于集合交集方便后来维护的人理解。第三别为了用而用。如果是普通业务逻辑集合操作、对象判等已经足够清晰强行用位运算只会让同事抓狂。现代编译器对常规算术的优化相当成熟一个a * 2早就被优化成移位了你手动写a 1并不会更快反而可能让语义变得模糊。位运算真正的战场是那些数据规模大、内存宝贵、判断简单高频的角落而不是所有地方。如果一定要给出一条学习路径我的建议是先把第 2 部分的七个基础技巧吃透亲手在纸上推演二进制变化然后把第 3 部分的集合映射和子集枚举写熟练最后再看业务场景把权限掩码这样的模型套进自己的项目里。位运算最迷人的地方是理解它之后你看很多底层源码和竞赛题解会突然变得顺滑起来——那种原来如此的体验很值得花时间。