算法运位算

目录常见位运算总结原码 → 反码 → 补码原码示例8 位表示范围8 位原码的致命缺陷反码规则示例8 位反码的优势加法可以统一反码的缺陷补码——现代计算机的标准规则示例8 位负数补码的快速求法补码的本质理解面试高分点对比表以 -5 为例8 位基础位运算左移运算运算规则示例右移运算运算规则按位取反~运算规则示例 | ^给一个数 n确定它的二进制表示中的第 x 位是 0 还是 1将一个数 n 的二进制表示的第 x 位修改成 1将一个数 n 的二进制表示的第 x 位修改成 0位图的思想提取一个数(n)二进制表示中最右侧的 1​编辑干掉一个数(n)二进制表示中最右侧的 1位运算的优先级异或(^)运算的运算律题目判断字符是否唯⼀easy解法位图的思想丢失的数字easy解法位运算哈希表高斯求和两整数之和medium​编辑前置知识半加器原理加法迭代进位法减法转换为加法只出现⼀次的数字IImedium只出现一次的数字 III第一步全部异或得到 a ^ b第二步找到 a 和 b 不同的那一位第三步按这一位分组异或消失的两个数字hard解法位运算常见位运算总结原码 → 反码 → 补码计算机需要表示负数但电路只有 0 和 1。如何用二进制表示负数这就是原码 → 反码 → 补码的演进过程。关键前提固定字长所有讨论都基于固定位数如 8 位、32 位。如果用 8 位表示一个整数最高位最左位作为符号位[符号位] [数值位]↑ ↑0正 剩余7位表示大小1负原码最高位是符号位0 正 1 负其余位是数值的绝对值。示例8 位5 的原码: 0 0000101-5 的原码: 1 00001010 的原码: 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 位5 的原码: 0 0000101 → 反码: 0 0000101正数不变-5 的原码: 1 0000101 → 反码: 1 1111010数值位取反0 的反码: 0 0000000-0 的反码: 1 1111111 ← 仍然有两个零反码的优势加法可以统一5 (-5) 用反码加:00000101 (5 的反码) 11111010 (-5 的反码)11111111 → 这是 -0 的反码结果正确值确实是 0反码的缺陷缺陷一仍然有 0 和 -0 两个零0 00000000-0 11111111缺陷二需要循环进位end-around carry硬件实现仍然不方便反码是原码到补码的过渡方案解决了加法统一的问题但零不唯一和循环进位的问题仍待解决。面试中简单提及即可重点是补码。补码——现代计算机的标准规则正数补码 原码不变负数在反码的基础上1即原码取反再加 1示例8 位5 的原码: 0 0000101 → 反码: 0 0000101 → 补码: 0 0000101-5 的原码: 1 0000101 → 反码: 1 1111010 → 补码: 1 11110110: 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 254254 mod 256 254254 11111110₂解读补码: 取反加1 → 00000010 2 → -2 ✓这就是为什么叫补码——负数用它相对于模的补数来表示。这种设计让加法和减法可以用同一套电路完成a - b只需要a (-b的补码)即可。对比表以 -5 为例8 位编码方式-5 的表示正数规则负数规则零的表示原码10000101不变符号位置 1数值位不变00000000和10000000两个零反码11111010不变符号位不变数值位取反00000000和11111111两个零补码11111011不变反码 100000000唯一零基础位运算左移运算运算规则将二进制数的所有位向左移动 N 位高位丢弃低位补 0。数学等价对于无溢出的情况左移 N 位等价于乘以 2^N。示例以5 2为例假设 8 位表示5 的二进制: 0000 0101左移 2 位: 0001 0100 → 十进制 20验证: 5 × 2² 5 × 4 20 ✓右移运算运算规则将二进制数的所有位向右移动 N 位低位丢弃高位的填充方式取决于有无符号类型高位填充方式名称无符号数unsigned补0逻辑右移有符号数signed补符号位算术右移数学等价右移 N 位等价于除以 2^N 并向负无穷取整注意不是向零取整按位取反~运算规则对二进制数的每一位取反0 变 11 变 0。这是一个一元运算符。数学公式基于补码表示~x -(x 1)示例以~5为例8 位5 的二进制: 0000 0101取反: 1111 1010 → 这是一个负数需要解读补码补码解读:1111 1010 取反加 1 → 0000 0101 1 0000 0110 6所以原值为 -6验证: ~5 -(5 1) -6 ✓以~0为例0 的二进制: 0000 0000取反: 1111 1111补码解读: 1111 1111 取反加 1 → 0000 0001 1所以原值为 -1验证: ~0 -(0 1) -1 ✓运算符号规则数学等价面试陷阱左移x n低位补 0高位丢弃x × 2ⁿ溢出后结果回绕右移x n无符号补 0有符号补符号位x ÷ 2ⁿ向负无穷取整C 中有符号右移是实现定义与整数除法取整方向可能不同取反~x每位翻转-(x 1)结果始终为负当 x ≥ 0用于构造掩码、判断 -1 | ^无进位相加对两个二进制数的每一位独立地做加法但只保留本位的结果不把进位传递给高位。普通的二进制加法每一位相加时可能出现三种情况0 0 0没有进位本位结果是 0。0 1 或 1 0 1没有进位本位结果是 1。1 1 10产生进位——本位结果是 0同时要向左边高位进一个 1。普通加法在第 3 种情况下会把进位传递给左边的高位高位再参与运算可能继续产生进位层层传递。无进位相加做的事情就是前面两种情况完全一样但在第 3 种情况1 1时只记录本位结果 0直接丢弃进位不往高位传。所以每一位的结果就是0 和 0 → 00 和 1 或 1 和 0 → 11 和 1 → 0本位照常算但进位直接扔掉把这四条摆在一起发现它和异或的真值表完全一致。因此异或运算在效果上就等价于无进位相加。给一个数 n确定它的二进制表示中的第 x 位是 0 还是 1(n x) 1把第 x 位移到最低位再和 1 做与运算。例如 n131101要查第 2 位(13 2) 1 (0011) 1 1。将一个数 n 的二进制表示的第 x 位修改成 1n | (1 x)用左移构造一个只有第 x 位为 1 的掩码做或运算强制该位置 1。例如 n91001把第 1 位置 19 | (1 1) 1001 | 0010 1011 11。将一个数 n 的二进制表示的第 x 位修改成 0n ~(1 x)先构造第 x 位为 1 的掩码取反后该位变 0 其余全 1再做与运算清零该位。例如 n131101把第 2 位清零13 ~(1 2) 1101 1011 1001 9。位图的思想本质就是哈希表用一个二进制数的每一位表示一个元素是否存在0 不存在1 存在用极小的空间实现集合的增删查。例如用一个 int 的 32 位可以表示 32 个不同元素的集合查第 k 个元素是否存在就是bits (1 k)添加就是bits | (1 k)删除就是bits ~(1 k)。提取一个数(n)二进制表示中最右侧的 1n -n。在补码下-n ~n 1取反后原来最右侧 1 的位置变成 0、右边全变 1加 1 后恰好又变成 1于是和原数相与只留下那个 1。例如 n121100-12的补码是…111010012 -12 0100 4正是最右侧 1 所在位的权值。这道题和下一道题就能解决力扣里面的这三个问题。干掉一个数(n)二进制表示中最右侧的 1n (n - 1)。减 1 会让最右侧的 1 变成 0、其右边的 0 全变成 1再和原数做与运算这个 1 及其右边就全清零了。例如 n12110012 11 1100 1011 1000 8。常用来统计二进制中 1 的个数每次干掉一个计数加一直到 n0。位运算的优先级~最高其次是和然后是接着是^最后是|。同级从左到右。所以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 - ach是当前遍历到的字符ch - a把字母转成 0~25 的整数。比如a - a 0b - a 1z - 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_setchar seen; for (auto ch : astr) { if (seen.count(ch)) return false; seen.insert(ch); } return true; } };丢失的数字easy268. 丢失的数字 - 力扣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 ^ 20 ^ 0 0出现两次抵消1 ^ 1 0出现两次抵消3 ^ 3 0出现两次抵消2只出现一次没人跟它抵消0 ^ 0 ^ 0 ^ 2 2.结果就是 2也就是缺失的那个数字。再提供一下几个其他的解法。哈希表思路把数组所有数存入哈希集合然后从 0 到 n 逐个查哪个不在集合里就是答案。class Solution { public: int missingNumber(vectorint nums) { int n nums.size(); unordered_setint 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 × (n1) / 2。现在丢了一个用理论和减去实际和差值就是丢失的数。class Solution { public: int missingNumber(vectorint nums) { int n nums.size(); // 理论和012...n int expected n * (n 1) / 2; // 实际和数组中所有数之和 int actual 0; for (int num : nums) actual num; return expected - actual; } };两整数之和medium371. 两整数之和 - 力扣LeetCode前置知识半加器原理计算机底层用门电路做加法最小单元叫半加器Half Adder它处理两个单比特相加ABSum和Carry进位0000011010101101观察上表Sum 列恰好就是 A ^ B异或相同为 0不同为 1Carry 列恰好就是 A B与两个都是 1 才得 1这就是位运算实现加法的数学根基。加法迭代进位法核心公式a b (a ^ b) ((a b) 1)部分运算含义a ^ b异或不考虑进位的各位相加结果(a b) 1与 左移所有进位左移是因为进位要加到高一位上然后把这两个结果再次相加递归或迭代直到进位为 0。例子535 01013 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 只用一套加法电路就能同时处理加法和减法无需额外的减法器。步骤对减数取反~b加一得到补码~b 1这个 1 也必须用前面的加法函数实现调用加法函数add(a, ~b 1)只出现⼀次的数字IImedium137. 只出现一次的数字 II - 力扣LeetCode代码解释x i把 x 右移 i 位把第 i 位挪到最右边(x i) 1和 1 做与运算取出第 i 位是 0 还是 11 i把 1 左移 i 位生成只有第 i 位是 1 的数ret | 1 i用或运算把 ret 的第 i 位设成 1解法比特位计数算法思路设要找的数的位 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 位分别是2 的第 0 位 0 因为 2 ...10最右边是 02 的第 0 位 03 的第 0 位 1 因为 3 ...11最右边是 12 的第 0 位 0把这 4 个数加起来0 0 1 0 1.然后对 3 取余数1 ÷ 3 0余1这个余数 1就是答案的第 0 位。为什么余数就是答案这是核心数组里有两类数字出现 3 次的2, 2, 2出现 1 次的3这就是答案对于第 0 位2 的第 0 位 0出现 3 次 → 贡献 000 0这是 3 的倍数3 的第 0 位 1出现 1 次 → 贡献 1总和 0 1 1出现 3 次的那些数字它们在每一位上的贡献一定是 3 的倍数因为出现了 3 次。3 的倍数除以 3 余 0取余后就没了。所以总和 % 3 答案在那一位的值。出现 3 次的数字被取余消掉了剩下的就是出现 1 次的那个数字的贡献。再看第 1 位重复同样的操作2 的第 1 位 1 2 ...10倒数第二位是 12 的第 1 位 13 的第 1 位 1 3 ...11倒数第二位是 12 的第 1 位 1加起来1 1 1 1 4.对 3 取余4 ÷ 3 1余1答案的第 1 位 1。第 2 位、第 3 位……同理2 的第 2 位 02 的第 2 位 03 的第 2 位 02 的第 2 位 0总和 00 % 3 0 → 答案第 2 位 0更高位全是 0不写了。答案第 0 位 1答案第 1 位 1答案第 2 位 0答案第 3 位 0……更高位都是 0从低到高拼起来0011二进制3十进制答案就是 3。题目变体其他数字出现次数目标数字出现次数怎么取模LeetCode 1362 次1 次% 2其实直接异或就行LeetCode 1373 次1 次% 3改编版4 次1 次% 4改编版5 次1 次% 5通用版N 次1 次% N只出现一次的数字 III260. 只出现一次的数字 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 110tmp 110这就是a ^ b第二步找到 a 和 b 不同的那一位tmp 110第 1 位是 1说明 a 和 b 在第 1 位不同。3 011 → 第 1 位 15 101 → 第 1 位 0diff 1。第三步按这一位分组异或把所有数按第 1 位分两组各自异或第 1 位 0 的组1 01 → 第1位 01 01 → 第1位 05 101 → 第1位 0异或1 ^ 1 ^ 5 0 ^ 5 5 ← 得到 b第 1 位 1 的组2 10 → 第1位 13 011 → 第1位 12 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 自己分别异或到两个变量里就得到了答案。