Set/Unset the rightmost unset bit
EasyOR with n+1
Problem
Set the rightmost 0-bit of a number to 1 (if the number is all 1s, return it unchanged).
OR the number with n+1 to flip on its lowest 0 bit.
The idea
Adding one turns the rightmost run of ones into zeros and sets the zero above them, so `n | (n + 1)` sets exactly that rightmost unset bit and leaves everything else alone. A number that is all ones has no unset bit and comes back unchanged in the intended range.
The trick
- `n | (n + 1)` sets the rightmost 0 bit.
- Compare with `n & (n + 1)`, which clears the rightmost run of ones.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — 10 (1010) Values: 10, 1010.
1if n & (n+1) == 0: return n // all ones2return n | (n+1)Input
- array
- [10, 1010]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 5
- Output:
- 7
- Explanation:
- 5 is 101; the rightmost 0 becomes 1 → 111 = 7.
Example 2
- Input:
- n = 7
- Output:
- 15
- Explanation:
- 7 is 111; the next bit up turns on → 1111 = 15.
Example 3
- Input:
- n = 10
- Output:
- 11
- Explanation:
- 10 is 1010; the lowest 0 flips → 1011 = 11.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.