算法运位算

目录

常见位运算总结

原码 → 反码 → 补码

原码

示例（8 位）

表示范围（8 位）

原码的致命缺陷

反码

规则

示例（8 位）

反码的优势：加法可以统一

反码的缺陷

补码——现代计算机的标准

规则

示例（8 位）

负数补码的快速求法

补码的本质理解（面试高分点）

对比表（以 -5 为例，8 位）

基础位运算

左移运算（<<）

运算规则

示例

右移运算（>>）

运算规则

按位取反（~）

运算规则

示例

& | ^

给一个数 n，确定它的二进制表示中的第 x 位是 0 还是 1

将一个数 n 的二进制表示的第 x 位修改成 1

将一个数 n 的二进制表示的第 x 位修改成 0

位图的思想

提取一个数(n)二进制表示中最右侧的 1

​编辑

干掉一个数(n)二进制表示中最右侧的 1

位运算的优先级

异或(^)运算的运算律

题目：

判断字符是否唯⼀（easy）

解法（位图的思想）

丢失的数字（easy）

解法（位运算）

哈希表

高斯求和

两整数之和（medium）

​编辑

前置知识：半加器原理

加法：迭代进位法

减法：转换为加法

只出现⼀次的数字II（medium）

只出现一次的数字 III

第一步：全部异或，得到 a ^ b

第二步：找到 a 和 b 不同的那一位

第三步：按这一位分组异或

消失的两个数字（hard）

解法（位运算）

常见位运算总结

原码 → 反码 → 补码

计算机需要表示负数，但电路只有 0 和 1。如何用二进制表示负数？这就是原码 → 反码 → 补码的演进过程。

关键前提：固定字长

所有讨论都基于固定位数（如 8 位、32 位）。如果用 8 位表示一个整数，最高位（最左位）作为符号位

[符号位] [数值位]
↑ ↑
0=正 剩余7位表示大小
1=负

原码

最高位是符号位（0 正 1 负），其余位是数值的绝对值。

示例（8 位）

+5 的原码: 0 0000101
-5 的原码: 1 0000101
+0 的原码: 0 0000000
-0 的原码: 1 0000000 ← 问题来了：有两个零！

表示范围（8 位）

最大: 0 1111111 = +127
最小: 1 1111111 = -127
范围: -127 ~ +127

原码的致命缺陷

缺陷一：零的表示不唯一

+0 = 00000000
-0 = 10000000

这导致比较判断混乱：+0 == -0在数学上成立，但在原码中两个位模式不同。

缺陷二：减法运算极其复杂

5 + (-5) 用原码直接加:
00000101
+ 10000101
-----------
10001010 → 原码表示 -10，不是 0！

必须设计两套电路：一套做加法，一套做减法，然后根据符号位判断走哪套。

反码

规则

• 正数：反码 = 原码（不变）
• 负数：符号位不变，数值位全部取反

示例（8 位）

反码的优势：加法可以统一

反码的缺陷

缺陷一：仍然有 +0 和 -0 两个零

缺陷二：需要"循环进位"（end-around carry），硬件实现仍然不方便

反码是原码到补码的过渡方案，解决了加法统一的问题，但零不唯一和循环进位的问题仍待解决。面试中简单提及即可，重点是补码。

补码——现代计算机的标准

规则

• 正数：补码 = 原码（不变）
• 负数：在反码的基础上+1（即：原码取反再加 1）

示例（8 位）

+5 的原码: 0 0000101 → 反码: 0 0000101 → 补码: 0 0000101
-5 的原码: 1 0000101 → 反码: 1 1111010 → 补码: 1 1111011

+0: 00000000
-0: 原码 10000000 → 反码 11111111 → 补码 00000000（溢出丢弃，变成 00000000）
↑ 零的表示唯一了！

负数补码的快速求法

方法一：原码取反加 1

-5:
原码: 10000101
取反: 11111010
加 1: 11111011 ← -5 的补码

方法二：从右往左找到第一个 1，这个 1 及其右边的所有位保持不变，这个 1 左边的所有位全部取反。

+5: 00000101
↑ 第一个 1（从右数）
左边取反: 11111011 ← 这就是 -5 的补码

