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

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

更新:更改 clearbits 以处理整数溢出后。以下输入失败 输入[-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 之间进行 mask ，我基本上想要生成如下所示的 mask :

0000111000

我可以通过首先尝试生成这个来做到这一点:

0000000111

并将其移动 i左边的位置。这个值+ 1给我:

0000001000

这是1 << (j-i+1) , 并减去 (1 << (j-i+1))-1一个给了我面具我仍然需要进一步左移 i ，所以我得到这个作为面具:

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

清除 n 上的位是使用 (n&~mask) 完成的.

我不能直接屏蔽 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));