java - Cracking the Coding Interview中5.1的解法错了吗？

Question

因为我有一个技术面试，最近开始研究《Cracking the Coding Interview》这本书。

我在练习5.1的题时，发现书上的解法和我的不一样。

问题是:

给定两个 32 位数字 N 和 M，以及两个位位置 i 和 j。编写一个方法，将 N 中 i 和 j 之间的所有位设置为 M(例如，M 成为 N 的子串，位于 i 并从 j 开始)。示例:

Input: N = 10000000000, M = 10101, i = 2, j = 6
Output: N = 10001010100

解决方法是:

public static int updateBits2(int n, int m, int i, int j) {
    int max = ~0;
    int left =  max - ((1 << j) - 1);
    int right = (1 << i) - 1;
    int mask = left | right;
    int maskN = mask & n;
    int result = maskN | (m << i);
    return result;
}

关键点是创建一个掩码将n的i到j位设置为0，并将 m 左移到 i 位置并对 m 和 n 进行或运算。

当输入为n=89，m=3，i=2，j=4时，答案应该是77，对于:

n = 1011001
m = 011
n with 2 to 4 set by m = 1001101 = 77 

但是解的结果是93。

然后我发现解决方案创建的掩码缺少一个0位在左侧。例如，掩码应该是 1100011 上面给定的输入。但是解决方案创建的掩码是 1110011。

我通过更改这一行来解决这个问题

int left =  max - ((1 << j) - 1);

到

int left =  max - ((1 << j + 1) - 1);

所以我的问题是，解决方案是错误的还是我遗漏了什么？

Answer 1

您可以从示例中看出，其中 i=2、j=6 和 5 位发生了变化，[i,j] 意味着包含范围。所以如果你有 i=2 和 j=4，你应该设置 3 位，而不是 2。

所以你发布的函数(我不知道是你的还是引用的)叫做updateBits2不正确。

但是，当 j==31 时，您的修复失败了，这是他们会在编码面试中打扰您的事情。而不是 (1<<(j+1))-1 , 使用 (1<<j)|((1<<j)-1) , 或将整行缩短为 left = -2<<j;