位运算

1 基本概念

位运算是以二进制位为最小处理单位的一类运算。与按十进制位进行书写不同，计算机内部更适合直接处理由 0 和 1 组成的位序列，因此位运算在底层表示、逻辑判断和高效计算中占有重要位置。

1.1 位与二进制表示

在数字计算中，整数通常先被表示为二进制形式，再参与后续运算。二进制的每一位只能取 0 或 1，分别表示不同的权值。多个二进制位组合起来，就形成了一个数的位级表示。

位不仅用于表示数值，也可用来表达状态、开关、权限、标志等信息。由于每一位都具有明确的独立含义，位级表示在空间利用和快速判断方面具有较高效率。

1.2 位运算的定义

位运算是指对两个位序列的对应位逐位进行逻辑处理，或对单个位序列进行位级变换。常见操作包括按位与、按位或、按位异或、按位非以及移位运算。

例如，两个二进制数做按位与时，只有对应位都为 1，结果位才为 1；其余情况结果为 0。类似地，其他位运算也都遵循逐位处理的原则，只是规则各不相同。

1.3 位运算与逻辑运算的区别

位运算处理的是数值在二进制层面的每一位，而逻辑运算通常处理的是“真”与“假”这类布尔值。二者表面上都与逻辑有关，但应用场景并不完全相同。

在许多编程语言中，逻辑运算具有短路特性，即一侧结果已足够确定整体结果时，另一侧不会继续求值；位运算则通常会完整计算两侧的对应位。前者更适合条件判断，后者更适合位级组合与掩码操作。

1.4 位宽与补码表示

位宽指一个数据类型可容纳的二进制位数，例如 8 位、16 位、32 位或 64 位。位宽决定了可表示数值的范围，也影响溢出行为和移位结果。

在现代计算机中，带符号整数常采用补码表示。补码使加减法运算在硬件层面更统一，也让零只有一种表示形式。对于负数而言，补码结构与最高位的符号含义密切相关，这也是理解位运算时必须掌握的基础。

2 基本运算符

位运算的基本运算符构成了位级处理的核心工具。它们各自对应不同的逻辑关系，常被用于掩码、标志控制和高效数值变换。

2.1 按位与

按位与通常用符号 & 表示，是最常见的位运算之一。

2.1.1 运算规则

按位与对两个操作数的每一对应位进行比较，只有两位都为 1 时，结果位才为 1。若任一位为 0，结果位即为 0。

这一规则使按位与常用于“筛选”某些位，也可用于清除不需要的位。

2.1.2 典型用途

按位与常见用途包括判断某一位是否为 1、提取特定位、清除标志位以及进行掩码处理。例如，将某个数与掩码相与，可以保留掩码对应的位，其余位置被置零。

在范围判断中，按位与也可用于检查偶数性，因为二进制最低位为 0 时，该数通常为偶数。

2.2 按位或

按位或通常用符号 `	` 表示。

2.2.1 运算规则

按位或对两个操作数的对应位进行比较，只要其中一位为 1，结果位就为 1；只有两位都为 0，结果位才为 0。

这种“只要有一个成立就成立”的特点，使按位或在合并标志和设置位时十分方便。

2.2.2 典型用途

按位或常用于开启某一标志位、合并状态集和构造掩码。若某一位原本是 0，与含有对应 1 位的掩码进行按位或后，该位会被设置为 1，而不会影响其他已为 1 的位。

因此，它非常适合做权限累积、状态叠加和配置组合。

2.3 按位异或

按位异或通常用符号 ^ 表示。

2.3.1 运算规则

按位异或对对应位进行比较，当两位不同的时候结果为 1，相同则为 0。也就是说，0 与 0、1 与 1 的结果都是 0，而 0 与 1、1 与 0 的结果都是 1。

异或具有明显的“差异检测”特征，因此在处理互斥条件和差分信息时很有用。

2.3.2 典型用途

按位异或常用于翻转指定位、交换变量、查找唯一元素以及处理成对抵消问题。若将一个值与同一个数异或两次，结果会回到原值，这种性质使它在某些算法中非常实用。

此外，异或也常用于简单校验与数据混淆，尽管在安全场景中并不构成强加密手段。

2.4 按位非

按位非通常用符号 ~ 表示。

2.4.1 运算规则

按位非会将操作数的每一位取反：0 变成 1，1 变成 0。它是单目运算，只作用于一个操作数。

由于结果会与位宽和补码表示相关，按位非在不同类型上的具体数值含义需要结合数据类型理解。

