LintCode刷题笔记-- Update Bits

标签：

位运算

描述：

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 j in N equal to M (e g , M becomes a substring of N located at i and starting at j)

解题思路：

1.这道题给出了四个int型的整数，其中m，n是两个给定的整数，而i与j则是前后两位的区间，例如i =2 , j =6 就是将n中的第二位到第六位变换为m

2.此题引入了一个掩码的概念（mask）：

（1）初始的时候所有位都为1：ones = ~0

（2） left ：将ones 所有的位都向左移动j位+1 left = (ones<< j) + 1，形成mask左边部分（之所以加1是因为第一位是符号位1）

(3) right ：将1同时也向左移动i位，再减去1，right = (1<<i)-1（之所以减去1是因为，要空出第i位，从i-1位变成1）

（4）将left和right来做或的运算，可以得到mask，正好得到前面所有的1和后面所有的1，空出中间的0，从而得到mask

　（5）对于mask其实存在一个corner case就是如果j>31 的情况，在此left方向就会溢出，此时只需要计算right部分即可，因为题目中保证存在足够的空间进行位移，所以不考虑溢出。

3. 将mask 与 n来做与运算，从而可以将mask其他的位置上的数字变为与n相同的

4. 将m向前移动i位，正好可以与mask中预留出来的所有的0对齐，再与第三步得到的结果进行或运算，将m中的内容插入n中的指定位置。

5. 最后的表达形式为：(n&mask) | (m<<i)

参考代码：

http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/72988

巴特西

LintCode刷题笔记-- Update Bits

最新文章

热门文章