1. 从一道“简单”的SQL题说起那天在刷Leetcode碰到了第620题“有趣的电影”。题目要求从cinema表里找出所有“有趣的”电影条件很简单description不是‘boring’并且rating是奇数。对于任何有SQL基础的朋友来说这题几乎就是送分题一个WHERE子句配合取模运算rating % 2 1就能搞定。我也确实这么做了提交通过一气呵成。但就在我准备关掉页面手指已经悬在鼠标上时我瞥了一眼讨论区。一个高赞的解法让我停了下来。他没有用取模而是用了一个我几乎没在SQL里用过的操作rating 1。就是这一个“”符号像一颗小石子投进了平静的湖面。我的第一反应是疑惑SQL里还能用位运算紧接着是好奇rating 1为什么能判断奇偶性最后一种久违的、面对未知技术细节的兴奋感涌了上来。这道被标记为“简单”的题目突然向我打开了一扇通往计算机底层运算逻辑的小窗。我们每天都在写高级语言用着各种封装好的库和框架很多时候已经习惯了“黑盒”操作。我们知道% 2能判断奇偶就像知道按开关灯会亮一样自然却很少去追问开关背后的电路是怎么工作的。这个符号这个“按位与”运算就是电路板上的一个基础门电路。这次偶然的发现促使我决定停下来不再仅仅追求解题数量而是钻进去把这个看似简单的“与运算”彻底搞明白。我发现理解它不仅能让我们写出更底层、有时更高效的代码更能帮助我们建立起对数据在计算机中如何存储、如何被操作的系统性认知。这篇文章就是这次探索旅程的记录适合所有对代码背后世界感兴趣的朋友无论你是正在刷题的学生还是希望夯实基础的开发者。2. 核心探秘按位与运算到底在做什么要理解rating 1我们必须先抛开高级语言回到最原始的二进制世界。计算机存储和处理的所有数据最终都是一串0和1。整数也不例外。比如数字5在计算机中用8位二进制表示是00000101数字6是00000110。按位与运算顾名思义就是按二进制位进行“与”逻辑操作。它的规则极其简单只有一条两个位都为1时结果才为1否则结果为0。我们可以把它想象成一道非常严格的双重安检门两位安检员两个操作数的对应位都必须点头值为1你结果位才能通过结果为1任何一位摇头值为0你就被拦下了。我们用真值表来直观展示这个逻辑位 A位 BA B (结果)000010100111现在让我们把数字5 (00000101) 和数字1 (00000001) 拿来做按位与运算。注意为了对齐位数我们通常会将位数少的数在高位补0。5 的二进制: 00000101 1 的二进制: 00000001 按位与操作: --------- 00000001我们从上到下逐位应用“与”规则第1位最右边1 1 1第2位0 0 0第3位1 0 0... 其他高位都是0 0 0所以5 1的结果就是00000001也就是十进制数字1。同理我们看看偶数6 (00000110) 1 (00000001) 的结果6 的二进制: 00000110 1 的二进制: 00000001 按位与操作: --------- 00000000最右边第一位是 0 1 0所以结果是0。看到这里你应该已经发现了规律任何一个整数与1进行按位与运算其结果只取决于这个整数二进制表示的最低位最右边那一位。因为1的二进制形式是...0001只有最低位是1其他高位都是0。根据“与”运算规则任何位与0相与结果都是0。所以整个运算的结果实际上被“屏蔽”得只剩下最低位与1的运算结果。如果原数最低位是1奇数结果就是1如果最低位是0偶数结果就是0。注意这里有一个非常重要的前提我们默认处理的是正整数或非负整数。对于负数的二进制表示通常使用补码情况会复杂一些 1的行为可能因语言和具体实现而异。在大多数场景尤其是像Leetcode这道题明确rating为整数且通常为正的上下文里我们可以安全地使用这个技巧。但在生产代码中如果涉及负数需要格外小心最好明确使用取模% 2或语言提供的专门函数来判断奇偶性以避免未定义行为。3. 从原理到实践为什么是更底层的选择理解了 1的原理后一个很自然的问题是它和常用的取模运算% 2有什么区别为什么有人会选择用位运算这就引出了对运算本质和效率的思考。3.1 效率的微观视角在绝大多数现代编程语言和CPU架构中按位与运算 () 通常比取模运算 (%) 更快。原因在于它们对应的底层CPU指令开销不同。按位与 ()对应的CPU指令是AND。这是一个非常基础、简单的位操作指令通常在一个时钟周期内就能完成效率极高。它直接操作寄存器的位不涉及复杂的算术逻辑。取模 (%)取模运算本质上是除法运算的副产品。CPU的除法指令如DIV或IDIV要比AND指令复杂得多耗时也更长。虽然编译器会对% 2这样的特殊情况进行优化可能优化为与运算但这并不是百分之百的保证尤其在一些解释型语言或特定上下文中。我们可以做一个简单的类比判断一个数奇偶性用% 2好比是问“这个数除以2余多少”需要执行一套完整的除法流程而用 1则是直接看一眼这个数最后一位数字是0还是1。显然后者更直接。3.2 在SQL中的特殊意义在Leetcode 620题这样的SQL语境下使用rating 1还有另一层意义——展示对数据库函数和表达式的深入理解。SQL标准确实支持位运算函数虽然在不同的数据库管理系统DBMS中语法可能略有差异例如MySQL、PostgreSQL都支持作为按位与操作符。在简单的WHERE条件中使用它可能不会带来显著的性能提升因为数据库优化器非常强大会对rating % 2 1进行等价优化。但这种写法传递了一个信号作者不仅会写SQL还了解数据在底层可能的处理方式并且熟悉SQL语言的完整操作符集合。这在解决一些更复杂、需要位掩码技巧的SQL问题时会成为一个强大的工具。3.3 一个简单的性能对比实验思维实验虽然在实际的数据库查询中由于网络I/O、磁盘I/O和查询优化器的主导作用这点运算差异微乎其微但我们可以在纯计算层面理解其差异。想象一个需要循环判断数百万个整数奇偶性的内存计算任务例如在数据处理脚本中方案A (取模):for num in list: if num % 2 1: ...方案B (位与):for num in list: if num 1 1: ...在Python、Java等语言中对于大规模循环方案B通常会有微小的性能优势。当然真正的性能优化需要 profiling性能剖析不能盲目迷信位运算。但在认知层面知道存在这样一个更底层的选项是有价值的。实操心得不要为了“炫技”而滥用位运算。在大多数业务代码中% 2的可读性远高于 1。优先保证代码清晰易懂。只有在性能瓶颈被明确证实与此类计算相关或者是在处理真正的位级数据如权限掩码、状态标志位时才应优先考虑位运算。在SQL中除非遇到明确需要位操作的场景例如存储了位掩码的状态字段否则使用标准的MOD()函数或%运算符通常是更通用、更易读的选择。4. 按位与运算的广阔应用场景判断奇偶性只是按位与运算最基础的一个应用。它真正的威力在于处理“位掩码”Bitmask。位掩码是一种利用一个整数的不同二进制位来独立表示多个布尔状态是/否或选项的技术。这在系统设计、协议定义、权限管理等领域非常常见。4.1 权限系统设计这是最经典的案例。假设我们有一个文件系统需要对文件设置三种权限可读R、可写W、可执行X。我们可以用三个二进制位来表示第1位 (2^0 1): 可读第2位 (2^1 2): 可写第3位 (2^2 4): 可执行那么一个文件的权限就可以用一个整数表示权限5(二进制101): 表示可读(1) 可执行(4) 5不可写。权限6(二进制110): 表示可写(2) 可执行(4) 6不可读。现在如何检查一个用户是否有“可写”权限呢就用按位与# 假设文件权限是 perm 6 (二进制110 即可写可执行) READ 1 # 0001 WRITE 2 # 0010 EXECUTE 4 # 0100 def has_write_permission(perm): return (perm WRITE) ! 0 # 即 perm 2 ! 0 print(has_write_permission(6)) # 输出: True因为 6 2 2 (非零) print(has_write_permission(5)) # 输出: False因为 5 2 0perm WRITE这个操作就像用一个只打开“可写”位探照灯去照射权限整数。如果“可写”位是亮的1结果就不为0如果是暗的0结果就是0。这种方法可以非常高效地组合和检查多个权限。4.2 网络协议与标志位许多底层网络协议如TCP头部使用标志位来表示不同的控制信息。例如TCP头中有URG、ACK、PSH、RST、SYN、FIN等标志位它们各自占据一个二进制位。接收方通过按位与操作来快速解析这些标志决定如何处理数据包。4.3 图形与游戏开发在图像处理中有时需要分离或操作颜色通道ARGB。每个通道通常用8位0-255表示组合成一个32位整数。通过按位与和移位操作可以快速提取或修改特定通道的值。在游戏开发中也常用位掩码来进行碰撞层管理或状态机管理。4.4 算法与数据结构在一些高级算法中位运算可以制造出惊人的效率。例如快速判断2的幂:n (n - 1) 0。如果一个正整数是2的幂它的二进制表示只有一个1。n-1则会把这个1右边的所有位变成1。两者相与结果必为0。交换两个变量的值不使用临时变量: 可以使用异或运算a ^ b; b ^ a; a ^ b;这其中也蕴含了位运算的思想。布隆过滤器 (Bloom Filter)这种概率型数据结构大量使用了位数组和哈希函数其核心操作之一就是通过按位与来检查某一位是否被设置。5. 深入原理从逻辑门到CPU指令为了真正理解按位与我们可以再往下走一层看看它在硬件层面是如何实现的。这有助于我们理解其“高速”特性的根源。5.1 逻辑门与门AND Gate一切始于最基础的电子元件——逻辑门。与门是一个有两个输入和一个输出的基本数字电路。它的行为就是我们前面真值表描述的那样仅当两个输入都是高电平代表1时输出才是高电平1否则输出低电平0。一个物理的与门可以由几个晶体管组合而成。5.2 从位到整数并行计算CPU的寄存器有固定的宽度比如32位或64位。当我们执行一条AND指令如AND rax, rbx时CPU并不是用一个逻辑门算完一位再算下一位。相反它内部有32个或64个并排的与门电路同时处理寄存器中所有对应位上的运算。这就是位运算在硬件层面“快”的根本原因——高度的并行性。一次CPU指令就完成了一个32/64位整数的全部按位与操作。5.3 与运算的数学性质了解这些性质有助于我们在设计中更灵活地运用它交换律:a b b a结合律:(a b) c a (b c)分配律对按位或:a (b | c) (a b) | (a c)幂等律:a a a与零相与得零:a 0 0与全1相与得自身:a (-1) a在补码表示中-1的二进制是所有位都为1这些性质在简化逻辑表达式、优化代码时非常有用。6. 常见误区与避坑指南尽管位运算强大但使用时陷阱也不少。下面是一些常见的“坑”和对应的避坑技巧。6.1 运算符优先级陷阱在大多数编程语言中位运算符的优先级通常低于比较运算符如,!但高于逻辑运算符如,||。一个经典的错误是if (value 1 0) { // 意图判断是否为偶数 // ... }在C、Java、Python等语言中的优先级高于。所以这行代码实际被解释为if (value (1 0))即if (value 0)这永远为假导致逻辑错误。正确做法是始终使用括号明确优先级if ((value 1) 0) { // 正确 // ... }6.2 负数与补码的困扰这是我们之前提到过的关键点。现代计算机普遍使用补码来表示有符号整数。在补码中负数的二进制表示最高位符号位为1且其数值部分并非简单的原码。 例如在8位有符号整数中-1的补码是11111111-5的补码是11111011(计算过程5的原码00000101- 反码11111010- 加1得补码11111011)那么-5 1等于多少-5 的补码: 11111011 1 的二进制: 00000001 按位与操作: --------- 00000001结果是1。按照我们“最低位为1是奇数”的规则-5确实是奇数。所以在这个特例下 1判断奇偶性对于负数似乎也“碰巧”工作。但是这严重依赖于语言规范。在C/C中对有符号负数的位操作结果是由实现定义的implementation-defined可能产生不可移植的结果。在Java中则明确规定了使用补码且位运算针对整数的二进制补码形式进行。在Python中整数理论上是无限精度的负数的位运算行为也有其特定规则。核心建议为了代码的清晰性和可移植性判断整数的奇偶性时请优先使用取模运算x % 2 0偶数或x % 2 ! 0奇数。或者使用语言提供的专门函数如Math.abs(x) % 2。将 1保留给你确知自己在处理无符号位模式或明确需要位掩码操作的场景。6.3 移位运算与符号位与按位与经常搭配使用的是移位运算左移右移。这里有一个大坑算术右移和逻辑右移的区别。逻辑右移无论正负高位一律补0。相当于把二进制串当作无符号数整体右移。算术右移右移时高位补的是符号位的值正数补0负数补1。这是为了在右移时保持负数的符号相当于做除以2的运算向下取整。在Java中是算术右移是无符号右移逻辑右移。在C/C中对于有符号数是算术右移还是逻辑右移是由实现定义的通常是算术右移对于无符号数是逻辑右移。在Python中是算术右移。6.4 可读性与维护性这是最重要的“软性”陷阱。位运算写出的代码对于不熟悉的人来说就像天书。例如# 晦涩的位运算 flags flags ~MASK | new_value # 可能更清晰的写法如果语言支持 flags (flags ~MASK) | new_value # 或者如果操作不复杂考虑用更高级的抽象在团队协作或维护历史代码时清晰的意图远比一点微乎其微的性能提升重要。除非在性能关键的底层库、算法竞赛或明确的位掩码上下文中否则请谨慎使用并务必加上清晰的注释。7. 举一反三其他位运算的妙用以按位与为起点我们可以快速理解其他位运算它们共同构成了强大的位级操作工具箱。7.1 按位或|用于设置位规则两位中有一个为1结果就为1。常用于将某些位“打开”设为1。READ 1 WRITE 2 perm 0 perm perm | READ # 添加读权限perm变为1 perm perm | WRITE # 添加写权限perm变为3 (二进制11)7.2 按位异或^用于切换位规则两位不同则结果为1相同则结果为0。一个非常有趣的性质a ^ a 0,a ^ 0 a。常用于切换toggle特定位的状态或在不使用临时变量的情况下交换两个数。# 切换第n位的状态 def toggle_bit(x, n): return x ^ (1 n) # 交换a和b a a ^ b b a ^ b # 此时 b (a ^ b) ^ b a ^ (b ^ b) a ^ 0 a a a ^ b # 此时 a (a ^ b) ^ a (a ^ a) ^ b 0 ^ b b7.3 按位非~取反规则每一位取反0变11变0。注意在补码表示中~x等于-x - 1。常用于创建掩码。MASK 0b00001111 # 要获取MASK的“反掩码”用于清除MASK表示的位 INVERSE_MASK ~MASK7.4 左移与右移、快速乘除与位对齐左移n位相当于乘以2^n右移n位相当于除以2^n向下取整。这是比直接乘除更快的操作。x 5 # 101 y x 2 # 10100 即20 相当于5 * 4 z x 1 # 10 即2 相当于5 // 2移位运算也广泛用于从打包的数据中提取特定字段或构造位掩码。# 构造一个只有第3位为1的掩码 (从0开始计数) mask 1 3 # 得到 0b1000 即88. 回到Leetcode思维延伸让我们回到最初的起点——Leetcode。位运算在算法竞赛和面试中是一类重要的技巧常用于状态压缩、优化常数时间、解决特定数学问题等。8.1 状态压缩动态规划Bitmask DP这是位运算在算法中最华丽的应用之一。当我们需要表示一个集合的状态例如哪些节点被访问过哪些任务已完成如果集合元素数量n不大比如n 20我们可以用一个n位的整数来表示这个集合。第i位为1表示第i个元素在集合中。这样集合的交、并、差、补操作就可以用位运算、|、 ~、^来高效完成。动态规划的状态dp[mask]就可以表示达到某个集合状态mask时的最优解。这能将许多指数级复杂度的搜索问题转化为在状态空间上的多项式时间动态规划。8.2 快速判断属性除了奇偶性还可以快速判断是否是2的幂n 0 and (n (n - 1)) 0检查第i位是否为1(num i) 1或num (1 i)将第i位设为1num | (1 i)将第i位设为0num ~(1 i)8.3 算法题实例很多题目暗藏位运算的巧解。例如“只出现一次的数字”一个数组所有数字都出现两次只有一个出现一次找出它。利用异或运算^的性质a ^ a 0,a ^ 0 a且满足交换律和结合律只需要将所有数字依次异或最终结果就是那个只出现一次的数字。时间复杂度O(n)空间复杂度O(1)极其优雅。从一道简单的SQL题出发我们深入了位运算的世界。rating 1这个小小的表达式像一把钥匙打开了一扇通往计算机底层逻辑的门。我们看到了它背后清晰的二进制逻辑、在硬件层面的高效实现、在权限控制等场景下的强大应用也绕开了它在优先级、负数处理上的陷阱。更重要的是我们建立了一种思维在遇到问题时除了高级的抽象有时也可以向下思考看看是否能用更接近机器本质的方式来表达和解决。这种思维对于写出高效、优雅的代码对于深入理解计算机系统都大有裨益。下次当你再看到、|、^、这些符号时希望你能会心一笑知道它们不仅仅是冰冷的操作符而是构建数字世界的一块块积木。