Cracking Coding Interview - 5.1 Insertion

Insertion: You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.

EXAMPLE

1
2

Input:  N   10000000000, M = 10011, i = 2, j = 6
Output: N = 10001001100

Hints: #137, #169, #215

解法

这个问题其实大致分为两步：

1. 把N中从i到j的bit统统设置为0
2. 把M向左移动i个bit
3. 两者OR一下

第一步中需要做一个Mask：

1
2

N:     10000000000, i=2, j=6
Mask:  11110000011

Mask可以分为两部分做：

1
2
3
4

Mask1: 11110000000
Mask2: 00000000011
Mask : Mask1 | Mask2
       11111000011

Mask1可以用-1 << j + 1来得到（-1到bit都是1），Mask2可以用(1 << i) - 1得到。

代码：

1
2
3
4
5

public int insert(int n, int m, int i, int j) {
  int allOnes = ~0; // 都是1
  int mask = (allOnes << (j + 1)) | ((1 << i) - 1); // mask1 | mask2
  return (n & mask) | (m << i);
}