题目难度: 简单
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。
编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。具体插入过程如图所示。
题目保证从 i 位到 j 位足以容纳 M， 例如： M = 10011，则 i ～ j 区域至少可容纳 5 位。
示例 1:
- 输入：N = 1024(10000000000), M = 19(10011), i = 2, j = 6
- 输出：N = 1100(10001001100)
示例 2:
- 输入： N = 0, M = 31(11111), i = 0, j = 4
- 输出：N = 31(11111)
题目思考
- 可以拆分成哪些过程?
解决方案
思路
- 分析题目, 比较容易可以想到, 我们可以先把数字 N 的第 i ~ j 位区域 清 0, 然后再将 M 左移 i 位, 最后 取或 即可得到最终结果
- 这里左移和取或都是非常直接的位运算, 关键在于如何清 0
- 如果我们能够构造出第 i ~ j 位区域为 0 而其他位都为 1 的数字
mask, 那么只需要将它和 N 取交, 即可将这部分区域清 0 - 直接构造这个数字不太方便, 我们可以反其道而行之, 先得到第 i ~ j 位区域为 1 而其他位都为 0 的数字
mask', 然后逐位取反 (~) 即可 - 这个数字
mask'如何得到呢? 注意到这个区域的长度 length 为 j-i+1, 所以我们可以利用(1<<length) - 1得到从低位到高共计 length 个 1 的数字, 然后左移 i 位即可 - 下面的代码对应了上面描述的完整过程, 只是将一些中间步骤合并在了一起, 更加简洁一些; 大家也可以将每一步分开来, 这样更便于理解
复杂度
- 时间复杂度 O(1): 只使用了几个常数空间的变量
- 空间复杂度 O(1): 只进行了几个常数级别的位运算操作
代码
class Solution:
def insertBits(self, N: int, M: int, i: int, j: int) -> int:
# 清0 + 左移取或
# mask代表[i,j]之间的位为0, 其他位为1的数字
mask = ~(((1 << (j - i + 1)) - 1) << i)
# N & mask将i到j之间的位清0, 然后将M左移i位, 并与N取或, 即得到最终结果
return (N & mask) | (M << i) 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号