Find Rightmost Set Bit

Locate the position of the lowest set bit in an integer using bitwise logic.

bitwise bit-manipulation integer

Write a function `rightmost_set_bit(n: int) -> int` that takes a non-negative integer `n` and returns the 1-indexed position of its rightmost set bit (the least significant bit that is 1). If `n` is 0 (no set bits), return 0. Positions count from 1, so for `n = 1` the rightmost set bit is at position 1. For `n = 12` (binary `1100`), the rightmost set bit is at the third position, so return 3. You may use any bitwise operations (shifts, AND, XOR, etc.) but avoid converting to string or using bit_length in a loop over all bits.

Constraints

- Input `n` is an integer such that `0 <= n <= 10^9`.
- Time complexity should be O(1) or O(log n) worst-case; typical solution uses bitwise tricks.

Example

>>> rightmost_set_bit(1)
1
>>> rightmost_set_bit(12)
3
>>> rightmost_set_bit(0)
0
>>> rightmost_set_bit(64)
7

8 points ~12 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider that `n & -n` isolates the lowest set bit.

If you isolate the bit, you can get its position using `int.bit_length()`.

If `n` is 0, handle it explicitly by returning 0.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.