Palindrome Permutation (Cracking the Coding Interview 1.4)

Question

I'm having trouble understanding the bit logic in these two functions.

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

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

3. 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"?

Full code 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;
}

Goraud

For 1 & 2, it is best if you take a piece of paper and a pen and write down some bits. You will see how well this works, and it will help you understand it properly. – Selfreproach

You should start by reading this – Trichocyst

For the toggle function, would return bitVector ^ (~bitVector ^ mask); do the job? – Milo

Answer 1

First of all, it's important to understand that mask has precisely one bit set, all other bits are zero. If index is 0, mask is 1. If index is 1, mask is 2. If index is 2, mask is 4. If index is 3, mask is 8. If index is 4, mask is 16. And so on. All these values of mask have precisely one bit set, the index-th bit.

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

This condition will be true if the bit is not set. If the bit was set, the result of bitVector & mask would be equal to mask, which we know is not zero.

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

We OR the value to set the bit. We AND ~mask to unset the bit. Remember that mask has precisely one bit set, and therefore ~mask has all except one bit set.

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"?

When you subtract 1 from a number, all bits after the last 1 become 1. This happens for the same reason that when a base-10 number ends with one or more zeros, if you subtract 1, then all the trailing zeros become 9. I suggest to down in binary a bunch of numbers, and their values after subtracting 1. The simple math becomes obvious.

Let's look at an example, 16:

16 : 10000
15 : 01111

It's clear that AND-ing the two numbers will result in 0. Let's look at another example, 48:

48 : 110000
47 : 101111

It's clear that AND-ing some number num with num-1 basically zeros out all the bits from the last 1 until the end. If there were any other bits before, they will remain, and the result will not be zero. The result will only be zero if there was only one 1.

Selfcontradiction

Thanks again for the detailed explanation. I keep running into bit manipulation problems so it's helpful to have some concrete step-by-step examples to refer back to. – Goraud