更直观地看:
00000101 (+5)
→ 找到最右边的 1: 000001[0]1
→ 左边全部取反: 111110[0]1
→ 结果: 11111011 (-5 的补码) ✓

补码的本质理解（面试高分点）

补码的本质是"模运算"。

以时钟类比：12 小时制的时钟上，往前拨 10 小时和往后拨 2 小时，结果一样。因为10 + 2 = 12（模），它们互为补数。

同理，在 8 位系统中，模 = 2⁸ = 256：

-5 的补码 = 256 - 5 = 251 = 11111011₂

所以做 3 + (-5) 等价于:
3 + 251 = 254
254 mod 256 = 254
254 = 11111110₂
解读补码: 取反加1 → 00000010 = 2 → -2 ✓

这就是为什么叫"补"码——负数用它相对于模的补数来表示。这种设计让加法和减法可以用同一套电路完成，a - b只需要a + (-b的补码)即可。

对比表（以 -5 为例，8 位）

基础位运算

左移运算（<<）

运算规则

将二进制数的所有位向左移动 N 位，高位丢弃，低位补 0。

数学等价：对于无溢出的情况，左移 N 位等价于乘以 2^N。

示例

以5 << 2为例（假设 8 位表示）：

右移运算（>>）

运算规则

将二进制数的所有位向右移动 N 位，低位丢弃，高位的填充方式取决于有无符号：

数学等价：右移 N 位等价于除以 2^N 并向负无穷取整（注意不是向零取整）

按位取反（~）

运算规则

对二进制数的每一位取反：0 变 1，1 变 0。这是一个一元运算符。

数学公式（基于补码表示）：~x = -(x + 1)

示例

以~5为例（8 位）：

以~0为例：

& | ^

无进位相加：对两个二进制数的每一位独立地做加法，但只保留本位的结果，不把进位传递给高位。

普通的二进制加法，每一位相加时可能出现三种情况：

0 + 0 = 0，没有进位，本位结果是 0。

0 + 1 或 1 + 0 = 1，没有进位，本位结果是 1。

1 + 1 = 10，产生进位——本位结果是 0，同时要向左边高位进一个 1。

普通加法在第 3 种情况下，会把进位传递给左边的高位，高位再参与运算，可能继续产生进位，层层传递。

无进位相加做的事情就是：前面两种情况完全一样，但在第 3 种情况（1 + 1）时，只记录本位结果 0，直接丢弃进位，不往高位传。

所以每一位的结果就是：

0 和 0 → 0

0 和 1 或 1 和 0 → 1

1 和 1 → 0（本位照常算，但进位直接扔掉）

把这四条摆在一起，发现它和异或的真值表完全一致。因此，异或运算在效果上就等价于无进位相加。

给一个数 n，确定它的二进制表示中的第 x 位是 0 还是 1

(n >> x) & 1，把第 x 位移到最低位再和 1 做与运算。例如 n=13（1101），要查第 2 位，(13 >> 2) & 1 = (0011) & 1 = 1。

将一个数 n 的二进制表示的第 x 位修改成 1

n | (1 << x)，用左移构造一个只有第 x 位为 1 的掩码，做或运算强制该位置 1。例如 n=9（1001），把第 1 位置 1：9 | (1 << 1) = 1001 | 0010 = 1011 = 11。

将一个数 n 的二进制表示的第 x 位修改成 0

n & ~(1 << x)，先构造第 x 位为 1 的掩码，取反后该位变 0 其余全 1，再做与运算清零该位。例如 n=13（1101），把第 2 位清零：13 & ~(1 << 2) = 1101 & 1011 = 1001 = 9。

位图的思想

本质就是哈希表

用一个二进制数的每一位表示一个元素是否存在（0 不存在，1 存在），用极小的空间实现集合的增删查。例如用一个 int 的 32 位可以表示 32 个不同元素的集合，查第 k 个元素是否存在就是bits & (1 << k)，添加就是bits |= (1 << k)，删除就是bits &= ~(1 << k)。

提取一个数(n)二进制表示中最右侧的 1

