Question

面试题 05.01. 插入

English Version

题目描述

插入。给定两个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

解法

方法一：位运算

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

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

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

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;
  }
}

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;
  }
};

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

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);
}