2.4.2 典型用途

按位非常用于生成全 1 掩码、翻转位模式以及与其他位运算组合使用。在实际编程中，它经常与按位与配合，用来清除某些位；也可与异或结合，形成更复杂的位变换。

2.5 左移与右移

移位运算是把位序列按指定方向平移若干位的操作，通常用 << 和 >> 表示。

2.5.1 逻辑移位

逻辑移位会在移入空位时补 0，移出范围的位则被丢弃。逻辑左移相当于整体向高位方向移动，逻辑右移则向低位方向移动。

对于无符号数，逻辑右移通常更直观；对于某些语言中的有符号数，右移是否补 0 取决于语言和实现。

2.5.2 算术移位

算术移位主要用于有符号整数。算术右移通常保留符号位，即高位补入原符号位的值，从而尽量维持数值的正负属性。算术左移在很多环境中与逻辑左移相同，但需要注意溢出风险。

由于不同平台和语言对有符号右移的定义可能不完全一致，编写底层代码时需要特别谨慎。

2.5.3 循环移位

循环移位是将移出的位重新接回另一端，形成“首尾相接”的效果。它常见于密码学、校验和以及某些位混洗算法中。

与普通移位相比，循环移位不会丢失位信息，因此更适合需要保留完整位模式的场景。

3 数学性质

位运算不仅是工程工具，也具有清晰的代数性质。这些性质使其便于分析、推导和优化。

3.1 交换律、结合律与分配律

按位与、按位或、按位异或通常都满足交换律和结合律，即操作顺序在一定范围内可以调整而不改变结果。部分运算之间还存在分配关系，便于将复杂表达式拆解为更简单的形式。

这些性质在化简位表达式、构造掩码以及设计无分支算法时很有价值。

3.2 幂等性与自反性

按位或与按位与分别具有典型的幂等特征：一个值与自身按位或，结果仍为自身；一个值与自身按位与，结果也仍为自身。异或则有自反性，即一个值与自身异或结果为 0。

这些性质常被用于去重、抵消和构造中间状态。

3.3 德摩根定律

德摩根定律描述了按位非与按位与、按位或之间的对应关系。它表明，对一个按位与结果取反，等价于分别取反后再做按位或；对一个按位或结果取反，则等价于分别取反后再做按位与。

这一规律在逻辑表达式变换和掩码设计中十分实用。

3.4 异或的特殊性质

异或具有若干独特性质，例如交换顺序不影响结果、同一个数异或两次会抵消为 0、与 0 异或保持原值等。由于这些性质非常稳定，异或常被用于构造“可逆”的位级操作。

它还能实现简单的对称处理，使某些数据在两次相同操作后恢复原状。

4 编码与表示

位运算的效果与数据的编码方式密切相关。理解二进制、补码和浮点结构，有助于准确解释运算结果。

4.1 二进制、十六进制与位序

二进制是位运算的直接基础，而十六进制常被用作二进制的紧凑书写方式。每个十六进制位对应 4 个二进制位，因此在调试和低级表示中很常见。

位序则涉及位在表示中的排列顺序。不同系统和文档可能采用不同的编号习惯，因此阅读位图、协议字段或寄存器说明时，需要确认位的起始方向与编号规则。

4.2 负数的补码表示

补码是有符号整数最常见的表示方法。它通过对原码按位取反再加 1 的方式构造，使加法电路可以统一处理正数和负数。

在补码体系下，最高位通常与符号相关，但其本质仍是数值位的一部分。负数参与位运算时，结果会受到补码结构影响，因此不能仅凭直觉按“数学负号”理解。

4.3 有符号与无符号整数

有符号整数用于表示正负数，无符号整数则只表示非负数。两者位宽相同，但可表示范围不同。

在位运算中，无符号数通常更适合纯位模式处理，因为其右移、比较和溢出特性更容易预测。有符号数则更适合数值计算，但在高位处理和符号扩展方面更需要注意语义差异。

4.4 浮点数的位级结构

浮点数通常由符号位、指数位和尾数位组成。其内部结构决定了可表示范围和精度，也使其能够借助位运算进行某些特殊处理。

不过，浮点数并不适合像整数那样直接进行一般位级推导。由于其编码遵循专门格式，直接操作位模式往往只适用于特定算法或底层实现。

5 常见技巧

位运算之所以在编程中广受欢迎，很大程度上来自一系列简洁而高效的技巧。这些方法常用于竞赛、面试和系统编程。

5.1 判定奇偶性