n & -n。在补码下-n = ~n + 1，取反后原来最右侧 1 的位置变成 0、右边全变 1，加 1 后恰好又变成 1，于是和原数相与只留下那个 1。例如 n=12（1100），-12的补码是…1110100，12 & -12 = 0100 = 4，正是最右侧 1 所在位的权值。

这道题和下一道题就能解决力扣里面的这三个问题。

干掉一个数(n)二进制表示中最右侧的 1

n & (n - 1)。减 1 会让最右侧的 1 变成 0、其右边的 0 全变成 1，再和原数做与运算，这个 1 及其右边就全清零了。例如 n=12（1100），12 & 11 = 1100 & 1011 = 1000 = 8。常用来统计二进制中 1 的个数（每次干掉一个，计数加一，直到 n=0）。

位运算的优先级

~最高，其次是<<和>>，然后是&，接着是^，最后是|。同级从左到右。所以n & 1 == 0会先算1 == 0再与 n，实际应写成(n & 1) == 0。位运算优先级普遍低于比较运算符，写复杂表达式时一律加括号最安全。

异或(^)运算的运算律

a ^ a = 0（自己异或自己归零）

a ^ 0 = a（和 0 异或不变）

交换律a ^ b = b ^ a

结合律a ^ (b ^ c) = (a ^ b) ^ c。

核心推论是a ^ b ^ b = a，一个数异或另一个数两次等于还原。经典应用：找数组中唯一出现一次的数（其余都出现两次），全异或一遍，成对的全抵消为 0，剩下那个就是答案。

题目：

判断字符是否唯⼀（easy）

面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

解法（位图的思想）

算法思路：利用位图的思想，每一个比特位代表一个字符，一个 int 类型的变量的 32 位足够表示所有的小写字母。比特位里面如果是 0，表示这个字符没有出现过。比特位里面的值是 1，表示该字符出现过。

int i = ch - 'a'：ch是当前遍历到的字符，ch - 'a'把字母转成 0~25 的整数。比如'a' - 'a' = 0，'b' - 'a' = 1，'z' - 'a' = 25。这个i就是当前字符在位图中对应的位号。

if ((bitMap >> i & 1) == 1) return false： 这就是之前学的"确定第 x 位是 0 还是 1"。把 bitMap 右移 i 位，让第 i 位挪到最低位，然后和 1 做与运算。如果结果为 1，说明这个字母之前已经标记过了，也就是重复了，直接返回 false。

标记字符已出现（位图的"增"）

bitMap |= 1 << i: 检查通过后，把当前字符对应的位置 1，记录它出现过了。1 << i构造一个只有第 i 位是 1、其余全 0 的掩码，和 bitMap 做或运算，强制把第 i 位变成 1，其他位不受影响。

解法二，哈希表

class Solution { public: bool isUnique(string astr) { if (astr.size() > 26) return false; unordered_set<char> seen; for (auto ch : astr) { if (seen.count(ch)) return false; seen.insert(ch); } return true; } };

丢失的数字（easy）

268. 丢失的数字 - 力扣（LeetCode）

解法（位运算）

算法思路：设数组的大小为 n ，那么缺失之前的数就是 [0, n] ，数组中是在 [0, n] 中缺失一个数形成的序列。如果我们把数组中的所有数，以及 [0, n] 中的所有数全部异或在一起，那么根据异或运算的消消乐规律（a ^ a = 0），最终的异或结果应该就是缺失的数。

以示例 1 为例：nums = [3, 0, 1]，n = 3，完整序列是[0, 1, 2, 3]，缺了 2:

把两批数放一起：

数组里的数： 3, 0, 1
完整的 0~n： 0, 1, 2, 3

全部异或：

3 ^ 0 ^ 1 ^ 0 ^ 1 ^ 2 ^ 3

重新排列一下，把相同的数放一起：

0 ^ 0 ^ 1 ^ 1 ^ 3 ^ 3 ^ 2

0 ^ 0 = 0（出现两次，抵消）

1 ^ 1 = 0（出现两次，抵消）

3 ^ 3 = 0（出现两次，抵消）

2只出现一次，没人跟它抵消

0 ^ 0 ^ 0 ^ 2 = 2.结果就是 2，也就是缺失的那个数字。

再提供一下几个其他的解法。

哈希表

