java - 回文排列(破解编码面试 1.4)

Question

我无法理解这两个函数中的位逻辑。

1. 我不知道为什么我们要检查条件 (bitVector & mask) == 0。

2. 此外，为什么我们在满足条件时将 bitVector 与掩码进行 OR，否则将 bitVector 与 ~mask 进行 AND？

3. 为什么有这样一种属性，可以“通过从整数中减去一个并将其与原始整数进行与运算来检查是否恰好设置了一位”？

完整代码 here .

/* Toggle the ith bit in the integer. */
public static int toggle(int bitVector, int index) {
    if (index < 0) return bitVector;

    int mask = 1 << index;
    if ((bitVector & mask) == 0) {
        bitVector |= mask;
    } else {
        bitVector &= ~mask;
    }
    return bitVector;
}

/* Check that exactly one bit is set by subtracting one from the 
 * integer and ANDing it with the original integer. */
public static boolean checkExactlyOneBitSet(int bitVector) {
    return (bitVector & (bitVector - 1)) == 0;
}

Answer 1

首先，重要的是要了解 mask 恰好设置了一位，所有其他位均为零。如果索引为0，则掩码为1。如果索引为1，则掩码为2。如果索引为2，则掩码为4。如果索引为3，则掩码为8。如果索引为4，则掩码为16。依此类推。 mask 的所有这些值都恰好设置了一位，即第 index 位。

I don't know why we are checking for the condition (bitVector & mask) == 0.

如果未设置该位，则此条件为真。如果该位已设置，bitVector & mask 的结果将等于 mask，我们知道它不为零。

Also, why do we OR the bitVector with the mask when the condition is satisfied and AND the bitVector with ~mask otherwise?

我们或设置位的值。我们和 ~mask 取消设置位。请记住，mask 恰好设置了一位，因此 ~mask 设置了除一位之外的所有内容。

Why is there a property such that one can "check that exactly one bit is set by subtracting one from the integer and ANDing it with the original integer"?

当你从一个数字中减去 1 时，最后一个 1 之后的所有位都变成 1。发生这种情况的原因与当一个以 10 为底的数字以一个或多个零结尾时相同，如果你减去 1，那么所有尾随零变成9。我建议用二进制记下一堆数字，减去1后的值。简单的数学变得显而易见。

我们来看一个例子，16:

16 : 10000
15 : 01111

很明显，两个数字的 AND 运算结果为 0。让我们看另一个例子，48:

48 : 110000
47 : 101111

很明显，将某个数字 num 与 num-1 进行 AND 运算基本上会将最后一个 1 到最后的所有位清零。如果之前有任何其他位，它们将保留，结果不会为零。如果只有一个 1，结果只会是零。