位运算这东西我做了这么多年开发日常写业务代码用得不算多但只要遇到性能瓶颈、算法优化、底层协议解析、状态压缩这些场景它几乎是唯一能让你“优雅地暴力”的手段。说实话很多程序员对位运算的理解停留在“知道有这回事”真要上手写的时候要么怕优先级搞错要么不知道什么场景该用。这篇博客就把我这些年积攒的位运算技巧做个系统的梳理从最基础的二进制特性讲到实战中的巧妙应用每一招都会解释原理和它背后的数学逻辑而不是只丢给你一个结论让你背。这篇内容适合任何写代码的人不管你是搞业务开发的、写算法的、做嵌入式的还是刚入门的学生掌握这些技巧你在读源码、写高性能代码、刷算法题的时候都会有不一样的视角。1. 位运算整体设计与思路拆解1.1 为什么要依赖位运算本质是直接操作硬件思维很多初学者不理解为什么明明有 - * /这些算术运算符非要绕一圈去用 | ^ ~ 。这里有个最底层的逻辑计算机里的一切数据最终都是二进制位运算就是直接对着这些二进制位做操作没有任何中间转换在硬件层面执行一个位运算只需要一个时钟周期而乘法、除法往往需要多个周期。举个例子你写a % 2来判断奇偶正常编译器的确会把它优化成a 1但如果你在写一段性能敏感的内层循环、嵌入式裸机代码或者面对一个不懂得优化的解释型语言环境直接使用位运算就能在一开始就拿到最优性能。更重要的是位运算不只是性能上的优势很多算法思想本身就构建在位运算之上——哈希函数、布隆过滤器、状态压缩DP、树状数组、网络协议解析全都离不开它。1.2 位运算的适用边界明确它解决什么问题任何一个工具都有边界的位运算也不例外。我个人的使用经验是它适合解决这几类问题性能敏感型执行频次极高的核心循环能用位运算替代算术运算就替代。状态表达型多个布尔开关、权限标记、配置项要打包存储用一个整数就能装下。算法核心型某些问题比如求子集、排列组合状态、找唯一出现一次的数字用位运算的解法在清晰度和效率上都碾压其它方式。内存受限型嵌入式、游戏服务器等场景用位图bitmap代替数组存储海量标志位内存能省几十倍。但位运算不是万能的。如果你的代码是要长期维护的业务系统可读性永远是第一位的没必要为了用技巧而用技巧。一个良好的原则是把位运算封装成语义清晰的函数比如hasPermission()、isPowerOfTwo()内部可以实现得巧妙外部调用者看到的是含义明确的方法名。1.3 从问题倒推方案解题时如何想到用位运算很多读者问过我“看别人代码里突然蹦出一行x (x - 1)我当时根本反应不过来这是在干嘛。” 这个问题其实有解法。我总结了一套“位运算雷达图”当遇到以下信号时就该条件反射地往位运算上想问题是关于“集合”的而且集合元素很少比如一个数组的若干个属性开关。问题是关于“出现次数奇偶”的异或的标准场景。问题是关于“整除2、判断2的幂、取余2”的。问题涉及掩码mask、开关、权限、标志位。问题要求空间复杂度极低不允许开额外数组。如果你判断一个场景命中上述任何一条就往位运算方向试试大概率能找到一个比常规解法更精简的方案。2. 位运算核心技巧详解原理、代码、实战心得2.1 判断奇偶x 1不只是省一点点时间最基础的技巧判断一个整数是奇数还是偶数。常规写法是x % 2 0位运算写法是(x 1) 0。原理也非常直接任何偶数的二进制最低位都是0奇数的二进制最低位是1所以x 1的结果等同于x % 2。这个技巧在绝大多数语言里都能直接用if ((x 1) 0) { // 偶数分支 } else { // 奇数分支 }但这里有个细节我要特意提醒在Java、C系语言里位运算的优先级低于所以括号不能省。我见过无数人写if (x 1 0)这行代码的解释是x (1 0)结果恒为0永远进不了分支特别坑。这种基础技巧本身不复杂真正容易出问题的是优先级。为什么这个技巧值得用除了减少一次模运算的时间开销在一些特殊场景还有奇效。比如判空集合的时候可以用空数组长度为0来判断而处理循环时用i 1控制交替逻辑能省去定义一个布尔变量反复翻转。这就是我常说的“用位运算替代额外变量”的思路。2.2 交换两个变量的值异或的魔法但别迷信很多人最早接触的位运算技巧一定是这个不借助临时变量交换两个整数。a ^ b; b ^ a; a ^ b;拆开来看第一步后a a ^ b。第二步b a ^ b (a ^ b) ^ b a ^ (b ^ b) a这里利用了异或的自反性x ^ x 0x ^ 0 x。第三步a a ^ b (a ^ b) ^ a b。这个技巧看起来很酷但我要负责任地提醒一句在日常应用中它没有实际优势。现代编译器的寄存器分配能力极强用临时变量交换通常会被优化成寄存器交换指令并不慢而且可读性远高于异或交换。异或交换真正的价值有两个一是让你理解异或的数学性质二是在极少数寄存器极度受限的嵌入式环境下可能有用。别为了炫技而牺牲代码可读性这是我在Code Review中经常提醒同事的。2.3 判断一个数是不是2的幂x (x - 1)的经典应用这个技巧是面试高频题。判断正整数x是否为2的整数次幂。bool isPowerOfTwo(int x) { return x 0 (x (x - 1)) 0; }原理的关键在于“2的幂”的二进制表示里只有一个位是1。比如 8 是1000减1后得到0111两者相与得到0。反过来如果 x 不是2的幂二进制里至少有两个1减1以后不会消掉全部高位相与结果就不为0。我第一次用这个技巧是在写一个内存分配器。当时需要判断用户请求的大小是否正好满足某个内存池的规格都是2的幂用这个位运算判断比维护一张表高效得多。顺带一提这个式子还有一个衍生用法x (x - 1)可以消除二进制最右边的那个1这个特性在后面计算1的个数时很有用。2.4 计算二进制中1的个数Brian Kernighan算法统计一个整数的二进制表示中有多少个1常规思路是循环右移逐位检查但更优雅的是 Brian Kernighan 算法int countOnes(int x) { int count 0; while (x) { x (x - 1); count; } return count; }这个算法利用的就是“x (x - 1)消去最右边那个1”的性质。每次循环消掉一个1循环次数等于1的个数而不是固定的32或64次。平均性能优秀而且代码简洁有力。我在工作里用这个函数做过海明距离计算、位图存储对象数量的统计。如果你在用Java有个更取巧的方式Integer.bitCount(x)它底层是并行计数把32位拆成多个2位组、4位组分别计数再合并原理上和Kernighan不同但效率更高。理解Kernighan算法最大的意义在于这个“消去最低位1”的思路能启发你解决很多别的位操作问题。2.5 获取最低位的1x (-x)与树状数组的底层逻辑如果要选一个“最优雅的位运算技巧”我会投给lowbit(x) x (-x)。它获取的是x二进制中最低位的1所表示的值。比如lowbit(12) 4因为12是1100最低位的1在第三位对应值4。原理在于负数的二进制是正数的补码取反加1。以121100为例-12的补码是01001100取反0011加1得0100两者相与得到0100恰好是最低位1所在的那个位次。这个技巧在树状数组Fenwick Tree里是核心操作每次更新和查询都需要靠 lowbit 在树节点之间跳跃。我当年理解树状数组时卡了很久想通lowbit之后整个数据结构一下子就有了“骨架感”。这也说明位运算技巧不是孤立的它往往是底层数据结构的承重墙。2.6 掩码操作置位、清位、翻转、查询一个干净利落位运算在工程里最大的应用场景就是掩码操作。给定一个整数状态寄存器int flags我们需要独立操作它的每一个位。将第k位设为1flags | (1 k)将第k位清为0flags ~(1 k)翻转第k位flags ^ (1 k)查询第k位(flags k) 1这套技巧的底层逻辑是(1 k)构造了一个只在第k位为1、其余位为0的掩码。置位用或只要有1就是1清位用与掩码取反后第k位变成0其余位是1所以保持不变翻转用异或异或1会取反异或0保持不变。我印象最深的一个实际应用是在一个网络协议解析模块里。协议头里有多个标志位FIN、SYN、RST、ACK等每1比特一个含义。解析时就是把这些位用掩码提取出来封包时把它们用移位和或运算装回去。用位运算处理这类固定格式的二进制协议极其自然、高效。2.7 异或的三大性质找唯一出现一次的数字异或是位运算中最有数学味道的运算符它的运算规则可以概括为“相同为0不同为1”其本质是二进制不进位加法。异或的三大性质是交换律a ^ b b ^ a结合律a ^ (b ^ c) (a ^ b) ^ c自反性a ^ a 0a ^ 0 a基于自反性就有了那道经典算法题一个数组里只有一个数出现一次其他数都出现两次找出这个数。int findUnique(int arr[], int n) { int result 0; for (int i 0; i n; i) { result ^ arr[i]; } return result; }因为相同的数异或之后变成0出现两次的数都抵消了最后剩下的就是出现一次的数。这个解法的时间和空间复杂度都做到了最优。我还用它处理过一个更实际的场景两个设备之间传输数据为了做一个快速校验可以把所有字节异或得到一个校验字节接收方重新异或结果必须为0。这个场景里没有用复杂的CRC因为那个协议对传输可靠性要求不高异或校验完全够用。需要警惕的是异或的“找唯一数”思路只对“其他数出现偶数次”有效。如果其他数出现3次异或就处理不了需要另想办法比如逐位计数取模。这一点在面试里经常是追问点要注意。2.8 状态压缩与位掩码用一个整数表达一组开关状态压缩是位运算在算法题中的高价值应用之一。假设你有若干个开关状态每个状态只有开/关两种取值你就可以用一个整数的二进制位来表达所有这些状态。比如有8盏灯每盏灯有亮/灭两种状态用一个byte就能存储全部状态比用8个boolean变量省8倍空间。实际操作// 打开第3盏灯 state | (1 3); // 关闭第5盏灯 state ~(1 5); // 判断第3盏灯是否亮 (state 3) 1; // 枚举所有状态 for (int mask 0; mask (1 n); mask) { // 对每个状态处理 }(1 n)是2的n次方枚举0到(1 n) - 1的所有整数就是枚举了n个元素的全部子集。这个技巧在状态压缩动态规划状压DP里是核心基础比如旅行商问题、铺砖问题等它的应用场景非常广阔。我个人认为状态压缩是位运算最容易让你“打开新世界大门”的一部分很多原本需要数组甚至二维数组表达的状态一个整数就能搞定。3. 实操过程位运算在真实场景中的落地3.1 案例一Linux文件权限的读写执行权限系统的工程范式如果你用过Linux系统一定见过这种写法chmod 755 file。其中的755拆开看就是7rwx、5r-x、5r-x。这里r代表读、w代表写、x代表执行它们恰好可以用位的开关来表示。在这种权限模型里读、写、执行的权限值通常设计为权限位掩码十进制二进制读r1 24100写w1 12010执行x1 01001判断用户是否可读常规写法(permission 4) ! 0用位运算是(permission READ_MASK) ! 0。增加权限用permission | WRITE_MASK删除权限用permission ~EXEC_MASK。我在自己设计一个后台管理系统的操作权限模块时完全复用了这套思路。当时用户有“查看、编辑、删除、导出”四种操作权限如果一个用户拥有全部权限就是0b1111 15只拥有查看和导出是0b1001 9。存储上只需要一个tinyint字段查询的时候用位与运算直接过滤不用关联多张权限表。唯一要注意的是Mysql里整数的存储宽度不要超出字段类型范围。3.2 案例二用位图bitmap对海量整数去重有一个非常经典的面试场景给你 40 亿个不重复的整数内存不够如何判断一个数是否存在答案是使用位图。把每个整数的“是否存在”映射到一段二进制位空间上存在则对应位置1不存在保持0。查询时只需要检查对应位是否为1。这个方案的底层操作就是前面讲的掩码技术#define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F // 将第i位设为1 void set(int i) { bits[i SHIFT] | (1 (i MASK)); } // 查询第i位 int test(int i) { return bits[i SHIFT] (1 (i MASK)); }除以32用右移5位替代取余32用 0x1F替代这两个替代位运算正好对应了x / 32和x % 32在除数是2的幂时的加速写法。我第一次在实际项目中用位图是在一个爬虫系统里做URL去重。当时需要记录几千万个URL是否已访问如果直接用HashSet内存开销非常大每个字符串对象加上哈希表开销随随便便几个GB。改用布隆过滤器本质就是位图加多个哈希函数之后总共只要几百MB而且误判率控制在1%以下。这是我实际受益最明显的位运算工程应用。3.3 案例三集合操作用位运算完成交集、并集、差集把两个集合编码成两个整数或长整数位运算可以直接完成集合运算交集a b并集a | b差集A - Ba (~b)对称差只在其中一个集合出现的元素a ^ b这里的一个潜在坑是~b在C语言里会将高位所有位取反如果整数类型是无符号的取反后高位全是1与a做与操作时可能得到不期望的结果。正确做法是在做差集前先将~b与全集的掩码再做一次与运算把超出范围的位清掉。这个技巧在写算法题时非常好用比如给定一个由若干字符串组成的集合判断某两个集合是否有交集如果每个集合都可以用一个整数表示前提是元素总数量小于整数位宽交集判断就是一次if (a b)比遍历集合快了几个数量级。3.4 案例四利用移位实现快速乘除法和取模这个技巧只适用于乘以或除以2的整数次幂的场景x * 2^n等价于x nx / 2^n等价于x n只适用于无符号数或不关心正负符号时x % 2^n等价于x (2^n - 1)例如x 7就是x % 8我在做图像处理算法的时候经常用这个。比如对单通道灰度图像的像素值做归一化时需要除以255这时候不能直接用位移255不是2的幂。但是很多图像尺寸是8的倍数、16的倍数需要对对齐操作时 7、 15就非常高频。还有哈希表的容量设计为2的幂取模就可以用位运算替代这是Java HashMap能在高并发场景保持高性能的细节之一。特别注意对有符号整数做右移是算术右移高位补的是符号位不是0。所以-8 1结果是-4看起来没错但如果你期待它等价于-8 / 2在向零取整的场景就会出错-7 / 2是-3而-7 1是-4。所以这类优化几乎只在无符号场景使用有符号数做右移优化要特别小心。4. 常见问题和排查技巧实录4.1 优先级问题这块是重灾区位运算的优先级陷阱几乎每个程序员都踩过。C/C和Java里位运算符的优先级从高到低大致是~ ^|这比算术运算符低又比逻辑运算符高。最坑的是位运算符优先级低于所以你在写条件判断时一定要把位运算表达式用括号包起来。我举几个我实际见过的问题if (x 1 0) // 错误被解析为 x (1 0)永远为0 if ((x 1) 0) // 正确 int a x 2 1; // 错误被解析为 x (2 1)而不是 (x 2) 1建议养成一个习惯写位运算表达式一律用括号把每个操作明确括起来。这不是胆小这是在保护自己和同事的头发。4.2 符号位与右移行为不同语言还有差异防不胜防有符号整数右移分为算术右移和逻辑右移两种。在C/C中对有符号数使用是算术右移高位补符号位对无符号数是逻辑右移高位补0。Java的情况不同是算术右移是逻辑右移。Python没有位数上限概念但负数的右移行为对初学者也是噩梦。举个例子int x -16; // 二进制 ...11110000 int arith x 2; // 结果 -4高位补1 int logic x 2; // 结果 1073741820高位补0所以当你要把一个整数当成纯二进制位串来操作时比如位图、协议解析、散列计算优先使用无符号类型或逻辑右移。我在写文件校验和的时候曾因为用了而不是导致不同平台上的校验结果不一致排查了很久才发现是符号位扩展在作怪。4.3 位数不够与溢出别等数据截断了才后悔位运算本身不报错但它对数据宽度极其敏感。举个真实案例我想用一个int记录一天的秒数1 20当秒用没问题但想用1 30表示更长时间范围时如果平台int只有16位虽然现在少见结果就直接截断了。更常见的是在状态压缩中int fullMask (1 n) - 1; // 当 n 31 时1 31 在有符号 int 中是负值这个bug在面试中经常出现。正确的写法是(1 n)前先把1转成无符号或长整型或者直接用(1U n) - 1。在Java中如果有更多状态位就直接考虑用long甚至BitSet。4.4 可读性与维护性位运算不是越炫越好我见过一段新手写的高度“炫技”代码把十几个位操作连在一起没有注释、没有命名常量。结果是自己几天后回来看也没看懂当时想干嘛。我的经验是位运算要配合命名常量和良好封装public static final int READ 1 0; public static final int WRITE 1 1; public static final int EXEC 1 2; public static boolean hasPermission(int permissions, int permission) { return (permissions permission) permission; }把位运算的细节藏在语义明确的函数里调用方永远只需要面对“有没有权限”这样的自然语言问题。这既保留了位运算的性能又不牺牲代码的可读性。4.5 调试位运算打印二进制是我最常用的办法排查位运算问题时人脑很难直接脑补出十六进制或十进制的二进制形态。我强烈的建议是在调试时直接打印二进制形式。不同的语言都有办法// Java System.out.println(Integer.toBinaryString(x)); // C/C printf(%08b\n, (unsigned char)x); // C23支持之前可以用自写函数 // Python print(bin(x)) # Python 的 bin 输出带0b前缀我调试权限模块的掩码出错时就是靠着打印二进制一眼看出掩码左移了一位。别嫌打印二进制麻烦这比自己盯着十进制硬想快十倍。4.6 位运算在不同语言下的行为差异速查语言对有符号数无符号右移位宽注意事项C/C算术右移实现定义但几乎所有编译器都是对无符号类型注意类型宽度移位量不能大于等于位宽Java算术右移int固定32位long固定64位Python算术右移无专门符号无限位宽位宽无限负数补码表现与有限整数不同Go算术右移对无符号类型移位量可以是变量这里再提一个隐藏较深的坑在C/C中移位量如果大于等于左操作数的位宽属于未定义行为。比如1 32在32位int上编译器会怎么处理完全没有保证可能结果是1可能是0也可能直接崩溃。所以写代码时一定要确保移位量在安全范围。5. 一个完整的实战案例手写一个简单的权限管理模块我把前面讲的技巧组合起来给你做一个完整可运行的小模块。这个例子不是为了演示知识片段而是让你看到位运算在真实工程中如何组合使用。需求是设计一个用户权限系统包含四种权限查看、创建、编辑、删除。用户存储时用一个整数permissions来表示。现在实现几个核心操作public class PermissionUtil { public static final int VIEW 1 0; // 1 public static final int CREATE 1 1; // 2 public static final int EDIT 1 2; // 4 public static final int DELETE 1 3; // 8 // 赋予权限把对应位置1 public static int grant(int permissions, int permission) { return permissions | permission; } // 撤销权限把对应位清0 public static int revoke(int permissions, int permission) { return permissions ~permission; } // 检查是否有权限 public static boolean has(int permissions, int permission) { return (permissions permission) permission; } // 检查是否同时有多个权限 public static boolean hasAll(int permissions, int permissionSet) { return (permissions permissionSet) permissionSet; } // 计算用户拥有多少种权限 public static int countPermissions(int permissions) { int cnt 0; while (permissions ! 0) { permissions (permissions - 1); cnt; } return cnt; } public static void main(String[] args) { int perm 0; perm grant(perm, VIEW); perm grant(perm, EDIT); System.out.println(has view: has(perm, VIEW)); // true System.out.println(has delete: has(perm, DELETE)); // false perm grant(perm, DELETE); perm revoke(perm, VIEW); System.out.println(permission count: countPermissions(perm)); // 2 System.out.println(binary: Integer.toBinaryString(perm)); // 1010 } }这段代码里grant和revoke是典型的置位和清位hasAll判断一组权限是否同时满足countPermissions用了Kernighan算法统计权限个数。如果你看懂了这段代码就等于把前面学的技巧串联起来落地了一次。6. 我对位运算的实际心得体会写到这里我特别想把一些个人感受分享出来。位运算看上去像是一个一个孤立的小技巧但实际上它背后贯穿着几条核心思维二进制描述世界、用掩码操作状态、用数学性质简化问题。掌握了这些思维之后你会发现读源码时不再害怕那些“天书”一样的位运算表达式反而能从里面读出设计者的思路。我在实际工作里有一个很强烈的体会位运算的代码往往“写起来很爽改起来很痛苦”。所以我在用位运算时给自己定了几条硬规矩第一能用EnumSet或语言自带的高层集合表达开关状态就别手搓位运算除非性能真的成为瓶颈。工程上简单和可靠优先于炫技和微优化。第二如果用位运算一定要配套常量定义和注释。命名常量让语义清晰注释写清楚这个位代表什么含义。一个好的位运算代码应该做到即使你不懂位运算也能大概猜出代码在干什么。第三写完后一定要用边界值测试0、1、-1、最大值、最小值、奇数、偶数、全1、全0。这些边界值最容易触发符号位、溢出、移位量越界问题。第四除非必要不要在业务代码里做x / 2替代成x 1这种微观优化。现代编译器早就把这个优化做好了你手动写了反而降低可读性。把位运算用在高价值的地方状态压缩、权限系统、协议解析、位图存储、算法核心这才是位运算真正的舞台。最后再分享一个小技巧学习位运算最好的方式不是看书而是刷题和读源码。LeetCode上有很多位运算专题找唯一数、子集枚举、位计数各语言标准库的源码里也藏着大量位运算的应用比如HashMap的哈希扰动、扩容取模读这些代码能最快地让你理解位运算的实战价值。相信我一旦你习惯用二进制视角看待数据很多复杂的逻辑都会瞬间变得清晰起来。