思路：把数组所有数存入哈希集合，然后从 0 到 n 逐个查，哪个不在集合里就是答案。

class Solution { public: int missingNumber(vector<int>& nums) { int n = nums.size(); unordered_set<int> seen; // 把数组中所有数存入哈希表 for (int num : nums) seen.insert(num); // 从 0 到 n 逐个检查 for (int i = 0; i <= n; i++) { if (!seen.count(i)) return i; } return -1; } };

高斯求和

思路：如果一个都没丢，0 + 1 + 2 + ... + n = n × (n+1) / 2。现在丢了一个，用理论和减去实际和，差值就是丢失的数。

class Solution { public: int missingNumber(vector<int>& nums) { int n = nums.size(); // 理论和：0+1+2+...+n int expected = n * (n + 1) / 2; // 实际和：数组中所有数之和 int actual = 0; for (int num : nums) actual += num; return expected - actual; } };

两整数之和（medium）

371. 两整数之和 - 力扣（LeetCode）

前置知识：半加器原理

计算机底层用门电路做加法，最小单元叫"半加器"（Half Adder），它处理两个单比特相加：

观察上表：

• Sum 列恰好就是 A ^ B（异或：相同为 0，不同为 1）
• Carry 列恰好就是 A & B（与：两个都是 1 才得 1）

这就是位运算实现加法的数学根基。

加法：迭代进位法

核心公式

a + b = (a ^ b) + ((a & b) << 1)

然后把这两个结果再次相加（递归或迭代），直到进位为 0。

例子：5+3

5 = 0101
3 = 0011

第一轮：

a = 0101 (5)
b = 0011 (3)

a ^ b = 0110 → 6 （不考虑进位的和）
(a & b) << 1 = (0001) << 1 = 0010 → 2 （进位）

新的 a = 6, b = 2

第二轮：

a = 0110 (6)
b = 0010 (2)

a ^ b = 0100 → 4
(a & b) << 1 = (0010) << 1 = 0100 → 4

新的 a = 4, b = 4

.......

第四轮：

a = 0000 (0)
b = 1000 (8)

a ^ b = 1000 → 8
(a & b) << 1 = 0000 → 0 ← 进位为 0，终止！

结果 = 8 ✓ (5 + 3)

减法：转换为加法

核心公式

a - b = a + (-b) = a + (~b + 1)

计算机中负数用补码表示：-b = ~b + 1（取反加一）。

补码的巧妙之处在于，它让 CPU 只用一套加法电路就能同时处理加法和减法，无需额外的减法器。

步骤

1. 对减数取反：~b
2. 加一得到补码：~b + 1（这个 +1 也必须用前面的加法函数实现）
3. 调用加法函数：add(a, ~b + 1)

只出现⼀次的数字II（medium）

137. 只出现一次的数字 II - 力扣（LeetCode）

解法（比特位计数）

算法思路：设要找的数的位 ret。由于整个数组中，需要找的元素只出现了一次，其余的数都出现的三次，因此我们可以根据所有数的某一个比特位的总和 % 3 的结果，快速定位到 ret 的一个比特位上的值是 0 还是 1。这样，我们通过 ret 的每一个比特位上的值，就可以将 ret 给还原出来

想要的最终答案是一个数字，比如答案是 3。但这道题不能直接找数字，因为题目限制了你不能用常规方法（比如排序、哈希表），只允许 O(1) 空间。

所以得换个思路：我不直接找这个数字，而是把这个数字的每一位"猜"出来，最后拼成完整答案。

打个比方：你要猜一个人的电话号码 138****5678，但不能直接看。怎么办？你一位一位地猜，先猜第 1 位是 1，再猜第 2 位是 3……最后拼起来就是完整号码。

这道题完全一样：答案是某个数字，我先猜它的第 0 位是几，再猜第 1 位是几……猜完 32 位拼起来就是答案。

先看所有数字的第 0 位（最右边那一位）

题目说数组[2, 2, 3, 2]，里面 2 出现了 3 次，3 出现了 1 次。每个数字的第 0 位分别是：

把这 4 个数加起来：0 + 0 + 1 + 0 = 1.然后对 3 取余数1 ÷ 3 = 0余1这个余数 1，就是答案的第 0 位。

为什么余数就是答案？这是核心！数组里有两类数字：

• 出现 3 次的：2, 2, 2
• 出现 1 次的：3（这就是答案）

对于第 0 位

总和 = 0 + 1 = 1

出现 3 次的那些数字，它们在每一位上的贡献一定是 3 的倍数（因为出现了 3 次）。3 的倍数除以 3 余 0，取余后就没了。所以总和 % 3= 答案在那一位的值。出现 3 次的数字被取余消掉了，剩下的就是出现 1 次的那个数字的贡献。

再看第 1 位，重复同样的操作

加起来：1 + 1 + 1 + 1 = 4.对 3 取余：4 ÷ 3 = 1余1答案的第 1 位 = 1。

第 2 位、第 3 位……同理

更高位全是 0，不写了。

答案第 0 位 = 1
答案第 1 位 = 1
答案第 2 位 = 0
答案第 3 位 = 0
……更高位都是 0

从低到高拼起来：0011（二进制）=3（十进制）答案就是 3。

只出现一次的数字 III

260. 只出现一次的数字 III - 力扣（LeetCode）

第一步：全部异或，得到 a ^ b

把数组里所有数异或在一起。出现两次的数字x ^ x = 0全部抵消，最后只剩下两个出现一次的数字的异或结果。

1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
= (1^1) ^ (2^2) ^ 3 ^ 5
= 0 ^ 0 ^ 3 ^ 5
= 3 ^ 5
= 011 ^ 101
= 110

tmp = 110，这就是a ^ b

第二步：找到 a 和 b 不同的那一位

tmp = 110，第 1 位是 1，说明 a 和 b 在第 1 位不同。

3 = 011 → 第 1 位 = 1
5 = 101 → 第 1 位 = 0

diff = 1。

第三步：按这一位分组异或

把所有数按第 1 位分两组，各自异或：

第 1 位 = 0 的组：

1 = 01 → 第1位 = 0
1 = 01 → 第1位 = 0
5 = 101 → 第1位 = 0

异或：1 ^ 1 ^ 5 = 0 ^ 5 = 5 ← 得到 b

第 1 位 = 1 的组：

2 = 10 → 第1位 = 1
3 = 011 → 第1位 = 1
2 = 10 → 第1位 = 1

异或：2 ^ 2 ^ 3 = 0 ^ 3 = 3 ← 得到 a

结果：[3, 5]

消失的两个数字（hard）

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

解法（位运算）

算法思路：本题就是268.丢失的数字+260.只出现一次的数字III组合起来的题。先将数组中的数和 [1, n + 2] 区间内的所有数异或在一起，问题就变成了：有两个数出现了一次，其余所有的数出现了两次。进而变成了260.只出现一次的数字III这道题。

详细解释：

将所有的数异或在一起，tmp：所有的数"指的是两批数——数组nums里的数，加上1到N的所有数。把它们全部异或在一起，得到一个结果tmp。为什么tmp = a ^ b？因为没丢的数字在 nums 里出现一次、在 1~N 里也出现一次，共两次，异或两次等于 0，全部抵消。而丢失的 a 和 b 只在 1~N 里出现，nums 里没有，所以抵消不掉，最后tmp就等于a ^ b。

找到 tmp 中，比特位上为 1 的那一位：tmp = a ^ b，异或的规则是相同为 0、不同为 1。所以 tmp 里为 1 的那些位，就是 a 和 b 取值不同的位。我们从 tmp 的二进制里找到一个为 1 的位，把它的位置记下来叫 x。这一步的目的就是：找到 a 和 b 在哪一位不一样。

根据 x 位的不同，划分成两类异或：拿上一步找到的第 x 位当标准，把所有数（nums 的 + 1~N 的）分成两类：

• 第 x 位是 0 的，归一类，异或在一起
• 第 x 位是 1 的，归一类，异或在一起

因为 a 和 b 在第 x 位不同，一个是 0 一个是 1，所以它们会被分到不同的类里。而其他数字每个都出现两次，同一个数在第 x 位的值是固定的，所以两次都进同一类，异或后抵消。最后每类里只剩下 a 或 b 自己，分别异或到两个变量里，就得到了答案。