Update Bits

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
return N=(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相加就得到最后的结果。