Set the rightmost unset bit

Problem Link

Set the Rightmost Unset Bit – GFG

Problem Statement

Given a positive integer n, set the rightmost unset bit (0) in the binary representation of n.
If there is no unset bit (i.e., all bits are 1), return n as it is.

Return the new integer after setting the rightmost unset bit to 1.

Examples

Example 1:

Input: n = 5
Output: 7
Explanation:
Binary of 5 = 0101  
Rightmost unset bit is at position 1 → setting it → 0111 = 7

Example 2:

Input: n = 1
Output: 3
Explanation:
Binary of 1 = 0001  
Rightmost unset bit is at position 1 → setting it → 0011 = 3

Constraints

• 1 <= n <= 10⁸

Intuition

Every binary number has 0s and 1s. This problem asks us to:

• Find the first 0 from the right (least significant side)

• Set that bit to 1 (i.e., make it "on")

• Leave other bits untouched

To do this:

• Start with a bitmask check = 1 (i.e., 0001)

• Shift it left until you find the first 0 bit in n by checking (n & check)

• Use bitwise OR: n | check to set that bit

Approach: Bitmask Scanning

1. Start with a bitmask check = 1 (represents bit position 0)

2. While (n & check) == check, keep shifting check left

   • This means current bit is already set

3. As soon as we find a bit where (n & check) == 0, break

4. Use n | check to set that bit

Java Code

class Solution {
    static int setBit(int n) {
        int check = 1;

        for (int i = 0; i < 32; i++) {
            if ((n & check) != check) {
                break;
            } else {
                check = check << 1;
            }
        }

        return n | check;
    }
}

Time and Space Complexity

Dry Run

Input: n = 5

• Binary: 0101

• Check = 0001 → (n & check) == 1 → already set → shift left

• Check = 0010 → (n & check) == 0 → found unset bit → break

• Result = 0101 | 0010 = 0111 = 7

Input: n = 7

• Binary: 0111 → all lower bits set

• Check = 0001 → already set
  → 0010 → set
  → 0100 → set
  → 1000 → unset → set it

• 0111 | 1000 = 1111 = 15

Conclusion

This problem teaches a practical use-case of bitmasking and bitwise manipulation to:

• Locate a specific bit (unset)

• Modify it without changing other bits

This is a classic system-level trick often seen in optimization, CPU-level programming, and competitive coding.