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

Question

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

我不知道为什么我们要检查条件 (bitVector & mask) == 0。
此外，为什么我们在满足条件时将 bitVector 与掩码进行 OR，否则将 bitVector 与 ~mask 进行 AND？
为什么会有属性可以"check that exactly one bit is set by subtracting one from the integer and ANDing it with the original integer"？

完整代码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?

我们或设置位的值。我们 AND ~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，结果只会是零。

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

Palindrome Permutation (Cracking the Coding Interview 1.4)

java

bit-manipulation

permutation

palindrome

bitvector