面试题 05.01. 插入

给定两个整型数字 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)

Python 解答：

class Solution:
    def insertBits(self, N: int, M: int, i: int, j: int) -> int:
        def transform(n):
            res = []
            while n > 0:
                r = n&1
                res.append(r)
                n >>= 1
            return res
        def retransform(arr):
            res = 0
            for item in arr[::-1]:
                res <<= 1
                res += item
            return res

        N_bits = transform(N)
        while len(N_bits) < j+1:
            N_bits.append(0)
        M_bits = transform(M)

        for k in range(len(M_bits)):
            N_bits[i+k] = M_bits[k]
        for k in range(i+len(M_bits), j+1):
            N_bits[k] = 0

        return retransform(N_bits)