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

• ← Previous Post
• Next Post →