Remove the last set bit (rightmost)

Given a number N, the task is to unset the rightmost set bit of the number.

Example

Input : n = 7
Output : 6
 
Input : n = 12
Output : 8

Explanation: The binary representation of 7 is 111 and the binary representation of 6 is 110. The rightmost set bit in 7 is at position 0. So, unsetting it will give 6.

Approach

1. We know how to convert a number into binary.
2. To unset the rightmost set bit, we need to AND the number with N-1.

Implementation

int unsetRightmostSetBit(int N) {
    return (N & (N - 1));
}

Confused? Let's dry run the above code with an example.

Dry Run

Example 1:

Given N = 7

N = 7 = 111
N - 1 = 6 = 110

Now, we will AND the above two values

  111
& 110
------
  110

Example 2:

Given N = 12

N = 12 = 1100
N - 1 = 11 = 1011

  1100
& 1011
------
  1000

Complexity Analysis