回文排列（破解编码面试1.4）

Question

我在理解这两个函数中的位逻辑时遇到麻烦。

1. 我不知道为什么我们要检查条件（bitVector＆mask）== 0。

2. 另外，为什么在满足条件时我们将bitVector与掩码进行“或”运算，否则将bitVector与〜mask进行“与”运算呢？

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

完整代码在这里。

/* 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。依此类推。掩码的所有这些值都精确地设置了一位，即第索引位。

我不知道为什么我们要检查条件（bitVector＆mask）== 0。

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

另外，为什么在满足条件时我们将bitVector与掩码进行“或”运算，否则将bitVector与〜mask进行“与”运算呢？

我们对值进行“或”设置。我们~mask并取消设置位。请记住，掩码恰好设置了一位，因此~mask除一位外，其他所有内容都已设置。

为什么要有这样一个属性，使得人们可以“通过从整数中减去一位并将其与原始整数进行“与”运算，来检查是否已正确设置了一位？

当您从一个数字中减去1时，最后一个1之后的所有位都变为1。这与以下原因相同：以10为底的数字以一个或多个零结尾时，如果您减去1，则所有尾随的零将变为9。我建议将一堆数字和它们的值相减后减去1。简单的数学就显而易见了。

让我们看一个例子：16

16 : 10000
15 : 01111

显然，将两个数字进行“与”运算将得出0。让我们看另一个示例48：

48 : 110000
47 : 101111

显然，将num-1与num-1进行“与”运算基本上将最后一位到末尾的所有位清零。如果之前还有其他位，则它们将保留，并且结果将不会为零。如果只有1，则结果将为零。