LeetCode 面试题 05.01. 插入
目录
题目描述
题意分析
给两个 32 位整数
N和M，以及两个位下标i和j，要求把M原封不动地嵌进N的第i到第j位（含两端，下标从最低位起算），返回嵌入后的结果。题目保证
M的有效位数不超过j - i + 1，也就是说目标窗口一定装得下，不会出现截断或溢出。这条保证很关键：它让实现可以省掉「先检查M是否放得下」的分支，直接按位写入。「嵌入」的语义要读准——是覆盖而不是叠加。窗口内
N原有的比特必须被完全丢弃，换成M的比特；窗口外的所有比特必须原样保留，一位都不能动。这两句话直接对应实现里的两个动作：清空窗口、写入内容。边界：
i可能为 0，此时窗口贴着最低位，M无需移位；M可能为 0，此时相当于把窗口清零；窗口内N原本可能已是全 0，清空动作退化成空操作但不能省略；j最大到 31，移位次数始终在合法范围内。
解法：位运算压缩状态
核心思路
一个自然但错误的第一反应是直接
N | (M << i)：把M挪到位置上再或进去。它只在「窗口原本全为 0」时碰巧正确——或运算只能把 0 变成 1，无法把 1 变回 0，所以N在窗口里原有的 1 会残留下来，与M的比特混在一起。这个失败恰好点明了必须补上的那一步：写入之前先把窗口清干净。于是整个操作被拆成两个互不干扰的阶段。第一阶段，把
N的第i到第j位全部置 0，其余位保持不变；第二阶段，把M左移i位对齐到窗口，再用或写入。因为第一阶段已经保证窗口全 0，或运算在窗口内等价于赋值，在窗口外因为M << i的对应位为 0 而不产生任何影响——这就是两阶段能够拆开的理由。清零的手段是「取反后按位与」：
1 << k只有第k位是 1，取反后就只有第k位是 0、其余全 1，与N相与就精确地打掉第k位而不碰别处。代码用一个从i到j的循环逐位这样做，好处是不用推导区间掩码公式，读起来就是「把这几位一个个抹掉」，白板上不易写错。维护的状态很简单，就是
N本身：循环的不变量是「每执行完一轮，N的第i到第k位已被清零，其余位与入参完全一致」。循环结束时窗口全空，此时再或上M << i即得答案。
解题步骤
- 逐位清空窗口：
for (int k = i; k <= j; ++k) N &= ~(1 << k);。循环边界是闭区间，k <= j而不是k < j——题面的j是要被覆盖的最高位，漏掉它会让M的最高位无处安放。- 用取反与而不是异或：
N &= ~(1 << k)无论该位原本是 0 还是 1，结果都是 0，是幂等的清零；换成N ^= 1 << k会变成翻转，原本是 0 的位反被置 1。- 对齐后写入：
return N | M << i;。左移i位是把M的第 0 位对到窗口的最低位i，这也是为什么循环从i而不是从 0 开始清。- 无需处理越界：题目保证
M放得下，所以M << i不会有比特落到j之外，或运算不会污染窗口外的位；若没有这条保证，写入前需要先用掩码把M截断到j - i + 1位。- 运算符优先级：
M << i的优先级低于|吗？恰好相反，移位优先于按位或，所以N | M << i等价于N | (M << i)；不确定时加括号更稳。以题面示例
N = 1024、M = 19、i = 2、j = 6走一遍。二进制下N = 100 0000 0000（只有第 10 位是 1），M = 1 0011（占 5 位，窗口宽度6 - 2 + 1 = 5，恰好装下）。清空阶段：依次对
k = 2, 3, 4, 5, 6执行清零。N在这五位上原本就全是 0，所以每一轮N都不变，仍是100 0000 0000。这一步虽然没改变数值，但它是正确性的前提——换个窗口非空的N，它就是决定成败的一步。写入阶段：
M << 2把1 0011变成100 1100（十进制 76），它的最高位落在第 6 位、最低位落在第 2 位，正好填满窗口。或上N得100 0100 1100，十进制是1024 + 76 = 1100，与期望输出一致。再看一个窗口非空的对照：
N = 0b111111、M = 0、i = 2、j = 4。清空后N变成0b100011，写入0 << 2不改变任何位，结果就是0b100011。若省掉清空直接或，会原样返回0b111111，窗口里的三个 1 一个都没被覆盖掉。
代码实现
class Solution {
public int insertBits(int N, int M, int i, int j) {
// 先把窗口 [i, j] 逐位清零，或运算才等价于赋值。
for (int k = i; k <= j; ++k) {
N &= ~(1 << k);
}
return N | M << i;
}
}
func insertBits(N int, M int, i int, j int) int {
// 先把窗口 [i, j] 逐位清零，或运算才等价于赋值。
for k := i; k <= j; k++ {
N &= ^(1 << k)
}
return N | M<<i
}
复杂度分析
- 时间复杂度：$O(j - i)$，即窗口宽度，最坏为 32 次循环，因此也可以视作常数级；循环体内只有一次移位、一次取反、一次与运算。
- 空间复杂度：$O(1)$，全程只在入参
N上原地修改，没有任何额外结构。
关键点总结
- 位操作里的「覆盖」必须拆成「先清零，再或写入」两步，因为或只能置位不能复位；把这句话说出口，基本就答对了这道题的核心。
x &= ~(1 << k)清零、x |= 1 << k置位、x ^= 1 << k翻转、x >> k & 1取位，这四个基本动作是所有位运算题的字母表，要能不假思索地写出来。- 循环逐位清零胜在直白、白板上不易错；若面试官追问常数时间写法，标准答案是构造区间掩码
mask = ~(((1 << (j - i + 1)) - 1) << i)，一次与运算清空整个窗口，但要额外小心j - i + 1等于 32 时移位溢出的坑。- 左移
i位是把M的第 0 位对齐到窗口最低位，「对齐」这个词能帮你记住移位量必须是i而不是j或窗口宽度。- 题目保证
M放得下，所以省掉了截断；面试时最好主动确认这条前提，并说明若不保证则需要先M &= (1 << (j - i + 1)) - 1，这体现了对输入契约的敏感。
易错点总结
- 省掉清零直接或：
N = 0b111111、M = 0、i = 2、j = 4→ 返回0b111111，窗口内原有的 1 全部残留，正确结果应是0b100011。- 循环条件写成
k < j：N = 0、M = 0b11、i = 0、j = 1→ 第 1 位没被清零（本例恰好为 0 未暴露），换成N = 0b10时该位残留，结果多出一个 1。- 清零写成异或：
N = 0、M = 1、i = 0、j = 2→ 三次异或把原本为 0 的三位全翻成 1，N变成0b111，再或上M得0b111而不是0b001。- 移位量写成
j：N = 1024、M = 19、i = 2、j = 6→M << 6的最高位跑到第 10 位，与N原有的 1 撞在一起，返回值远大于 1100。- 移位量写成窗口宽度
j - i + 1：同一组用例 →M被挪到第 5 位起，整体偏移一格，低位空出一个 0。- 从第 0 位开始清：
N = 0b1011、M = 0、i = 2、j = 3→ 低两位被误清，返回0b0000而不是0b0011。- 用
1 << k时k达到 31 而变量是有符号类型：i = 31、j = 31→1 << 31是负数（最小值），取反后与运算虽仍能正确清零，但若写成1L << k与int混用则会因隐式转换丢掉高位。- 改用掩码写法时忽略宽度为 32 的情形：
i = 0、j = 31→1 << 32在 Java 中因移位量取模而等价于1 << 0，掩码算成 0，整个窗口清成空操作，结果错得毫无征兆。- 误以为要保留窗口内原值做叠加：
N = 0b1100、M = 0b01、i = 2、j = 3→ 若写成N + (M << i)得0b10000，进位污染了窗口外的位，而正确答案是覆盖成0b0100。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 面试题 05.07. 配对交换 | 简单 | 同为掩码操作，但用奇偶位掩码一次性拆分再拼回，无需逐位循环 |
| 面试题 05.06. 整数转换 | 简单 | 先异或定位差异位，再数 1 的个数，考的是位差异而非位覆盖 |
| 面试题 05.03. 翻转数位 | 简单 | 把整数当成 0/1 序列做窗口扫描，关注的是连续段而非固定区间 |
| 面试题 05.08. 绘制直线 | 中等 | 把区间置位推广到跨多个整数的位图上，多了下标定位这一层 |
| 190. 颠倒二进制位 | 简单 | 逐位取出再反向置位，可用分治掩码把 32 次循环压到 5 步 |
| 201. 数字范围按位与 | 中等 | 求区间内所有数的公共前缀，靠不断右移对齐而非构造掩码 |