Problem

Clear the rightmost set bit in the given integer.

For example, given the number 5, the bit pattern is 0101. Clearing the right most set bit we get 0100, which is 4. Given the number 8, the bit pattern is 1000, clearing the right most set bit we get 0.

Algorithm

The algorithm is simple. The difference in bit pattern between two consecutive binary numbers (n and n-1) is such that the rightmost set bit in the greater number is not set in the lesser number. However, all bits to the left of the rightmost set bit in the greater number are the same in both numbers. Therefore, if we bitwise AND the two consequence numbers together, we get the number in which the rightmost set bit from the greater number is unset, but all the other bits are kept the same.

Here is the code in java:

public static int clearLowestBit(int x) {
    return x & (x-1);
}
Be Sociable, Share!