6

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

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

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

  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;
}
4

1 回答 1

10

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

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

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

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

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

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

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

让我们看一个例子，16：

16 : 10000
15 : 01111

很明显，对这两个数字进行 AND 运算会得到 0。让我们看另一个例子，48：

48 : 110000
47 : 101111

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

于 2016-11-30T07:02:35.567 回答