一、二进制与补码：位运算的物理基础
要真正理解位运算，必须先回到计算机如何存储整数这个问题上。计算机内部一切数据都以二进制的 0 和 1 存储，整数的位运算就是直接对这些比特位进行操作，因此它贴近硬件、执行极快，是许多高效算法的根基。
对于有符号整数，计算机采用补码表示法。正数的补码与其原码相同，而负数的补码通过对原码"符号位不变、数值位按位取反、末位加一"得到。这条规则带来一个极其重要的恒等式：一个数 x 的相反数，等于它的按位取反再加一，即负 x 等于取反 x 再加一。这个等式是位运算中最常被调用的性质之一，后面会看到，"取最低位的 1"这一核心技巧就完全建立在该等式之上。
补码的设计并非偶然。它让加减法可以统一用一套加法器电路实现，让 0 的表示唯一（不存在正零与负零之分），还让负数向右移位时能够自动进行符号扩展。理解了补码，才能理解为什么对一个正整数按位取反会得到一个负数，为什么对负数右移时高位补的是 1 而不是 0。
移位运算同样需要分清两种语义。左移整体向左挪动，右边补 0，每左移一位相当于乘以 2。右移则分为算术右移与逻辑右移：算术右移时高位以符号位填充，即正数补 0、负数补 1，相当于对整数做除以 2 向下取整；逻辑右移则无论符号位如何，高位一律补 0，主要用于无符号数。在不少语言里，对有符号负数做右移的结果依赖于编译器实现，这是跨平台代码中必须警惕的一个点。
二、六大基本运算符的语义
位运算的核心只有六种操作，但它们组合起来能产生极其丰富的语义。
按位与的规则是两位都为 1 结果才为 1，常被理解为"有 0 出 0，全 1 才 1"。它的典型用途是屏蔽位，即用一个掩码把目标数据的某些位提取出来、把另一些位清零。例如，把一个整数和 1 做按位与，由于 1 的高位全是 0，结果只保留最低位，这正是判断奇偶性的本质依据。
按位或的规则是只要有一个 1 结果就为 1，即"有 1 出 1，全 0 才 0"。它用于设置特定位，把一个数的某一位或某几位置成 1 而不影响其他位。权限系统中"叠加多种权限"就是用按位或完成的。
按位异或的规则是相同为 0、相异为 1，可以理解为"无进位加法"。它拥有三条黄金定律：任何数与 0 异或等于其本身、任何数与自身异或等于 0、满足交换律和结合律。这三条性质是后续大量算法的支点，从找单身数字到不用临时变量交换两数，再到简单的对称加密，都依赖它们。
按位取反把 0 变 1、1 变 0，是一元运算符。它与按位与配合可以实现"清除特定位"的操作，也单独用于构造全 1 掩码。左移和右移前文已述，分别对应乘以和除以 2 的幂。
需要特别强调的是，位运算符的优先级普遍低于算术运算符和比较运算符，这是一个让无数工程师踩过坑的细节。当位运算与加法、比较、逻辑运算混用时，最稳妥的做法是无脑加括号，宁可写得更啰嗦，也不要依赖对优先级的记忆。
三、常用位运算技巧
判断奇偶
一个整数的奇偶性完全由其最低位决定：最低位是 1 则为奇数，是 0 则为偶数。因此，将待判断的数与 1 做按位与，结果为 1 即奇数，为 0 即偶数。这种写法比取模运算更快，因为它对应的是单条机器指令，而取模往往涉及除法运算。无论正数还是负数，由于补码的性质保证最低位在取反加一过程中保持一致，这一判断都成立。
统计二进制中 1 的个数
这是一道面试高频题，也是理解"消除最低位 1"这一技巧的最佳入口。核心操作是：让 n 与 n 减一做按位与，结果会把 n 二进制表示中最右侧的 1 变成 0，而其他位不受影响。原因是，n 减一会让最低位的 1 借位变为 0，其后所有位都变成 1，与原数按位与后这些位全部归零。于是，反复执行这一操作直到 n 变为 0，执行次数就是 1 的个数，时间复杂度与 1 的数量成正比，而非与位数成正比。
与此相关的是另一个常用技巧 lowbit，即取出一个数二进制最右侧的 1。它的实现是 n 与负 n 做按位与。其原理正是前文提到的取反加一：负 n 的二进制相当于把 n 按位取反再加一，在这个过程中，n 最右侧的 1 及其右侧的 0 会保持不变，而其左侧所有位都被取反，因此按位与后只有最右侧的 1 被保留。lowbit 是树状数组等数据结构的基石。
不用临时变量交换两数
借助异或的自反律和交换律，可以在不引入第三个变量的前提下交换两个整数。第一步，让第一个数异或第二个数；第二步，让第二个数异或新的第一个数，由于代入后第二个数变成了原第一个数；第三步，让新的第一个数异或新的第二个数，结果变成原第二个数。整个过程没有借助任何额外存储，仅靠三次异或完成交换。需要注意的是，这种写法在两个变量指向同一内存地址时会把自己清零，因此实际工程中未必优于引入临时变量的朴素写法，但它对理解异或性质极有价值。
判断 2 的幂
2 的非负整数次幂在二进制表示中只有一个 1，例如 1、2、4、8 分别是 1、10、100、1000。因此，一个正整数 n 是 2 的幂，当且仅当 n 大于 0 且 n 与 n 减一的结果为 0。因为 n 减一会把那个唯一的 1 变成 0、其后的所有位变成 1，与原数按位与必然为 0。基于 lowbit 也能给出等价判断：2 的幂当且仅当 n 与负 n 相等，因为它的最右侧的 1 就是它唯一的 1。这一技巧可以把原本需要循环的对数级判断降到常数级。
不用加减乘除做加法
这是面试中常见的位运算综合题。两个二进制数相加，不考虑进位时就是按位异或，而进位部分可以用按位与再左移一位得到。把这两部分相加，又回到同样的问题，于是循环执行，直到进位为 0。整个过程把加法拆解为异或与按位与的组合，从硬件角度看，这正是全加器电路的工作原理。减法可以通过"减去一个数等于加上它的相反数"转化为加法，乘除法也都能在此基础上进一步拆解，体现了计算机底层用位运算实现算术运算的设计哲学。
四、经典算法实战
只出现一次的数字系列
这是一个把异或性质用到极致的经典系列。第一题是：给定一个非空整数数组，除某个元素只出现一次外，其余每个元素均出现两次，找出那个只出现一次的元素。哈希表计数能解决，但需要线性额外空间。最优解是让所有元素依次异或：由于任何数与自身异或为 0、任何数与 0 异或为自身、且异或满足交换律和结合律，所有成对出现的数会两两抵消为 0，最后剩下的就是那个只出现一次的数。这一解法时间复杂度线性、空间复杂度常数。
第二题是其余元素均出现三次的情形。此时异或的"消消乐"失效，因为异或只能处理偶数次出现。解法转为"逐位统计"：对整数的 32 个比特位分别统计该位上 1 的总个数，若某个数出现三次，它贡献的 1 在每一位上要么是 0、要么是 3 的倍数；只出现一次的那个数，其某一位的 1 会让该位的统计结果对 3 取余为 1。把所有对 3 取余为 1 的位组合起来，就是答案。这一思路可以推广到"其余元素均出现 k 次，找出只出现一次的元素"，只需把取余的基数换成 k 即可。
第三题是数组中有两个只出现一次的数，其余都出现两次。先把所有数异或起来，结果是这两个数的异或值，其中至少有一位是 1，因为这两个数不同。找出该异或结果中任意一个为 1 的位，这一位说明两个目标数在该位上不同。以此为分组依据，把原数组按该位是 0 还是 1 分成两组，两个目标数必然分属不同组，而其他成对出现的数一定在同一组。对每一组分别做整体异或，就分别得到两个目标数。lowbit 在这里又一次派上用场，因为它能高效地取出异或结果中最右侧的 1 作为分组依据。
丢失的数字
给定一个包含 0 到 n 的 n 个数的数组，找出缺失的那个数。可以用高斯求和公式减去数组之和，但位运算同样优雅：让一个初始值先异或数组中所有元素，再异或 0 到 n 的所有整数，存在的数字被异或两次抵消为 0，只有缺失的数字被异或了一次，最终结果就是它。这本质上是"只出现一次的数字"的变体，再次体现了异或"消消乐"思想的普适性。
N 皇后问题的位运算优化
N 皇后问题要求在 N 乘 N 的棋盘上放置 N 个皇后，使其互不攻击。传统回溯用数组记录每行皇后所在列，逐行尝试并用一个校验函数判断是否冲突，时间复杂度呈指数级。位运算优化的核心是：用一个整数的各个比特分别表示某一列、某一条主对角线、某一条副对角线是否已被占用，于是冲突检测从"遍历历史数组"变成了"一次按位与"。
具体地，用三个整数分别记录列、主对角线、副对角线的占用情况。在每一行，把三者按位或得到"被禁止放置"的位集合，取反后与棋盘位宽掩码做按位与，就得到所有"可放置"的列。然后利用 lowbit 不断取出最右侧的可放置位置进行递归尝试。递归到下一行时，列掩码直接按位或上新放置的位，主对角线掩码左移一位、副对角线掩码右移一位，这对应了皇后攻击斜线在下一行的偏移。这种写法把冲突检测和状态更新都压缩为整数运算，常数因子极小，可以在极短时间内求解 14 皇后甚至 16 皇后问题。它的精髓不在于改变了回溯的本质，而在于把每个判断的代价从线性降到常数。
快速幂
快速幂要解决的问题是：求 a 的 b 次幂，朴素算法需要连乘 b 次，复杂度是线性的，而快速幂利用指数的二进制拆分，把复杂度压到对数级。其核心思想是：把指数 b 写成二进制形式，比如 13 的二进制是 1101，于是 a 的 13 次方等于 a 的 8 次方乘以 a 的 4 次方乘以 a 的 1 次方，因为 13 等于 8 加 4 加 1。
实现上，每次循环检查指数 b 的最低位：若为 1，就把当前底数累乘到结果中；无论是否为 1，都让底数自乘平方，对应二进制下一位的权值翻倍；然后让指数右移一位，处理下一位。整个过程只用了按位与判断最低位、右移一位、乘法三种操作，把原来需要一百万次的乘法压缩到大约二十次。在需要取模的场景下，只需在每次乘法后取模即可防止溢出，这几乎是所有数论题的标准操作。快速幂还能推广到矩阵快速幂，用于加速线性递推式，例如用对数级时间求斐波那契数列的第 n 项，是算法工程中的常用利器。
五、工程应用场景
权限系统的位掩码
在系统级编程中，位掩码是一种用单个整数的不同比特位表示多个开关、状态或权限的技术。其基本操作可以归纳为四类：用按位或设置某一位为 1、用按位与配合取反清除某一位为 0、用按位与检测某一位是否为 1、用按位异或翻转某一位。
在权限控制中，把读、写、执行分别定义为 1 左移 0 位、1 左移 1 位、1 左移 2 位，即数值 1、2、4。一个用户的权限组合就是这些值按位或的结果：读加写等于 3，读加执行等于 5，全部权限等于 7。要判断是否拥有某种权限，只需把用户权限与该权限的掩码做按位与，结果非 0 即拥有；要追加权限，用按位或；要移除权限，用按位与配合取反；要切换权限，用按位异或。整个权限集合被压缩进一个整数，存储空间从多个布尔字段缩减到几个字节，检查速度也因为单次位运算而极快，这种设计在很多操作系统的文件权限模型中得到印证。
位掩码的另一个工程价值是它天然支持集合运算。两个权限集合的并集就是按位或，交集是按位与，差集是按位与配合取反，对称差是按位异或。这意味着复杂的权限计算可以在不引入额外数据结构的前提下完成，在性能敏感的关键路径上优势明显。
状态压缩动态规划
当动态规划的状态本身是一个集合时，比如"已经访问过哪些城市"、"已经选取了哪些物品"，如果用数组或哈希表表示集合，空间和常数都难以承受。状态压缩的核心思想是用一个整数的各个比特位表示集合中每个元素是否被选中，于是集合的状态被压缩成一个整数。
旅行商问题是状态压缩动态规划的经典应用。用二进制掩码表示已访问城市的集合，第 i 位为 1 表示第 i 个城市已访问，状态转移时把当前城市加入集合只需按位或上对应位的掩码。由于整数能表示的状态数为 2 的 n 次方，这种方法适合 n 较小的场景，通常 n 不超过 20 比较稳妥，因为状态总数随 n 指数增长。
在子集枚举中，位运算同样大放异彩。给定一个掩码 m，要遍历它的所有非空子集，可以用一个巧妙的迭代式：让 s 从 m 开始，每次让 s 减一再与 m 做按位与，直到 s 变为 0。这一写法能够按降序枚举 m 的所有非空子集，且跳过了所有不属于 m 的位，效率远高于暴力枚举所有小于 2 的 n 次方的整数再判断是否为子集。在容斥原理、子集卷积等问题中，这是不可或缺的工程化手段。
状态压缩还能配合滚动数组进一步优化空间。当状态转移只依赖上一层的若干状态时，可以只保留必要的两层状态数组，把空间复杂度从状态总数降为常数。这种"二进制压缩加滚动数组"的组合是工程上处理中小规模状态空间问题的标准方案。
布隆过滤器与位图
位图是用一个比特位表示一个元素是否存在的数据结构，n 个元素只需 n 个比特存储，空间效率远高于用整数数组或哈希集合。在大规模数据的存在性判断中，位图几乎是唯一可行的选择。布隆过滤器在位图基础上引入多个哈希函数，用 k 个比特位的按位与来判断元素是否存在，能够在可接受误判率的前提下把空间占用压到极低。虽然这里不展开其实现细节，但其底层完全是位运算的按位或与按位与。
颜色通道与子网掩码
在图像处理中，一个像素常被编码为一个 32 位整数，其中每 8 位分别表示红、绿、蓝、透明度四个通道。要提取某一通道，只需把像素值右移到最低 8 位再与 0xFF 做按位与；要合并通道，用按位或把各通道放到对应位置即可。这种处理避免了拆解成结构体的开销，在图像编解码的 hot path 上非常常见。
在网络通信中，子网掩码通过按位与运算划分 IP 地址的网络位与主机位，掩码中连续的 1 标识网络部分、0 标识主机部分，是路由转发的基础。这些场景的共同点是：把多个语义相关的数值压进一个整数，再用位运算快速拆装，既节省存储又加速运算。
六、位运算的误区与最佳实践
位运算虽强，但用得不当会埋下隐蔽的 bug。第一个陷阱是运算符优先级。比较运算符的优先级高于按位与，因此判断第 0 位是否为 1 时，不加括号的写法会被解析为先判断等于再按位与，导致逻辑错误。类似地，左移右移的优先级低于加减法，中点取值时若不加括号，等价于把整个表达式右移一位，会造成死循环。最稳妥的做法是：只要位运算与加法、比较、逻辑运算混用，就一律加括号。
第二个陷阱是有符号数的右移。对负数做右移时，算术右移会让高位补 1，逻辑右移让高位补 0，不同语言和编译器的实现可能不同。如果代码需要跨平台一致的行为，应尽量对无符号数做移位操作。第三个陷阱是移位数量的边界：移位位数不能大于或等于数据类型的位宽，否则属于未定义行为；左移时若移出有效位尤其是符号位，也会导致溢出或数据错误。
第四个陷阱是位运算符与逻辑运算符的混淆。按位与和逻辑与、按位或和逻辑或，在功能上完全不同，前者作用在每一位上结果可能是任意整数，后者作用在布尔值上结果只能是 0 或 1。在条件判断中误用按位与代替逻辑与，可能会让一个非 0 非 1 的值被当作真值，引入难以察觉的逻辑错误。
第五个陷阱是可读性。位运算天然晦涩，一段纯位运算的代码对没有相关背景的同事而言近乎天书。因此，在生产代码中使用位运算时，应当配合有意义的常量命名和充分的注释，把"这一步在做什么"说清楚，而不是把"这一步怎么做"留给读者去推演。一个可读性差的位运算实现，即便快了几个时钟周期，也可能在后续维护中付出数倍的代价。
七、性能边界与适用判断
位运算并非万能。在普通业务代码中，编译器已经能够把简单的乘除 2 优化为移位指令，手写位运算带来的收益往往微乎其微，却牺牲了可读性。因此，是否使用位运算应基于场景判断：当处于性能敏感的关键路径、当需要紧凑表示集合或状态、当需要直接操控硬件寄存器、当面试或算法竞赛中需要把时间常数压到最低时，位运算是不二之选；而在普通业务逻辑中，清晰的算术运算和结构化的数据表达往往更值得优先。
一个值得记住的经验法则是：看到"重复、消失、只出现一次"这类关键词就联想到异或，看到"统计 1、判断 2 的幂"就联想到按位与减一，看到"二进制翻转、逐位处理"就联想到移位加取位，看到"集合状态、子集枚举"就联想到位掩码。这种从问题特征到工具的映射，比死记硬背几十道位运算题更有价值，它能在新问题面前快速激活正确的思路。
结语
位运算的魅力在于它把高级语言的多层抽象一刀切开，让我们直接看到数据在硬件中的真实形态。从补码这一最底层的表示规则，到异或、按位与这些基本运算，再到只出现一次的数字、快速幂、N 皇后等经典算法，最后到权限系统、状态压缩动态规划等工程实践，位运算构成了一条自洽而完整的技术脉络。掌握它，不仅意味着在面试和竞赛中多了几件趁手的兵器，更意味着在遇到性能瓶颈、存储压力、状态空间爆炸等工程难题时，能够想到"也许可以把问题压到一个整数的比特位里去解决"。这种把问题映射到二进制层面再加以操纵的思维方式，才是位运算真正教会开发工程师的东西。
