插入

面试题 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)

题目描述有问题

在N的二进制数据的基础上（不是在32位2进制的基础上，即前面不含多余的0）替换从右往左数第i位到第j位的bit位为M的bit位，如果M的二进制（前面不含多余的0）的长度小于j-i,那么在M的高位补足0

class Solution {
    public int insertBits(int N, int M, int i, int j) {
        if (i > j) return 0;
        String s1 = Integer.toBinaryString(N);
        String s2 = Integer.toBinaryString(M);
        for (int index = s2.length(); index < j - i + 1; index++) {
            s2 = "0" + s2;
        }
        String prefix = "";
        String suffix = "";
        if (s1.length() - j - 1 >= 0) {
            prefix = s1.substring(0, s1.length() - j - 1);
        }
        if (s1.length() - i >= 0) {
            suffix = s1.substring(s1.length() - i, s1.length());
        }
        String res = prefix + s2 + suffix;
        return Integer.valueOf(res, 2);
    }
}

高效写写法

class Solution {
    public int insertBits(int N, int M, int i, int j) {
        String n = Integer.toBinaryString(N);
        String m = Integer.toBinaryString(M);
        StringBuilder sb = new StringBuilder();
        for (int x = 0; x < n.length() - j - 1; x++) {
            sb.append(n.charAt(x));
        }
        for (int x = 0; x < j - i + 1 - m.length(); x++) { 
            sb.append('0');
        }
        sb.append(m);          
        for (int x = n.length() - i; x < n.length(); x++) {
            sb.append(n.charAt(x));
        }
        return Integer.parseInt(sb.toString(), 2);
    }
}

位运算

• 先把数N的j到i之间的位置0
• M左移i位
• 再用N或运算M

  例 N = 1011 1111, M = 101, i = 2, j = 4
       (1<<(j-i+1))-1)<<i = 0001 1100 
  取反后
       1110 0011
  对N于运算
       1011 1111 & 1110 0011 = 1010 0011
  M左移动i位
      101 << i = 0001 0100
  最后M|N
      0001 0100 | 1010 0011 = 1011 0111 = 183
  
  作者：yechanghong
  链接：https://leetcode-cn.com/problems/insert-into-bits-lcci/solution/wei-yun-suan-bu-xun-huan-by-yechanghong/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

  public int insertBits(int N, int M, int i, int j) {
         int mask=((1<<(j-i+1))-1)<<i;
         mask=~mask;
         N&=mask;
         M=M<<i;
         return M|N;
     }
  
  作者：yechanghong
  链接：https://leetcode-cn.com/problems/insert-into-bits-lcci/solution/wei-yun-suan-bu-xun-huan-by-yechanghong/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信