Remove Rightmost Set Bit in Binary Representation.

Problem Statement: Given a number n, remove its rightmost set bit (i.e., the lowest bit that is set to 1) and return the updated number.

Example 1:
Input: n = 18
Binary: 10010
Output: 16
Explanation: 18 & 17 = 10010 & 10001 = 10000 (16)

Example 2:
Input: n = 40
Binary: 101000
Output: 32
Explanation: 40 & 39 = 101000 & 100111 = 100000 (32)

Approach:

The binary representation of a number contains bits (0s and 1s). A set bit is a bit with value 1. The rightmost set bit is the lowest 1 when scanning from right to left.

To remove this bit, we use the trick:

n & (n - 1)

Why n & (n - 1) work?

Let’s say:

• n = xxx1000 (where the rightmost set bit is the last 1 before a string of zeros)
• n - 1 = xxx0111 (it flips all bits from that position)

When you AND these two:

• All bits after the rightmost 1 become 0
• The rightmost 1 is turned to 0
• All other bits remain the same

Example:

18 & (18 - 1)  
= 10010 & 10001  
= 10000  
= 16 (in decimal)

Example Code:

        
#include <iostream>
using namespace std;

int removeRightmostSetBit(int n) {
    return n & (n - 1);
}

int main() {
    int n = 18;
    cout << "After removing rightmost set bit: " << removeRightmostSetBit(n) << endl;
    return 0;
}

        

        
# Python Example to Remove the Rightmost Set Bit
def remove_rightmost_set_bit(n):
    return n & (n - 1)

n = 18
print("After removing rightmost set bit:", remove_rightmost_set_bit(n))

        

        
// Java Example to Remove the Rightmost Set Bit
public class RemoveRightmostSetBit {
    public static int removeRightmostSetBit(int n) {
        return n & (n - 1);
    }

    public static void main(String[] args) {
        int n = 18;
        System.out.println("After removing rightmost set bit: " + removeRightmostSetBit(n));
    }
}

        

Output:

After removing rightmost set bit: 16

Using n & (n - 1) is a powerful bitwise trick to remove the rightmost set bit efficiently in constant time. It's widely used in many algorithmic problems and is a must-know technique for interviews and competitive programming.