Update Bits
今天的题目来自LintCode，是一道关于数学和位运算的题目，难度为Medium， Acceptance为19%。
题目如下：
Given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and jin N equal to M (e g , M becomes a substring of N located at i and starting at j)
Example Given
N=(10000000000)2, M=(10101)2, i=2, j=6
returnN=(10001010100)2
Note In the function, the numbers N and M will given in decimal, you should also return a decimal number.
Challenge Minimum number of operations?
Clarification 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.
思路如下：
其实这道题并不难，至少不涉及太多的数据结构和算法，需要的只是一些数学知识和位运算的知识，和一些细心与耐心。
首先，因为涉及到位运算，当然要将所有数字表示成32位二进制数的形式（题目中给出的不满32位的形式不利于解题）。拿题目中的例子来说：
N=(10000000000)2 M=(10101)2 即N=1024,将其表示成32位的形式，即在前面补0得到N=(00000000 00000000 00000100 00000000)2 M=(00000000 00000000 00000000 00010101)2。Update之后N=(10001010100)2，即N=(00000000 00000000 00000000 00000100 01010100)2。其中加粗的部分即M。与Update之前的N对比，可以发现，除了i到j这一部分，其他部分与原数据相同。
由位运算的性质可知，要保留一个数不变，需要与1做与运算，而变成M的部分可以先将该部分变成0，然后再与M做或运算，或者直接将M移位后做加法。好了，思路有了之后，我们来看代码。
代码如下：
Java版
class Solution {
/**
*@param n, m: Two integer
*@param i, j: Two bit positions
*return: An integer
*/
public int updateBits(int n, int m, int i, int j) {
// write your code here
int mask = (j < 31 ? (~((1 << (j + 1)) - (1 << i))) : ((1 << i) - 1));
return (m << i) + (mask & n);
}
}
C++版
class Solution {
public:
/**
*@param n, m: Two integer
*@param i, j: Two bit positions
*return: An integer
*/
int updateBits(int n, int m, int i, int j) {
int mask;
if (j < 31) {
mask = ~((1 << (j + 1)) - (1 << i));
} else {
mask = (1 << i) - 1;
}
return (m << i) + (mask & n);
}
};
其中的mask即我们需要的掩码，以题目中的例子为例，mask=(11111111 11111111 11111111 10000011)2，这样与n做与运算，就可以做到我们前面说的保留i到j之外的部分，同时i到j之间的部分清0，然后在和左移i位的m相加就得到最后的结果。
如果觉得文章有帮助的话，不妨关注一下本公众号，当然也希望能帮作者推广一下，更多人关注我也会更有动力，在此先谢过了。
关注我
