DSA interview question

Set the Rightmost Unset Bit / Clear the Rightmost Set Bit

Easy · Algorithms · Topics: bit manipulation

The problem

A resource pool tracks which of its slots are occupied as bits of an integer (1 = occupied). Two operations run constantly. Allocate marks the lowest free slot as occupied, which means setting the rightmost 0 bit, but if every slot up to the highest occupied one is already full, the number stays the same, following the classic problem's rule. Release frees the lowest occupied slot, which means clearing the rightmost 1 bit. Both are one-line tricks built on how +1 and −1 ripple through the low bits.

Example: set on 6 (110) → 7 (111); clear on 12 (1100) → 8 (1000).

Function signature

int setRightmostUnsetBit(int n);   // n >= 0; if bits 0..top are all 1, return n unchanged; 0 -> 1
int clearRightmostSetBit(int n);   // any n; 0 stays 0

Test cases

Input	Output	Explanation
`setRightmostUnsetBit(6)`	`7`	110 → 111
`setRightmostUnsetBit(10)`	`11`	1010 → 1011
`setRightmostUnsetBit(13)`	`15`	1101 → 1111
`setRightmostUnsetBit(15)`	`15`	1111 has no unset bit, so it stays
`setRightmostUnsetBit(0)`	`1`	"0" has an unset bit at position 0
`clearRightmostSetBit(12)`	`8`	1100 → 1000
`clearRightmostSetBit(7)`	`6`	111 → 110

(Confirm: for the set operation, n ≥ 0 and only bits up to its highest set bit count; numbers like 1, 3, 7 and 15 stay unchanged.)

How interviewers phrase it

"Set the rightmost unset bit of a non-negative number; if there is none, leave it unchanged" (GeeksforGeeks).
"Turn off the rightmost set bit" is the companion question.

Clarifying questions to ask

What counts as "no unset bit"? (All bits below the highest set bit are 1.)
What should happen for 0?
Can n be negative? (Not for the set operation in the classic version.)

Follow-ups to expect

"Why does n | (n + 1) set the rightmost 0?"
"How do you detect 'all ones'?"
"Why does n & (n − 1) clear the rightmost 1?"
"Isolate the rightmost set bit?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview