Problem

Given an integer x, clear the kth bit from the right (the rightmost bit is the 0th bit).

For example, let's say x = 000100101110. Here the 1st, 2nd, 3rd, 5th, and 8th bit are set. So for k=1, the algorithm should return 00100101100, but for k=0, since the 0th bit is already clear, it should return the original value unchanged.

Algorithm

To solve this problem we need to do some bit masking. We want to mask one bit to 0, while leaving the other bits unchanged. To mask a bit to 0, we use a bitwise AND. We need to bitwise AND the integer x with a number containing bits all set to 1, except in the kth location set to 0. In boolean algebra a \& 1 = a whereas a \& 0 = 0, so we leave all the bits unchanged except in the kth location we clear it.

For example if x = 00100101110 and k=1, we want to do the operation 000100101110 \& 111111111101, which gives us our answer, 000100101100.

The question then is how do we compute the number 111111111101 where all bits are set except the kth bit. To do this, we can take the number 1 shift it to the left by k positions and negate the result.

Here is the code in java:

public static int clearBit(int x, int k) {
    return x & ~(1 << k);
}
Be Sociable, Share!