回文排列（Cracking the Coding Interview 1.4）

Question

回文排列（Cracking the Coding Interview 1.4）

javabit-manipulationpermutationpalindromebitvector

7

我有些困惑这两个函数中的位逻辑。

我不知道为什么要检查条件(bitVector & mask) == 0。
当条件满足时，为什么要将bitVector与mask进行OR运算，否则要将bitVector与~mask进行AND运算？
为什么存在一种属性，可以“通过从整数中减去1并将其与原始整数进行AND运算来检查是否只设置了一个位”？

完整代码在此处。

/* 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;
}

- Decimal

1

对于1和2，最好拿一张纸和笔写下一些位，你会发现这很有效，并且有助于你正确理解它。 - Richard Le Mesurier

你应该从阅读这个开始。 - AxelH

对于“toggle”函数，return bitVector ^ (~bitVector ^ mask);是否能够胜任？ - jsheeran

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- janos · Accepted Answer

首先，重要的是要理解 mask 只有一个位被设置为1，其它位都是0。如果索引是0，则mask为1。如果索引是1，则mask为2。如果索引是2，则mask为4。如果索引是3，则mask为8。如果索引是4，则mask为16。所有这些mask值都只有一个位被设置为1，即索引位。

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

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

“另外，为什么当条件满足时我们要使用按位或（OR）操作符将bitVector与mask相加，否则要使用按位与（AND）操作符将bitVector与~mask相与？”

我们使用按位或（OR）将值设置为1。我们使用按位与（AND）~mask 将该位清零。请记住，mask只有一个位被设置为1，因此~mask除了一个位被设置为1以外，其它所有位都被设置为1。

“为什么存在一种属性可以"通过从整数中减去1并将其与原整数进行AND运算来检查是否只有一个位被设置"呢？”

当您从一个数字中减去1时，最后一位1之后的所有位都变为1。这与当一个10进制数以一个或多个零结尾时，如果您减去1，那么所有尾随的0都会变成9是同样的原因。我建议你把一些数字转化为二进制，并将它们减去1后的值进行比较。这个简单的计算很明显。

让我们看一个例子，16：

16 : 10000
15 : 01111

很明显，对这两个数字进行与运算的结果为0。我们再来看另外一个例子，48：

48 : 110000
47 : 101111

很明显，将某个数字num与num-1进行按位与操作（AND），会将从最后一个1的位置一直到末尾的所有位都变为0。如果在最后一个1之前还有其他的1，它们不会改变，并且结果不会变为0。只有当原数字中只有一个1时，结果才会变成0。