判断一个整数是否为偶数，常可直接检查最低位。若最低位为 0，则该数通常为偶数；若最低位为 1，则通常为奇数。

这种方法比取模运算更接近硬件层面的表示，也常被视为典型的位运算入门技巧。

5.2 清除、设置与翻转指定位

清除某一位通常使用按位与配合取反掩码；设置某一位常用按位或；翻转某一位则多用异或。通过构造不同掩码，可以对目标位进行精确控制。

这类操作适合处理状态标志、权限位和压缩字段，逻辑清晰且效率较高。

5.3 取最低位 1 与二进制拆分

一个数与其相反数按位与，常可得到其二进制表示中最低位的 1。这个结果可帮助快速分离出最右侧的有效位。

基于这一技巧，可以进一步进行二进制拆分、分组统计或构造子问题，从而简化某些算法流程。

5.4 统计二进制中 1 的个数

统计一个数的二进制表示中有多少个 1，是常见的位操作任务。方法包括逐位检查、不断清除最低位 1，或借助专门的硬件指令与库函数。

这个问题在图像处理、哈希分析、编码校验和某些数据结构中都很常见。

5.5 子集枚举与状态压缩

当一个集合元素数量较少时，可以用一个整数的各个位表示元素是否选中。这样一来，子集就能对应到二进制状态，枚举过程也可通过位运算完成。

状态压缩不仅节省空间，还能让动态规划和搜索在状态管理上更加紧凑，是组合优化中的重要手段。

6 算法应用

位运算不仅是技巧集合，更是许多算法设计的基础工具。它能提升表达效率，也能在性能上带来明显收益。

6.1 位掩码与集合表示

位掩码是一种使用二进制位表示集合成员关系的方法。某一位为 1，通常表示对应元素存在；为 0，则表示不存在。

这种表示法特别适合小规模集合、权限系统和需要频繁增删查操作的场景。由于可直接通过位操作完成合并、交集和差集，计算过程往往比一般容器更紧凑。

6.2 位运算优化

在某些场景中，位运算可以替代除法、取模、乘法或条件判断，从而提升运行效率。例如，使用移位代替乘除以 2 的幂，使用掩码代替部分取模操作，都是常见的优化思路。

不过，优化并不意味着所有情况下都应优先使用位运算。代码可读性、可维护性和语言语义同样需要考虑。

6.3 图论与动态规划中的状态压缩

在图论和动态规划中，位压缩常用于表示访问集合、路径状态或选择方案。尤其在节点数量不大但状态组合很多时，位表示可以显著减少状态管理成本。

例如，旅行类问题、集合覆盖类问题和某些路径计数问题，都经常借助位运算来组织状态转移。

6.4 哈希、加密与校验中的位处理

位运算在哈希函数、校验码和某些加密算法中经常出现。原因在于位级变换可以快速打散模式、增强混合效果，并保持操作的确定性与可逆性。

很多数据处理流程都会利用异或、移位和掩码来完成中间混合，但这并不等同于真正的高强度安全机制。

6.5 进制转换与高效计算

位运算可以帮助理解和实现二进制、十进制、十六进制之间的转换。由于 2 的幂次与位移动直接相关，因此在某些进制场景中可通过移位和掩码高效完成处理。

在高性能计算中，这种特性常被用于编码、压缩和数据拆包。

7 硬件与体系结构

位运算与计算机硬件之间存在天然联系。其逻辑基础直接映射到电路实现，也影响处理器的设计方式。

7.1 逻辑门与布尔代数

位运算本质上可以由逻辑门实现，例如与门、或门、非门和异或门。布尔代数为这些门提供了数学表达形式，也为组合逻辑电路设计奠定了基础。

因此，位运算不仅是编程概念，也是数字电路中的核心操作语言。

7.2 CPU 指令中的位操作

现代处理器通常提供专门的位操作指令，用于移位、测试、置位、清位和位扫描等任务。与高级语言中的抽象表达相比，底层指令更贴近硬件执行流程。

这些指令在性能敏感场景中很有价值，尤其适合实现循环控制、标志处理和快速查表。

7.3 寄存器、标志位与位域

寄存器是 CPU 内部存储数据的高速单元，而标志位则用于记录运算结果的特征，如进位、零、符号等。位域则是在结构体或存储单元中划分若干位段，以表示多个紧凑字段。

这些设计都体现了“用少量位承载更多语义”的思想，也正是位运算大显身手的地方。

7.4 并行计算中的位级操作

