Set Bits
出处 Insertion
Given N and M, 32bit integers, how to set i to j bits (bit position as 1,2,3,…32) of N as the value of bits in M.
For example, N = 00000000000000000000000001111011,
M = 00000000001000000011000000011000, i = 10, j = 20, then the result should be:
00000000001000000011000001111011
Solution
我们首先根据题意重现我们需要做的操作:
- 我们需要从M中get第i到第j个比特
- 我们需要clear N中第i到第j个比特
- 我们需要set N中第i到第j个比特。
对于1),根据基本操作,get bit需要&1,所以与M进行操作的bit mask在第i到第j位应当为1,其他位为0。对于2), 根据基本操作,clear bit需要&0,所以与N进行操作的位掩码在第i到第j位应当为0,其他位为1。注意,这个位掩码刚好是前一项操作位掩码的位反运算。对于3),我们只需要将1),2)的操作结果进行位或即可。构造所需位掩码的过程如前所述,对~0进行基本操作和加减法即可。
题意简单来讲就是使用 M 代替 N 中的第i位到第j位。很显然,我们需要借用掩码操作。大致步骤如下:
- 得到第i位到第j位的比特位为0,而其他位均为1的掩码mask。
- 使用mask与 N 进行按位与,清零 N 的第i位到第j位。
- 对 M 右移i位,将 M 放到 N 中指定的位置。
- 返回 N | M 按位或的结果。
获得掩码mask的过程可参考 CTCI 书中的方法,先获得掩码(1111...000...111)的左边部分,然后获得掩码的右半部分,最后左右按位或即为最终结果。
在给定测试数据[-521,0,31,31]时出现了 WA, 也就意味着目前这段程序是存在 bug 的,此时m = 0, i = 31, j = 31,仔细瞅瞅到底是哪几行代码有问题?本地调试后发现问题出在left那一行,left移位后仍然为ones, 这是为什么呢?在j为31时j + 1为32,也就是说此时对left位移的操作已经超出了此时int的最大位宽!
使用~0获得全1比特位,在j == 31时做特殊处理,即不必求left。求掩码的右侧1时使用了(1 << i) - 1, 题中有保证第i位到第j位足以容纳 M, 故不必做溢出处理。
Complexity
复杂度 O(1)
Code
final int BITS_COUNT = 32;
int setBits(int m, int n, int i, int j){
int max = ~0;
int mask = (max << BITS_COUNT - i) | (max >> j);
return (m & mask) | (n & ~mask)
}