跳转至

面试题 05.01. 插入

题目描述

插入。给定两个32位的整数N与M，以及表示比特位置的i与j。编写一种方法，将M插入N，使得M从N的第j位开始，到第i位结束。假定从j位到i位足以容纳M，也即若M = 10 011，那么j和i之间至少可容纳5个位。例如，不可能出现j = 3和i = 2的情况，因为第3位和第2位之间放不下M。

示例1:

 输入：N = 10000000000, M = 10011, i = 2, j = 6
 输出：N = 10001001100

示例2:

 输入： N = 0, M = 11111, i = 0, j = 4
 输出：N = 11111

解法

方法一：位运算

思考

要把 \(M\) 插入 \(N\) 的第 \(i\) 到 \(j\) 位。若直接按位或，原区间里残留的 \(1\) 会干扰 \(M\) 的 \(0\) 位。

须先把 \([i,j]\) 清零，再把 \(M\) 对齐到第 \(i\) 位后并入。

对 \(k\in[i,j]\) 执行 \(N \&= \sim(1\ll k)\)，再返回 \(N \mid (M \ll i)\)。区间长度不超过字长，操作为位运算常数级。

我们先将 \(N\) 的第 \(i\) 位到第 \(j\) 位清零，然后再将 \(M\) 左移 \(i\) 位，最后将 \(M\) 与 \(N\) 进行或运算。

时间复杂度 \(O(\log n)\)，其中 \(n\) 是 \(N\) 的大小。空间复杂度 \(O(1)\)。

1
2
3
4
5
class Solution:
    def insertBits(self, N: int, M: int, i: int, j: int) -> int:
        for k in range(i, j + 1):
            N &= ~(1 << k)
        return N | M << i

1
2
3
4
5
6
7
8
class Solution {
    public int insertBits(int N, int M, int i, int j) {
        for (int k = i; k <= j; ++k) {
            N &= ~(1 << k);
        }
        return N | M << i;
    }
}

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int insertBits(int N, int M, int i, int j) {
        for (int k = i; k <= j; ++k) {
            N &= ~(1 << k);
        }
        return N | M << i;
    }
};

1
2
3
4
5
6
func insertBits(N int, M int, i int, j int) int {
    for k := i; k <= j; k++ {
        N &= ^(1 << k)
    }
    return N | M<<i
}

1
2
3
4
5
6
function insertBits(N: number, M: number, i: number, j: number): number {
    for (let k = i; k <= j; ++k) {
        N &= ~(1 << k);
    }
    return N | (M << i);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    func insertBits(_ N: Int, _ M: Int, _ i: Int, _ j: Int) -> Int {
        var result = N

        for k in i...j {
            result &= ~(1 << k)
        }

        return result | (M << i)
    }
}

评论