Set / Unset the Rightmost Unset Bit
Solve this Problem
Given a non-negative integer
n, set its rightmost unset (0) bit to 1 and return the result. If every bit within n's current width is already set, the next bit position beyond its highest set bit gets set instead.
Scanning bit by bit until the first 0 is found works, but there's a neat identity: n | (n + 1) always sets exactly that bit. Adding 1 to n flips every trailing run of 1 bits to 0 and carries into the first 0 — a bit that's now set only in n + 1 — so OR-ing the two together restores everything else while keeping that one newly-set bit.
Test Case 1:
Input:n = 6
Output:7
Explanation:6 = 110 — the rightmost unset bit (bit 0) becomes 1, giving 111 = 7.
Test Case 2:
Input:n = 15
Output:31
Explanation:15 = 1111 has no unset bit within its own width, so the next one (bit 4) gets set, giving 11111 = 31.
Test Case 3:
Input:n = 0
Output:1
Explanation:0 has every bit unset — the rightmost one (bit 0) becomes 1.
Constraints
- ◆
0 ≤ n ≤ 10⁸
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Scan Bit by Bit
BruteWalk bit positions from 0 upward, checking each one, until the first unset bit is found — then set just that bit and return.
Time
O(32)Space
O(1)Java
1class Solution {
2 public int setRightmostUnsetBit(int n) {
3 for (int bit = 0; bit < 32; bit++) {
4 if (((n >> bit) & 1) == 0) {
5 return n | (1 << bit);
6 }
7 }
8 return n;
9 }
10}Optimal — n | (n + 1)
OptimalAdding 1 to n flips every trailing run of 1 bits to 0 and carries into the first 0 bit, turning it into a 1 — a bit that's now set in n + 1 but wasn't in n. OR-ing n with n + 1 restores every bit that got flipped off along the way (since n itself still has them as 1) while keeping that newly-set bit — exactly the rightmost unset bit, now set.
Time
O(1)Space
O(1)Java
1class Solution {
2 public int setRightmostUnsetBit(int n) {
3 int next = n + 1;
4 int result = n | next;
5 return result;
6 }
7}