位运算
位运算（Bit Manipulation）是直接对整数二进制位进行操作的运算族——把一个数看成 0/1 组成的位串，用与（&）、或（|）、非（~）、异或（^）、左移（<<）、右移（>>）这六个操作按位计算。它是计算机最底层的运算：CPU 的 ALU 本就是逐位做逻辑运算的，所以位运算天然是 O(1) 且常数极小。几乎所有语言都把它作为对整数类型的一等运算符（C/C++/Java/JS/Go/Python 的 &|^~<<>>），Python 还提供任意精度的位运算（无 32 位溢出之忧）。它既是「不引入额外数据结构、只在原数上做文章」的算法套路核心（只出现一次的数字、不用加减法求和、汉明重量），也是状态压缩 DP、位掩码权限标志、哈希与压缩编码的底层基石，地位相当于算法里的「积木」。
位运算的全部考点都源于两个事实：异或的自反性（a^a=0、a^0=a）⇒ 消除成对元素，以及**n & (n-1) 能去掉最低位的 1 ⇒ 操作单个 1 的位置**。由此衍生出三大主题：①基础六运算与异或性质（补码表示、移位的乘除含义、异或的消去与交换）；②常用位运算技巧（判断奇偶、不用临时变量交换、n&(n-1) 去 1、n&(-n) 取 lowbit、判断 2 的幂、取/设/清/翻某位）；③经典应用与位掩码（只出现一次的数字、不用加减法求和、汉明重量与距离、状态压缩 DP、权限标志位）。其中异或是「在成对元素里揪出落单者」的万能钥匙，n&(n-1) 是「在 1 的层面精耕细作」的瑞士军刀——它们本质都是利用「整数即位串」这一性质，把朴素 O(n) 的操作压到 O(1) 或 O(位数)。
评价
优点
- 常数极小、极度高效：位运算直接映射到 CPU 单条指令，无分支、无访存、可被编译器深度优化——在热路径里用位运算替代算术/条件判断常有数倍提速
- 状态压缩的天然载体：一个 32/64 位整数能装下 32/64 个布尔标志，把原本 O(n) 空间的集合压成一个数，是状态压缩 DP、权限位、布隆过滤器的底层
- 无需额外数据结构：很多「计数/查找/去重」问题（只出现一次的数字、不用加减法求和）用位运算 O(1) 空间解决，是空间优化的极致
- 异或的对称性：
a^a=0这一性质让异或成为「成对抵消」的代数工具，加解密、纠错码、找单元素都依赖它
缺点
- 可读性差：
n&(n-1)、a^=b;b^=a;a^=b这类写法对不熟悉位运算的人形如天书，团队代码里滥用会损害可维护性——能用普通写法讲清楚时不应炫技 - 平台与语言差异：JS 的位运算是 32 位有符号（
~5 === -6，大数被截断到 32 位）；Python 是任意精度（无溢出）；右移在 Java/C++ 对负数是「算术右移」（补符号位）而某些场景需注意——跨语言移植易踩坑 - 运算优先级反直觉：
&的优先级低于比较运算符（==/<），n & 1 == 0实际是n & (1==0)=n & false——这是最高频的位运算 bug，必须加括号 - 只在「位层面」有效：位运算优化的是常数和空间，不改变大 O（把 O(n) 变 O(n/log) 的是数学，不是位运算）；且现代编译器常自动做这类优化，手写不一定更快
本叶地图
- 入门 —— 六种位运算（与或非异或移位）、异或的自反性、移位的乘除含义、补码与负数表示
- 常用位运算技巧 —— 判断奇偶、不用临时变量交换、
n&(n-1)去最低位 1、lowbit、判断 2 的幂、取/设/清/翻某位 - 经典应用与位掩码 —— 只出现一次的数字、不用加减法求和、汉明重量、状态压缩 DP、权限标志位
- 参考 —— 六运算速查表、技巧清单表、经典题代码、易错点（优先级/符号位/溢出/JS 32 位）
交互演示
位运算无专门交互演示，建议结合快速幂理解位运算的应用——快速幂正是用「把指数按二进制拆位 + 逐位判断」把 O(n) 的幂运算降到 O(log n)，是位运算思想最优雅的体现。