一个测试用例的更新位错误

Question

给定两个 32 位数字 N 和 M，以及两个位位置 i 和 j。写一个方法，设置N中i和j之间的所有位都等于M（例如，M成为N的一个子串，位于i，从j开始）

例子

Given N=(10000000000)2, M=(10101)2, i=2, j=6
return N=(10001010100)2

这是我的代码：

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) {
    n = clearbits(n,i,j);
    m = m<<i;
    return m|n;
}
public static int clearbits(int n, int i, int j){
    //& with 0
    long allones = ~0;
    long left = allones << (j);
    long right = ((1<<i) - 1);
    long mask  = left | right;
    return (int) mask & n;
}}

问题是输入 [-123,45,21,26] 预期输出是 -37748859 并且代码给出输出 -123

更新：更改清除位以处理整数溢出后。以下输入失败输入 [-521,0,31,31] 输出 -521 预期的 2147483127

Answer 1

你真正需要的是：

public int updateBits(int n, int m, int i, int j) {
  int mask = ((int)((1L<<(j-i+1))-1))<<(i);
  return (n&~mask)|((m<<i)&mask);
}

请注意，为了调试目的，您可以使用以下方法打印出位串：

System.out.println(Integer.toBinaryString(mask));

基本上我需要创建一个掩码来匹配 i 和 j 之间的位位置。现在假设我想在位置 3 和 5 之间进行遮罩，我基本上想要生成如下所示的遮罩：

0000111000

我可以先尝试生成这个：

0000000111

并将其向左移动 i 个位置。这个值 + 1 给我：

0000001000

也就是 1 << (j-i+1)，然后像 (1 << (j-i+1))-1 那样减去一个掩码，我仍然需要进一步左移 i，所以我得到这个掩码：

((1<<(j-i+1))-1)<<(i)

使用 (n&~mask).

清除 n 上的位

我不能直接屏蔽m中的位，因为我仍然需要将它左移以匹配要替换的位串的位置。移位后，我可以使用 ((m<<i)&mask) 进行遮罩。请注意，如果用户确保 m 适合掩码，则可能不需要掩码 m。

现在把这两个词放在一起，你就有答案了！

return (n&~mask)|((m<<i)&mask);

或者不使用掩码 m，一步完成：

return (n&~(((int)((1L<<(j-i+1))-1))<<(i)))|(m<<i);

更新：

您采用了一种略有不同的方法，即构建掩码的左侧和右侧，并将两者相加。不错的方法。但是，我注意到的一个错误是：left 不应该是 allones << (j+i)，而应该是 allones << (j+1)（加一，而不是加 i）。

我们还需要再次处理溢出问题：

int left = (int)(((long)allones) << (j+1));

一个测试用例的更新位错误

Update bits error on one testcase

java

algorithm

bit-manipulation