Insertion

作者 QIFAN 日期 2016-10-24
Insertion

Source: Cracking the Code Interview 5.1


Description

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method
to insert Minto 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
Input: N = 10000000000, M = 10011, i = 2, j = 6
Output: N = 10001001100
将二进制N的i到j位换成M

思路

简单的方式是用string,但这样就脱离了这道题的初衷。
由于一个数或运算0都是它本身,可以联想清空N的i-j的位(变为0),然后将M扩充使其值刚好对其N的i-j位而保持其他位都为0,再将 N | M
步骤如下:

  1. 清空 N 中的 i-j 位
  2. 移动M使之对齐 N 的 i-j 位
  3. 合并 M 和 N

Solution

注释中以N = 10000000, M = 101, i = 2, j = 4为例

int updateBits(int n, int m, int i, int j) {
// 11111111
int allOnes = ~0;
// 使得j位前的数都为1,后面都为0,即left = 11100000
int left = allOnes << (j + 1);
// 使得i位后的都为1,即right = 00000011
int right = ((1 << i) - 1);
// 得到 mask = 11100011
int mask = left | right;
// n_cleared = 11100011
int n_cleared = n & mask;
// 移动m使得与N对齐,m_shifted = 10100
int m_shifted = m << i;
// 11100011 | 10100 = 11110111
return n_cleared | m_shifted;
}