在并行计算和向量化处理中，位级操作可帮助同时处理大量二进制信息。例如，位图扫描、批量掩码与并行标志判断，都可在一定程度上减少分支和单次操作成本。

在某些数据密集型应用中，这类技术能有效提升吞吐量。

8 编程语言支持

不同编程语言对位运算的支持方式略有差异，但核心思想基本一致。理解语言细节，有助于避免移位和类型转换中的错误。

8.1 常见语言中的位运算符

大多数主流语言都支持按位与、按位或、按位异或、按位非以及移位运算符。具体符号通常相对统一，但某些语言还提供复合赋值形式，如 &=、`	=、^=、<<= 和 >>=`。

此外，一些语言还提供更高级的位集合接口或标准库函数，方便开发者进行批量处理。

8.2 运算优先级与结合性

位运算在表达式中具有特定优先级。若不加括号，可能会因优先级规则导致计算顺序与预期不同。尤其在混合了算术、比较和逻辑运算时，这一点更需要注意。

为了提高可读性和减少歧义，位表达式通常建议显式使用括号。

8.3 溢出、移位与未定义行为

位运算虽然直观，但在不同语言中并非总是完全一致。某些情况下，移位位数过大、对负数右移、或左移导致超出表示范围，可能触发未定义行为或依赖实现的结果。

因此，在编写跨平台代码时，必须关注类型宽度、符号属性和语言规范。

8.4 高级语言中的位集合类型

部分高级语言和标准库提供了专门的位集合或位数组类型，用于表示大量布尔状态。这类结构在内存占用上比逐个布尔变量更紧凑，也更适合批量位运算。

它们常用于权限表、过滤器和压缩索引等场景。

9 经典例题与模式

许多位运算题目都围绕有限模式展开，思路短小但很考验对性质的理解。

9.1 交换两个变量

利用异或可以在不借助临时变量的情况下交换两个整数。其基本思想是通过三次异或操作，使两个值在中间状态中相互“抵消”并完成交换。

不过，在现代编程实践中，这种写法更多体现技巧性，实际开发中未必比使用临时变量更清晰。

9.2 找出只出现一次的数

当数组中大多数元素成对出现时，可以利用异或的抵消性质找出只出现一次的数。因为成对元素异或后为 0，最终结果往往只剩下那个独立元素。

这一模式非常经典，常见于面试和基础算法题。

9.3 判断是否为 2 的幂

一个数是否为 2 的幂，常可通过检查其二进制表示中是否只含有一个 1 来判断。若一个正整数满足与其减 1 后按位与为 0，通常说明它是 2 的幂。

这一判断方式简洁高效，是位运算中的代表性应用之一。

9.4 计算二进制区间与

计算一段连续整数的按位与结果时，常可观察它们二进制前缀的共同部分。由于区间内数值变化会使低位不断翻转，最终保留下来的通常只有共同高位前缀。

因此，这类题目的关键往往是找出共同前缀长度，而不是逐个枚举。

9.5 位运算谜题与面试题

位运算题目中常出现一些表面简单、实则考察理解深度的问题，例如利用掩码筛选、寻找缺失元素或构造最小状态表示。它们往往需要结合二进制性质、边界条件和类型规则一起分析。

这类题目之所以常见，是因为它们能够有效区分“会写代码”和“理解底层表示”的能力差异。

10 历史与发展

位运算的发展与计算机科学、逻辑学和硬件工程密切相关。它从抽象数学逐步进入工程实践，并在现代软件与硬件中长期保留其基础地位。

10.1 布尔代数的形成

位运算的理论根源可追溯到布尔代数。布尔代数将逻辑关系形式化，为后来数字电路和计算机逻辑设计提供了数学基础。

这一理论使“真与假”的逻辑操作能够被严格描述，也为按位与、按位或和按位非等概念提供了系统框架。

10.2 计算机早期的位级处理

早期计算机受硬件条件限制，常需直接处理位级数据。由于存储和运算资源都较为有限，位运算成为高效实现逻辑控制与数值处理的重要手段。

在这种背景下，位操作不仅是优化工具，更是底层编程的基本语言。

10.3 位运算在现代编程中的演进

随着编程语言和硬件能力不断发展，位运算的地位从“底层必需”逐渐扩展为“高效工具”和“算法技巧”。它依然广泛存在于系统编程、图形处理、压缩编码和性能敏感场景中。

与此同时，现代语言更强调可读性与抽象层次，因此位运算也更多作为必要时的精准手段，而非默认写法。