1. 项目概述从“0”和“1”开始理解计算机的底层语言如果你写过代码一定用过加减乘除也用过和||来判断条件。但有没有想过计算机的CPU在最底层其实不认识这些“高级”的运算它真正“认识”和直接处理的是每一位上的“0”和“1”。我们今天要聊的位运算就是直接操作这些二进制位的运算它是编程语言与硬件指令之间的一座直接桥梁。无论是为了写出更高效的代码还是为了通过某些算法竞赛比如标题里提到的CSP初赛的刁钻题目亦或是为了真正理解计算机如何处理整数和浮点数位运算和与之紧密相关的原码、反码、补码都是无法绕开的基础。很多人初次接触位运算会觉得它很“偏门”只在一些特定场景如嵌入式开发、加密算法、图形处理才会用到。但事实并非如此。一个简单的例子判断一个整数是奇数还是偶数最快速的方法不是n % 2 0而是(n 1) 0。因为与运算直接检查最低位是0还是1而取模运算%背后是一系列更复杂的算术过程。再比如快速计算2的n次方可以用左移运算1 n这比调用pow(2, n)或循环相乘要快得多。理解位运算就像是拿到了打开计算机底层性能优化大门的钥匙。而原码、反码、补码则是理解计算机中整数如何表示和运算的关键。为什么int类型的范围是-2147483648到2147483647为什么-1在内存中看起来是0xFFFFFFFF为什么加法器可以直接用来做减法这些问题的答案都藏在补码的设计里。可以说不懂补码就不能算真正理解了计算机的整数运算。所以这篇内容的目标很明确抛开晦涩的教科书定义用最直白的语言和大量实操例子带你彻底掌握位运算的四大操作与、或、异或、取反并弄懂原码、反码、补码的前世今生与内在联系。无论你是正在备战信息学竞赛的学生还是希望夯实基础、写出更优雅代码的开发者抑或是单纯对计算机原理感到好奇的学习者这篇内容都将为你提供一次彻底搞懂这些概念的机会。2. 核心基石彻底搞懂原码、反码与补码在直接操作二进制位之前我们必须先解决一个根本问题计算机如何表示一个数特别是负数你可能会想这还不简单加个负号“-”不就行了但在只有0和1的世界里“-”这个符号并不存在。计算机科学家们设计了几种编码方案最终补码成为了绝对的主流。理解这个演变过程比死记硬背定义重要得多。2.1 原码最直观但也最“难用”的表示法原码的规则非常符合人类的直觉最高位表示符号0为正1为负其余位表示数值的绝对值。假设我们用8位二进制来举例5的原码是0000 0101最高位0表示正后面是5的二进制101-5的原码是1000 0101最高位1表示负后面是5的二进制101看起来清晰明了对吧但问题马上就来了。第一个大问题“零”有两个编码。0的原码是0000 0000-0的原码是1000 0000。对于计算机来说同一个数值“0”有两种不同的内部表示这在进行比较、判断时会带来极大的麻烦和逻辑复杂性。第二个也是更致命的问题运算电路设计极其复杂。我们设计CPU的算术逻辑单元ALU时希望加法器能同时处理加法和减法。但如果用原码做加法5 (-5)理论上应该等于0。但让我们用原码算一下0000 0101 (5的原码) 1000 0101 (-5的原码) --------------- 1000 1010 (结果是-10的原码)这显然错了。为了让原码能进行正确的加减法CPU必须额外判断两个数的符号位如果是同号就做加法异号就要用绝对值大的减绝对值小的结果符号取绝对值大的那个数的符号……这套逻辑非常复杂会严重拖慢运算速度增加硬件成本。正因为原码在运算上的巨大缺陷它被淘汰了。我们需要一种新的编码让减法运算可以转化为加法运算从而让硬件设计变得简单统一。2.2 反码过渡方案解决了部分问题反码可以看作是为了解决原码运算问题的一个尝试。它的规则是正数的反码与其原码相同负数的反码是在其原码的基础上符号位不变其余各位取反0变11变0。同样用8位举例5的反码依然是0000 0101-5的原码是1000 0101其余位取反得到反码1111 1010反码的设计意图是让x (-x) 0。我们来验证一下5 (-5)0000 0101 (5的反码) 1111 1010 (-5的反码) --------------- 1 0000 0000 (最高位溢出得到8位的0000 0000)注意这里产生了进位溢出如果我们忽略最高位的进位在固定位宽的计算机中溢出位会被丢弃结果正好是0000 0000也就是0的反码。看起来成功了但是反码依然没有解决“零”有两个编码的问题0的反码0000 0000-0的反码1111 1111更重要的是反码的运算规则虽然比原码简单了一些但依然不够完美。在进行跨越0点的加减法时有时需要对结果进行“循环进位”即把溢出的进位再加回到最低位这仍然增加了电路的复杂性。2.3 补码终极解决方案现代计算机的基石补码完美地解决了原码和反码的所有问题它的设计非常巧妙。规则如下正数的补码与其原码相同负数的补码是在其反码的基础上加1。继续我们的例子5的补码是0000 0101与原码、反码相同-5的计算过程-5的原码1000 0101符号位不变其余取反得到反码1111 1010反码加1得到补码1111 1011补码的精髓与优势唯一的零表示0的补码是0000 0000。那么-0呢按照规则-0的原码是1000 0000反码是1111 1111反码加11111 1111 1 1 0000 0000。由于我们只有8位最高位的1溢出被丢弃结果还是0000 0000。所以补码中0只有一种表示将减法统一为加法这是补码最伟大的特性。x - y可以等价于x (-y)而-y就是y的补码。CPU只需要一个加法器就能同时完成加法和减法运算。 验证5 - 3即5 (-3)5的补码0000 0101-3的补码先求3的补码0000 0011然后按位取反加11111 1100 1 1111 1101计算0000 0101 1111 1101 1 0000 0010。丢弃溢出位得到0000 0010这正是2的补码。完美自然的溢出与范围对于n位有符号整数补码能表示的范围是-2^(n-1)到2^(n-1)-1。例如8位补码范围是-128到127。这个范围是连续的、不对称的负数比正数多一个即那个特殊的-128其补码直接表示为1000 0000没有对应的原码和反码。这种表示法非常契合模运算的思想。实操心得如何快速心算一个负数的补码死记“取反加一”的公式有时会慢。我常用的方法是“凑整法”找到一个正数让它和这个负数相加等于2^nn是位数。比如在8位系统中求-5的补码。思考什么数加上5等于2562^8答案是251。251的二进制就是-5的补码。251的二进制是1111 1011这与我们之前计算的结果一致。这个方法在理解上更直观。重要结论在现代计算机系统中整数在内存中一律以补码形式存储和参与运算。我们接下来要讨论的所有位运算其操作对象都是这些补码形式的二进制位。理解这一点是正确理解和预测位运算结果的前提。3. 位运算四大核心操作详解现在我们终于可以开始直接操作这些二进制位了。位运算的操作对象是整数以其补码形式但运算规则是按位独立进行的。我们可以把两个数字的每一个二进制位对齐然后根据规则逐位计算。下面我们逐一拆解这四大操作。3.1 按位与逻辑“乘”用于掩码与清零运算规则只有两个对应的二进制位都为1时结果位才为1否则为0。其真值表如下ABA B000010100111你可以把它想象成逻辑上的“乘法”或者一个严格的“过滤器”。核心应用场景奇偶性判断n 1。因为二进制奇数的最低位是1偶数的最低位是0。所以(n 1) 1判断为奇数(n 1) 0判断为偶数。这比n % 2效率更高。int n 7; if (n 1) { printf(%d 是奇数\n, n); // 输出 }取特定位掩码操作这是与运算最常用的功能。用一个特定二进制模式掩码去“与”一个数可以取出保留我们关心的位而将其他位清零。取出低8位n 0xFF0xFF二进制是1111 1111检查第k位从0开始是否为1n (1 k)。如果结果不为0则第k位是1。获取一个颜色值的RGB分量在32位ARGB颜色值0xFF336699中取蓝色分量(B)就是color 0xFF。int color 0xFF336699; // 一个ARGB颜色 int blue color 0xFF; // blue 0x99 (153) int green (color 8) 0xFF; // green 0x66 (102) int red (color 16) 0xFF; // red 0x33 (51) int alpha (color 24) 0xFF; // alpha 0xFF (255)清零特定位构造一个掩码需要清零的位为0其他位为1然后进行与运算。将最低位清零n (~1)或n 0xFFFFFFFE假设32位。将第k位清零n (~(1 k))。注意事项符号位的陷阱在与运算中如果操作数是负数补码形式结果需要小心理解。例如-5 0xFF在32位系统中-5的补码是0xFFFFFFFB与0xFF相与后得到0x000000FB即251。这实际上是取出了-5的低8位。如果你期望得到一个正数结果这种操作是没问题的。但如果你将其视为数学上的“与”可能会感到困惑。关键在于位运算始终是按位的逻辑操作不直接等同于整数间的数学关系。3.2 按位或|逻辑“加”用于置位与组合运算规则只要两个对应的二进制位有一个为1结果位就为1否则为0。其真值表如下ABA | B000011101111你可以把它想象成逻辑上的“加法”但1|11不会进位或者一个“开关打开”操作。核心应用场景将特定位设置为1置位用一个掩码去“或”一个数可以将掩码中为1的位强制设置为1其他位保持不变。将最低位置1n | 1。将第k位置1n | (1 k)。int flags 0; // 初始状态所有标志位为0 flags flags | 0x01; // 设置第0位标志比如“已读”标志 flags flags | 0x04; // 设置第2位标志比如“置顶”标志 // 现在 flags 的二进制是 0000 0101即同时设置了第0位和第2位。合并数据可以将多个数据片段组合到一个整数的不同区域。常与左移、右移操作配合。// 将4个8位的字节组合成一个32位整数 unsigned char a 0xAA, b 0xBB, c 0xCC, d 0xDD; unsigned int combined (d 24) | (c 16) | (b 8) | a; // combined 0xDDCCBBAA实现简单的开关逻辑在资源紧张的嵌入式系统中常用一个整数的不同位来表示多个布尔开关用或运算来打开开关。3.3 按位异或^找不同与无进位加法运算规则当两个对应的二进制位**相异一个0一个1**时结果位为1否则为0。其真值表如下ABA ^ B000011101110异或运算有几个非常美妙且重要的数学性质归零律a ^ a 0任何数与自身异或结果为0恒等律a ^ 0 a任何数与0异或结果为其本身交换律和结合律a ^ b b ^ a(a ^ b) ^ c a ^ (b ^ c)自反性a ^ b ^ b a因为a ^ b ^ b a ^ (b ^ b) a ^ 0 a核心应用场景不借助临时变量交换两个数这是异或最著名的技巧。int a 5, b 9; a a ^ b; // a 现在等于 5 ^ 9 b a ^ b; // b (5 ^ 9) ^ 9 5 ^ (9 ^ 9) 5 ^ 0 5 a a ^ b; // a (5 ^ 9) ^ 5 (5 ^ 5) ^ 9 0 ^ 9 9 // 现在 a9, b5交换完成这个方法的优势是在一些极端环境下如嵌入式系统可以节省一个临时变量的内存空间但现代编译器优化下使用临时变量的方法通常更安全易读。加密与简单校验如异或校验利用a ^ b ^ b a的特性可以进行简单的加密解密。网络传输或存储中常用的异或校验就是将所有数据字节进行连续异或得到一个校验和。接收方再次计算并与发送的校验和比较如果不一致则说明数据可能出错。// 计算一段数据的异或校验和 unsigned char data[] {0x01, 0x02, 0x03, 0x04, 0x05}; unsigned char checksum 0; for (int i 0; i 5; i) { checksum ^ data[i]; // 连续异或 } // checksum 就是校验和。传输时附带这个值。 // 接收方重新计算所有数据包括收到的校验和的异或结果应为0否则出错。找出数组中唯一不重复的元素在一个数组中除了一个元素只出现一次其他每个元素都出现两次找出那个只出现一次的元素。利用a ^ a 0和a ^ 0 a的性质将所有元素一起异或成对出现的元素会抵消为0最后剩下的就是那个单独的元素。int arr[] {2, 3, 4, 5, 3, 2, 4}; int single 0; for (int i 0; i 7; i) { single ^ arr[i]; } // single 最终等于 5翻转特定位开关切换与1异或可以翻转取反特定位与0异或则保持不变。翻转第k位n ^ (1 k)。如果该位是0则变1是1则变0。3.4 按位取反~一元操作比特位翻转运算规则这是一个一元运算符。它将操作数的每一个二进制位取反0变11变0。特别注意取反运算的结果高度依赖于操作数的类型和位数。在C/C、Java等语言中对整数进行取反是对其补码形式的所有位包括符号位进行取反。unsigned char a 5; // 二进制 0000 0101 unsigned char b ~a; // 二进制 1111 1010即 250 (十进制) 或 0xFA (十六进制) char c 5; // 在大多数系统中char 是有符号的补码表示同样是 0000 0101 char d ~c; // 对补码取反1111 1010这个补码表示的是 -6 printf(%d\n, d); // 输出 -6核心应用场景构造掩码与运算配合用于清零特定位。如前所述n (~(1 k))用于将第k位清零。~(1 k)生成了一个只有第k位是0其他位都是1的掩码。获取一个数的相反数减一对于一个整数x无论是正是负有一个有趣的等式~x -x - 1。你可以用补码的定义来验证这个等式。这有时可以用于一些巧妙的代码优化。在无符号数中实现模运算对于无符号整数~0会得到该类型能表示的最大值所有位全1。例如unsigned int max ~0;。~n则等于MAX_UINT - n。实操心得区分逻辑非(!)与按位取反(~)这是初学者常犯的错误。!是逻辑非它把任何非零值变成0把0变成1。而~是按位取反作用在每个二进制位上。例如int x 5; // 二进制 ... 0101 int a !x; // a 0 (因为x非零) int b ~x; // b ... 1111 1010 (即-6的补码) printf(!%d %d, ~%d %d\n, x, a, x, b);务必根据你的意图选择正确的运算符。4. 位运算的实战应用与高级技巧理解了基本操作后我们来看看如何将它们组合起来解决一些实际问题和算法挑战。这部分内容将结合代码示例展示位运算的强大威力。4.1 状态压缩用整数表示集合这是位运算在算法竞赛如标题中提到的CSP、NOI和某些特定场景下的经典应用。核心思想是用一个整数的每一个二进制位来表示一个元素是否存在。假设我们有n个元素我们可以用一个n位的整数来表示它的一个子集。基本操作假设用int mask表示一个集合第i位从0开始表示第i个元素。加入元素imask mask | (1 i)删除元素imask mask ~(1 i)检查元素i是否存在if (mask (1 i))切换元素i的状态mask mask ^ (1 i)求两个集合的交集mask1 mask2求两个集合的并集mask1 | mask2求补集~mask注意位数限制通常需要与一个全1的掩码相与如(~mask) ((1 n) - 1)应用场景动态规划DP在旅行商问题TSP等状态空间模型中用位掩码表示已经访问过的城市集合可以极大地压缩状态表示提高效率。权限系统用不同的位表示不同的权限如读、写、执行、删除一个用户的权限可以用一个整数表示检查权限时用与运算即可。#define PERM_READ (1 0) // 0001 #define PERM_WRITE (1 1) // 0010 #define PERM_EXEC (1 2) // 0100 #define PERM_DEL (1 3) // 1000 int user_perm PERM_READ | PERM_WRITE; // 用户有读和写权限即 0011 // 检查是否有写权限 if (user_perm PERM_WRITE) { printf(有写权限\n); } // 添加执行权限 user_perm | PERM_EXEC; // 移除写权限 user_perm ~PERM_WRITE;4.2 快速乘除与幂运算利用移位运算左移右移可以快速进行2的幂次方的乘除。a n等价于a * (2^n)a n等价于a / (2^n)注意对于有符号负数右移是算术右移高位补符号位并非严格的除以2^n。对于无符号数或正数逻辑右移等价于除以2^n。快速幂算法计算a^b的高效算法其核心思想就是利用指数的二进制表示和位运算。例如计算3^1313的二进制是1101即13 8 4 1。那么3^13 3^8 * 3^4 * 3^1。算法通过不断平方底数a a * a并根据指数b的当前最低位是否为1来决定是否乘入结果。long long fastPow(long long a, long long b) { long long result 1; while (b 0) { if (b 1) { // 如果b的当前最低位是1 result * a; } a * a; // 底数平方 b 1; // 指数右移一位 } return result; }4.3 位运算实现集合论操作与趣味题目判断一个数是否是2的幂如果一个正整数n是2的幂那么它的二进制表示中有且仅有一个1。例如8 (1000)16 (10000)。利用n (n-1)的技巧可以快速判断。bool isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }原理如果n是2的幂比如1000那么n-1就是0111。两者相与结果为0。如果n不是2的幂比如1010那么n-1是1001相与结果为1000不为0。计算一个整数的二进制表示中1的个数Population Count这是一个经典问题。int countBits(int n) { int count 0; while (n) { n (n - 1); // 每次操作消去n二进制表示中最低位的1 count; } return count; }原理n (n-1)这个操作每次都能将n最低位的1变成0。循环直到n为0循环次数就是1的个数。比逐位检查要高效。不用比较运算符找出两个数中的较大/较小值利用位运算和算术运算的特性。// 方法之一利用差值符号位。注意此方法可能溢出需谨慎使用。 int max(int a, int b) { // 计算 (a - b) 的符号位。在32位系统中右移31位得到符号位0或-1。 int sign (a - b) 31; // 如果absign0如果absign-1所有位全1 // 当sign0时a (a-b)*0 a当sign-1时a (a-b)*(-1) b return a sign * (a - b); // 更稳健但复杂的方法需要处理溢出这里仅展示思路。 }5. 常见问题、陷阱与深度思考即使理解了原理在实际编码中位运算仍然有许多细节需要注意否则极易产生隐蔽的Bug。5.1 符号位与移位操作的陷阱这是位运算中最容易出错的地方主要发生在有符号数的右移和取反操作上。算术右移 vs 逻辑右移逻辑右移无论符号位是0还是1高位都补0。C/C中对无符号整数进行右移是逻辑右移。算术右移高位补符号位。C/C中对有符号整数进行右移大多数编译器实现为算术右移这是标准允许的但非强制不过几乎所有现代平台都如此。int a -8; // 补码1111...1111 1000 (32位) int b a 2; // 算术右移2位高位补1结果1111...1111 1110即 -2 unsigned int c (unsigned int)a; // 数值变为一个很大的正数4294967288 unsigned int d c 2; // 逻辑右移2位高位补0结果是一个正数 printf(%d %u\n, b, d); // 输出 -2 和 1073741822教训当你想进行除以2的幂运算时如果操作数可能为负直接使用右移得到的是向负无穷取整的除法-3 1 -2而数学除法-3 / 2在C语言中是向零取整-1。两者结果不同左移的未定义行为对于有符号数如果左移后发生符号位改变即溢出在C/C标准中是未定义行为。这意味着编译器可以做任何事情程序可能崩溃或产生任意结果。对于无符号数左移是定义良好的溢出部分被丢弃。int a 0x40000000; // 2^30 a a 2; // 左移后理论上应为0x100000000但符号位改变这是未定义行为 unsigned int b 0x40000000; b b 2; // 定义良好结果为0x00000000溢出丢弃最佳实践进行移位操作时尽量使用无符号整数类型如unsigned int除非你非常清楚自己在做什么并且能确保不会触发未定义行为。5.2 运算符优先级带来的坑位运算符的优先级通常低于比较运算符和算术运算符。忘记加括号是常见的错误来源。int a 1, b 2, c 3; int result1 a b c; // 错误等价于 a (b c)因为 优先级高于 int result2 (a b) c; // 正确写法 int flag 0x01; if (flag 0x03 ! 0) { ... } // 错误等价于 flag (0x03 ! 0)永远为真或假 if ((flag 0x03) ! 0) { ... } // 正确写法安全建议只要涉及位运算与其他运算符混用一律加上括号不要依赖记忆优先级。5.3 关于“异或高斯消元”与“异或校验”的延伸标题的热搜词提到了“异或高斯消元”和“异或校验”这里简要解释其联系。异或校验如前所述它是一种简单、快速的错误检测方法。由于其线性性质异或运算是线性运算它被广泛用于网络通信如IP包头校验和、存储系统如RAID 5等场景。但它只能检测奇数个位错误无法纠正错误也不能检测偶数个位错误。异或高斯消元这是在解异或方程组时用到的一种算法。所谓异或方程组就是所有方程中的变量系数和常数都是0或1运算规则是异或。例如x1 ^ x2 ^ x3 1 x1 ^ x3 0 x2 ^ x3 1这类方程组在密码学、逻辑电路设计、某些图论问题中会出现。解法和普通的高斯消元法类似但因为运算只有异或可以用位运算如bitset来高效实现时间复杂度可以优化到O(n^2/word_size)其中word_size是机器字长如64位。这是算法竞赛中的一个高级技巧。5.4 浮点数的位运算热搜词中出现了“float异或校验”。这是一个需要极度小心的领域。在C/C中直接对float或double进行位运算如,|,^,~是不合法的因为位运算符的操作数必须是整数类型。如果你想操作浮点数的二进制表示必须通过类型转换type-punning将其底层的内存解释为整数。常用的方法是使用union或memcpy。union FloatIntUnion { float f; unsigned int i; // 假设float是32位 }; union FloatIntUnion u; u.f 3.14f; unsigned int bits u.i; // 现在可以对bits进行位运算了 // ... 对bits进行异或校验等操作 ... u.i bits; // 再转换回去 float new_float u.f; // 注意这可能会产生NaN或非规格化数甚至触发硬件异常警告这种操作破坏了类型安全极易引入未定义行为、平台依赖性问题如字节序以及对特殊值NaN无穷大的错误处理。除非你在进行极其底层的系统编程、数值分析或特定格式的编解码并且完全清楚后果否则绝对不要在普通应用中对浮点数进行位运算。对于浮点数的校验通常使用基于其数值的校验和如相加或专门的CRC算法更为安全可靠。掌握位运算和补码就像是获得了与计算机硬件直接对话的能力。它不仅能让你写出更高效、更简洁的代码更能从根本上深化你对程序运行机制的理解。从判断奇偶性到状态压缩DP从交换两个变量到理解整数溢出的本质这些知识无处不在。我个人的体会是花时间彻底弄懂这些“底层”概念远比盲目学习更多高级框架和工具来得划算它是你技术栈中一块坚实的地基能让你在遇到复杂问题时多一种清晰而有力的解决思路。下次当你看到n (n-1)这样的表达式时希望你能会心一笑并自信地运用它。
1. 项目概述从“0”和“1”开始理解计算机的底层语言如果你写过代码一定用过加减乘除也用过和||来判断条件。但有没有想过计算机的CPU在最底层其实不认识这些“高级”的运算它真正“认识”和直接处理的是每一位上的“0”和“1”。我们今天要聊的位运算就是直接操作这些二进制位的运算它是编程语言与硬件指令之间的一座直接桥梁。无论是为了写出更高效的代码还是为了通过某些算法竞赛比如标题里提到的CSP初赛的刁钻题目亦或是为了真正理解计算机如何处理整数和浮点数位运算和与之紧密相关的原码、反码、补码都是无法绕开的基础。很多人初次接触位运算会觉得它很“偏门”只在一些特定场景如嵌入式开发、加密算法、图形处理才会用到。但事实并非如此。一个简单的例子判断一个整数是奇数还是偶数最快速的方法不是n % 2 0而是(n 1) 0。因为与运算直接检查最低位是0还是1而取模运算%背后是一系列更复杂的算术过程。再比如快速计算2的n次方可以用左移运算1 n这比调用pow(2, n)或循环相乘要快得多。理解位运算就像是拿到了打开计算机底层性能优化大门的钥匙。而原码、反码、补码则是理解计算机中整数如何表示和运算的关键。为什么int类型的范围是-2147483648到2147483647为什么-1在内存中看起来是0xFFFFFFFF为什么加法器可以直接用来做减法这些问题的答案都藏在补码的设计里。可以说不懂补码就不能算真正理解了计算机的整数运算。所以这篇内容的目标很明确抛开晦涩的教科书定义用最直白的语言和大量实操例子带你彻底掌握位运算的四大操作与、或、异或、取反并弄懂原码、反码、补码的前世今生与内在联系。无论你是正在备战信息学竞赛的学生还是希望夯实基础、写出更优雅代码的开发者抑或是单纯对计算机原理感到好奇的学习者这篇内容都将为你提供一次彻底搞懂这些概念的机会。2. 核心基石彻底搞懂原码、反码与补码在直接操作二进制位之前我们必须先解决一个根本问题计算机如何表示一个数特别是负数你可能会想这还不简单加个负号“-”不就行了但在只有0和1的世界里“-”这个符号并不存在。计算机科学家们设计了几种编码方案最终补码成为了绝对的主流。理解这个演变过程比死记硬背定义重要得多。2.1 原码最直观但也最“难用”的表示法原码的规则非常符合人类的直觉最高位表示符号0为正1为负其余位表示数值的绝对值。假设我们用8位二进制来举例5的原码是0000 0101最高位0表示正后面是5的二进制101-5的原码是1000 0101最高位1表示负后面是5的二进制101看起来清晰明了对吧但问题马上就来了。第一个大问题“零”有两个编码。0的原码是0000 0000-0的原码是1000 0000。对于计算机来说同一个数值“0”有两种不同的内部表示这在进行比较、判断时会带来极大的麻烦和逻辑复杂性。第二个也是更致命的问题运算电路设计极其复杂。我们设计CPU的算术逻辑单元ALU时希望加法器能同时处理加法和减法。但如果用原码做加法5 (-5)理论上应该等于0。但让我们用原码算一下0000 0101 (5的原码) 1000 0101 (-5的原码) --------------- 1000 1010 (结果是-10的原码)这显然错了。为了让原码能进行正确的加减法CPU必须额外判断两个数的符号位如果是同号就做加法异号就要用绝对值大的减绝对值小的结果符号取绝对值大的那个数的符号……这套逻辑非常复杂会严重拖慢运算速度增加硬件成本。正因为原码在运算上的巨大缺陷它被淘汰了。我们需要一种新的编码让减法运算可以转化为加法运算从而让硬件设计变得简单统一。2.2 反码过渡方案解决了部分问题反码可以看作是为了解决原码运算问题的一个尝试。它的规则是正数的反码与其原码相同负数的反码是在其原码的基础上符号位不变其余各位取反0变11变0。同样用8位举例5的反码依然是0000 0101-5的原码是1000 0101其余位取反得到反码1111 1010反码的设计意图是让x (-x) 0。我们来验证一下5 (-5)0000 0101 (5的反码) 1111 1010 (-5的反码) --------------- 1 0000 0000 (最高位溢出得到8位的0000 0000)注意这里产生了进位溢出如果我们忽略最高位的进位在固定位宽的计算机中溢出位会被丢弃结果正好是0000 0000也就是0的反码。看起来成功了但是反码依然没有解决“零”有两个编码的问题0的反码0000 0000-0的反码1111 1111更重要的是反码的运算规则虽然比原码简单了一些但依然不够完美。在进行跨越0点的加减法时有时需要对结果进行“循环进位”即把溢出的进位再加回到最低位这仍然增加了电路的复杂性。2.3 补码终极解决方案现代计算机的基石补码完美地解决了原码和反码的所有问题它的设计非常巧妙。规则如下正数的补码与其原码相同负数的补码是在其反码的基础上加1。继续我们的例子5的补码是0000 0101与原码、反码相同-5的计算过程-5的原码1000 0101符号位不变其余取反得到反码1111 1010反码加1得到补码1111 1011补码的精髓与优势唯一的零表示0的补码是0000 0000。那么-0呢按照规则-0的原码是1000 0000反码是1111 1111反码加11111 1111 1 1 0000 0000。由于我们只有8位最高位的1溢出被丢弃结果还是0000 0000。所以补码中0只有一种表示将减法统一为加法这是补码最伟大的特性。x - y可以等价于x (-y)而-y就是y的补码。CPU只需要一个加法器就能同时完成加法和减法运算。 验证5 - 3即5 (-3)5的补码0000 0101-3的补码先求3的补码0000 0011然后按位取反加11111 1100 1 1111 1101计算0000 0101 1111 1101 1 0000 0010。丢弃溢出位得到0000 0010这正是2的补码。完美自然的溢出与范围对于n位有符号整数补码能表示的范围是-2^(n-1)到2^(n-1)-1。例如8位补码范围是-128到127。这个范围是连续的、不对称的负数比正数多一个即那个特殊的-128其补码直接表示为1000 0000没有对应的原码和反码。这种表示法非常契合模运算的思想。实操心得如何快速心算一个负数的补码死记“取反加一”的公式有时会慢。我常用的方法是“凑整法”找到一个正数让它和这个负数相加等于2^nn是位数。比如在8位系统中求-5的补码。思考什么数加上5等于2562^8答案是251。251的二进制就是-5的补码。251的二进制是1111 1011这与我们之前计算的结果一致。这个方法在理解上更直观。重要结论在现代计算机系统中整数在内存中一律以补码形式存储和参与运算。我们接下来要讨论的所有位运算其操作对象都是这些补码形式的二进制位。理解这一点是正确理解和预测位运算结果的前提。3. 位运算四大核心操作详解现在我们终于可以开始直接操作这些二进制位了。位运算的操作对象是整数以其补码形式但运算规则是按位独立进行的。我们可以把两个数字的每一个二进制位对齐然后根据规则逐位计算。下面我们逐一拆解这四大操作。3.1 按位与逻辑“乘”用于掩码与清零运算规则只有两个对应的二进制位都为1时结果位才为1否则为0。其真值表如下ABA B000010100111你可以把它想象成逻辑上的“乘法”或者一个严格的“过滤器”。核心应用场景奇偶性判断n 1。因为二进制奇数的最低位是1偶数的最低位是0。所以(n 1) 1判断为奇数(n 1) 0判断为偶数。这比n % 2效率更高。int n 7; if (n 1) { printf(%d 是奇数\n, n); // 输出 }取特定位掩码操作这是与运算最常用的功能。用一个特定二进制模式掩码去“与”一个数可以取出保留我们关心的位而将其他位清零。取出低8位n 0xFF0xFF二进制是1111 1111检查第k位从0开始是否为1n (1 k)。如果结果不为0则第k位是1。获取一个颜色值的RGB分量在32位ARGB颜色值0xFF336699中取蓝色分量(B)就是color 0xFF。int color 0xFF336699; // 一个ARGB颜色 int blue color 0xFF; // blue 0x99 (153) int green (color 8) 0xFF; // green 0x66 (102) int red (color 16) 0xFF; // red 0x33 (51) int alpha (color 24) 0xFF; // alpha 0xFF (255)清零特定位构造一个掩码需要清零的位为0其他位为1然后进行与运算。将最低位清零n (~1)或n 0xFFFFFFFE假设32位。将第k位清零n (~(1 k))。注意事项符号位的陷阱在与运算中如果操作数是负数补码形式结果需要小心理解。例如-5 0xFF在32位系统中-5的补码是0xFFFFFFFB与0xFF相与后得到0x000000FB即251。这实际上是取出了-5的低8位。如果你期望得到一个正数结果这种操作是没问题的。但如果你将其视为数学上的“与”可能会感到困惑。关键在于位运算始终是按位的逻辑操作不直接等同于整数间的数学关系。3.2 按位或|逻辑“加”用于置位与组合运算规则只要两个对应的二进制位有一个为1结果位就为1否则为0。其真值表如下ABA | B000011101111你可以把它想象成逻辑上的“加法”但1|11不会进位或者一个“开关打开”操作。核心应用场景将特定位设置为1置位用一个掩码去“或”一个数可以将掩码中为1的位强制设置为1其他位保持不变。将最低位置1n | 1。将第k位置1n | (1 k)。int flags 0; // 初始状态所有标志位为0 flags flags | 0x01; // 设置第0位标志比如“已读”标志 flags flags | 0x04; // 设置第2位标志比如“置顶”标志 // 现在 flags 的二进制是 0000 0101即同时设置了第0位和第2位。合并数据可以将多个数据片段组合到一个整数的不同区域。常与左移、右移操作配合。// 将4个8位的字节组合成一个32位整数 unsigned char a 0xAA, b 0xBB, c 0xCC, d 0xDD; unsigned int combined (d 24) | (c 16) | (b 8) | a; // combined 0xDDCCBBAA实现简单的开关逻辑在资源紧张的嵌入式系统中常用一个整数的不同位来表示多个布尔开关用或运算来打开开关。3.3 按位异或^找不同与无进位加法运算规则当两个对应的二进制位**相异一个0一个1**时结果位为1否则为0。其真值表如下ABA ^ B000011101110异或运算有几个非常美妙且重要的数学性质归零律a ^ a 0任何数与自身异或结果为0恒等律a ^ 0 a任何数与0异或结果为其本身交换律和结合律a ^ b b ^ a(a ^ b) ^ c a ^ (b ^ c)自反性a ^ b ^ b a因为a ^ b ^ b a ^ (b ^ b) a ^ 0 a核心应用场景不借助临时变量交换两个数这是异或最著名的技巧。int a 5, b 9; a a ^ b; // a 现在等于 5 ^ 9 b a ^ b; // b (5 ^ 9) ^ 9 5 ^ (9 ^ 9) 5 ^ 0 5 a a ^ b; // a (5 ^ 9) ^ 5 (5 ^ 5) ^ 9 0 ^ 9 9 // 现在 a9, b5交换完成这个方法的优势是在一些极端环境下如嵌入式系统可以节省一个临时变量的内存空间但现代编译器优化下使用临时变量的方法通常更安全易读。加密与简单校验如异或校验利用a ^ b ^ b a的特性可以进行简单的加密解密。网络传输或存储中常用的异或校验就是将所有数据字节进行连续异或得到一个校验和。接收方再次计算并与发送的校验和比较如果不一致则说明数据可能出错。// 计算一段数据的异或校验和 unsigned char data[] {0x01, 0x02, 0x03, 0x04, 0x05}; unsigned char checksum 0; for (int i 0; i 5; i) { checksum ^ data[i]; // 连续异或 } // checksum 就是校验和。传输时附带这个值。 // 接收方重新计算所有数据包括收到的校验和的异或结果应为0否则出错。找出数组中唯一不重复的元素在一个数组中除了一个元素只出现一次其他每个元素都出现两次找出那个只出现一次的元素。利用a ^ a 0和a ^ 0 a的性质将所有元素一起异或成对出现的元素会抵消为0最后剩下的就是那个单独的元素。int arr[] {2, 3, 4, 5, 3, 2, 4}; int single 0; for (int i 0; i 7; i) { single ^ arr[i]; } // single 最终等于 5翻转特定位开关切换与1异或可以翻转取反特定位与0异或则保持不变。翻转第k位n ^ (1 k)。如果该位是0则变1是1则变0。3.4 按位取反~一元操作比特位翻转运算规则这是一个一元运算符。它将操作数的每一个二进制位取反0变11变0。特别注意取反运算的结果高度依赖于操作数的类型和位数。在C/C、Java等语言中对整数进行取反是对其补码形式的所有位包括符号位进行取反。unsigned char a 5; // 二进制 0000 0101 unsigned char b ~a; // 二进制 1111 1010即 250 (十进制) 或 0xFA (十六进制) char c 5; // 在大多数系统中char 是有符号的补码表示同样是 0000 0101 char d ~c; // 对补码取反1111 1010这个补码表示的是 -6 printf(%d\n, d); // 输出 -6核心应用场景构造掩码与运算配合用于清零特定位。如前所述n (~(1 k))用于将第k位清零。~(1 k)生成了一个只有第k位是0其他位都是1的掩码。获取一个数的相反数减一对于一个整数x无论是正是负有一个有趣的等式~x -x - 1。你可以用补码的定义来验证这个等式。这有时可以用于一些巧妙的代码优化。在无符号数中实现模运算对于无符号整数~0会得到该类型能表示的最大值所有位全1。例如unsigned int max ~0;。~n则等于MAX_UINT - n。实操心得区分逻辑非(!)与按位取反(~)这是初学者常犯的错误。!是逻辑非它把任何非零值变成0把0变成1。而~是按位取反作用在每个二进制位上。例如int x 5; // 二进制 ... 0101 int a !x; // a 0 (因为x非零) int b ~x; // b ... 1111 1010 (即-6的补码) printf(!%d %d, ~%d %d\n, x, a, x, b);务必根据你的意图选择正确的运算符。4. 位运算的实战应用与高级技巧理解了基本操作后我们来看看如何将它们组合起来解决一些实际问题和算法挑战。这部分内容将结合代码示例展示位运算的强大威力。4.1 状态压缩用整数表示集合这是位运算在算法竞赛如标题中提到的CSP、NOI和某些特定场景下的经典应用。核心思想是用一个整数的每一个二进制位来表示一个元素是否存在。假设我们有n个元素我们可以用一个n位的整数来表示它的一个子集。基本操作假设用int mask表示一个集合第i位从0开始表示第i个元素。加入元素imask mask | (1 i)删除元素imask mask ~(1 i)检查元素i是否存在if (mask (1 i))切换元素i的状态mask mask ^ (1 i)求两个集合的交集mask1 mask2求两个集合的并集mask1 | mask2求补集~mask注意位数限制通常需要与一个全1的掩码相与如(~mask) ((1 n) - 1)应用场景动态规划DP在旅行商问题TSP等状态空间模型中用位掩码表示已经访问过的城市集合可以极大地压缩状态表示提高效率。权限系统用不同的位表示不同的权限如读、写、执行、删除一个用户的权限可以用一个整数表示检查权限时用与运算即可。#define PERM_READ (1 0) // 0001 #define PERM_WRITE (1 1) // 0010 #define PERM_EXEC (1 2) // 0100 #define PERM_DEL (1 3) // 1000 int user_perm PERM_READ | PERM_WRITE; // 用户有读和写权限即 0011 // 检查是否有写权限 if (user_perm PERM_WRITE) { printf(有写权限\n); } // 添加执行权限 user_perm | PERM_EXEC; // 移除写权限 user_perm ~PERM_WRITE;4.2 快速乘除与幂运算利用移位运算左移右移可以快速进行2的幂次方的乘除。a n等价于a * (2^n)a n等价于a / (2^n)注意对于有符号负数右移是算术右移高位补符号位并非严格的除以2^n。对于无符号数或正数逻辑右移等价于除以2^n。快速幂算法计算a^b的高效算法其核心思想就是利用指数的二进制表示和位运算。例如计算3^1313的二进制是1101即13 8 4 1。那么3^13 3^8 * 3^4 * 3^1。算法通过不断平方底数a a * a并根据指数b的当前最低位是否为1来决定是否乘入结果。long long fastPow(long long a, long long b) { long long result 1; while (b 0) { if (b 1) { // 如果b的当前最低位是1 result * a; } a * a; // 底数平方 b 1; // 指数右移一位 } return result; }4.3 位运算实现集合论操作与趣味题目判断一个数是否是2的幂如果一个正整数n是2的幂那么它的二进制表示中有且仅有一个1。例如8 (1000)16 (10000)。利用n (n-1)的技巧可以快速判断。bool isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }原理如果n是2的幂比如1000那么n-1就是0111。两者相与结果为0。如果n不是2的幂比如1010那么n-1是1001相与结果为1000不为0。计算一个整数的二进制表示中1的个数Population Count这是一个经典问题。int countBits(int n) { int count 0; while (n) { n (n - 1); // 每次操作消去n二进制表示中最低位的1 count; } return count; }原理n (n-1)这个操作每次都能将n最低位的1变成0。循环直到n为0循环次数就是1的个数。比逐位检查要高效。不用比较运算符找出两个数中的较大/较小值利用位运算和算术运算的特性。// 方法之一利用差值符号位。注意此方法可能溢出需谨慎使用。 int max(int a, int b) { // 计算 (a - b) 的符号位。在32位系统中右移31位得到符号位0或-1。 int sign (a - b) 31; // 如果absign0如果absign-1所有位全1 // 当sign0时a (a-b)*0 a当sign-1时a (a-b)*(-1) b return a sign * (a - b); // 更稳健但复杂的方法需要处理溢出这里仅展示思路。 }5. 常见问题、陷阱与深度思考即使理解了原理在实际编码中位运算仍然有许多细节需要注意否则极易产生隐蔽的Bug。5.1 符号位与移位操作的陷阱这是位运算中最容易出错的地方主要发生在有符号数的右移和取反操作上。算术右移 vs 逻辑右移逻辑右移无论符号位是0还是1高位都补0。C/C中对无符号整数进行右移是逻辑右移。算术右移高位补符号位。C/C中对有符号整数进行右移大多数编译器实现为算术右移这是标准允许的但非强制不过几乎所有现代平台都如此。int a -8; // 补码1111...1111 1000 (32位) int b a 2; // 算术右移2位高位补1结果1111...1111 1110即 -2 unsigned int c (unsigned int)a; // 数值变为一个很大的正数4294967288 unsigned int d c 2; // 逻辑右移2位高位补0结果是一个正数 printf(%d %u\n, b, d); // 输出 -2 和 1073741822教训当你想进行除以2的幂运算时如果操作数可能为负直接使用右移得到的是向负无穷取整的除法-3 1 -2而数学除法-3 / 2在C语言中是向零取整-1。两者结果不同左移的未定义行为对于有符号数如果左移后发生符号位改变即溢出在C/C标准中是未定义行为。这意味着编译器可以做任何事情程序可能崩溃或产生任意结果。对于无符号数左移是定义良好的溢出部分被丢弃。int a 0x40000000; // 2^30 a a 2; // 左移后理论上应为0x100000000但符号位改变这是未定义行为 unsigned int b 0x40000000; b b 2; // 定义良好结果为0x00000000溢出丢弃最佳实践进行移位操作时尽量使用无符号整数类型如unsigned int除非你非常清楚自己在做什么并且能确保不会触发未定义行为。5.2 运算符优先级带来的坑位运算符的优先级通常低于比较运算符和算术运算符。忘记加括号是常见的错误来源。int a 1, b 2, c 3; int result1 a b c; // 错误等价于 a (b c)因为 优先级高于 int result2 (a b) c; // 正确写法 int flag 0x01; if (flag 0x03 ! 0) { ... } // 错误等价于 flag (0x03 ! 0)永远为真或假 if ((flag 0x03) ! 0) { ... } // 正确写法安全建议只要涉及位运算与其他运算符混用一律加上括号不要依赖记忆优先级。5.3 关于“异或高斯消元”与“异或校验”的延伸标题的热搜词提到了“异或高斯消元”和“异或校验”这里简要解释其联系。异或校验如前所述它是一种简单、快速的错误检测方法。由于其线性性质异或运算是线性运算它被广泛用于网络通信如IP包头校验和、存储系统如RAID 5等场景。但它只能检测奇数个位错误无法纠正错误也不能检测偶数个位错误。异或高斯消元这是在解异或方程组时用到的一种算法。所谓异或方程组就是所有方程中的变量系数和常数都是0或1运算规则是异或。例如x1 ^ x2 ^ x3 1 x1 ^ x3 0 x2 ^ x3 1这类方程组在密码学、逻辑电路设计、某些图论问题中会出现。解法和普通的高斯消元法类似但因为运算只有异或可以用位运算如bitset来高效实现时间复杂度可以优化到O(n^2/word_size)其中word_size是机器字长如64位。这是算法竞赛中的一个高级技巧。5.4 浮点数的位运算热搜词中出现了“float异或校验”。这是一个需要极度小心的领域。在C/C中直接对float或double进行位运算如,|,^,~是不合法的因为位运算符的操作数必须是整数类型。如果你想操作浮点数的二进制表示必须通过类型转换type-punning将其底层的内存解释为整数。常用的方法是使用union或memcpy。union FloatIntUnion { float f; unsigned int i; // 假设float是32位 }; union FloatIntUnion u; u.f 3.14f; unsigned int bits u.i; // 现在可以对bits进行位运算了 // ... 对bits进行异或校验等操作 ... u.i bits; // 再转换回去 float new_float u.f; // 注意这可能会产生NaN或非规格化数甚至触发硬件异常警告这种操作破坏了类型安全极易引入未定义行为、平台依赖性问题如字节序以及对特殊值NaN无穷大的错误处理。除非你在进行极其底层的系统编程、数值分析或特定格式的编解码并且完全清楚后果否则绝对不要在普通应用中对浮点数进行位运算。对于浮点数的校验通常使用基于其数值的校验和如相加或专门的CRC算法更为安全可靠。掌握位运算和补码就像是获得了与计算机硬件直接对话的能力。它不仅能让你写出更高效、更简洁的代码更能从根本上深化你对程序运行机制的理解。从判断奇偶性到状态压缩DP从交换两个变量到理解整数溢出的本质这些知识无处不在。我个人的体会是花时间彻底弄懂这些“底层”概念远比盲目学习更多高级框架和工具来得划算它是你技术栈中一块坚实的地基能让你在遇到复杂问题时多一种清晰而有力的解决思路。下次当你看到n (n-1)这样的表达式时希望你能会心一笑并自信地运用它。
![[具身智能-181]：PC+服务器+具身机器人：构建具身智能从仿真到量产的闭环迭代混合架构](http://pic.xiahunao.cn/yaotu/[具身智能-181]：PC+服务器+具身机器人：构建具身智能从仿真到量产的闭环迭代混合架构)
