Problem Statement

Given an integer number, remove the last set bit (rightmost 1 bit) in its binary representation. The remaining bits should stay unchanged.

Input:

• number: An integer from which the last set bit needs to be removed.

Output:

• The integer after removing the last set bit.

Constraints:

• 0 ≤ number ≤ 2^31 - 1 (32-bit unsigned integer)

Examples

Example 1:

Input: number = 12 (Binary: 1100)
Output: 8 (Binary: 1000)

Explanation:
The original number is 12 (binary 1100).
The last set bit is at position 3 (0-indexed from the right).
Removing the last set bit results in 1000 (binary), which is 8 in decimal.

Example 2:

Input: number = 29 (Binary: 11101)
Output: 28 (Binary: 11100)

Explanation:
The original number is 29 (binary 11101).
The last set bit is at position 0.
Removing the last set bit results in 11100 (binary), which is 28 in decimal.

Different Approaches

1️⃣ Bitwise AND

To remove the last set bit of a number, you can use the following approach:

1. Subtract 1 from the number: This operation flips all the bits to the right of the last set bit, including the last set bit itself.
2. Bitwise AND with the original number: The result of this operation will clear the last set bit while preserving all other bits.

This works because flipping all the bits to the right of the last set bit and then AND-ing with the original number will turn the rightmost 1 bit to 0 and leave all other bits unchanged.

Approach:

Bitwise Operation Approach:

• Step 1: Compute number - 1. This flips the rightmost set bit and all bits to its right.
• Step 2: Perform a bitwise AND operation between the original number and the result from step 1. This clears the rightmost set bit.

Dry Run:

Initialization:

number = 29 (Binary: 11101)

Calculate number - 1:

number = 29 (Binary: 11101)

number - 1 = 28 (Binary: 11100)

Perform Bitwise AND Operation:

number = 29 (Binary: 11101)

number - 1 = 28 (Binary: 11100)

result = number & (number - 1)
       = 29 & 28 (decimal)
       = 11101 & 11100 (Binary)
       = 11100 (Binary: 28 in decimal)

Code:

#include <iostream>
using namespace std;

int removeLastSetBit(int number) {
    // Remove the last set bit
    number = number & (number - 1);
    
    return number;
}

int main() {
    int number;
    
    cout << "Enter the number: ";
    cin >> number;
    
    int result = removeLastSetBit(number);
    
    cout << "Number after removing the last set bit: " << result << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(1) Each operation is constant time.
• Space Complexity:O(1) No extra space used.