Problem

Given an integer x, isolate (keep) only the rightmost set bit (1) and clear all other bits. If x is 0, the result is 0.

Examples

Example 1

1
2
3

Input: x = 0b01011010
Output: 0b00000010
Explanation: only the rightmost 1-bit is preserved.

Example 2

1
2

Input: x = 0
Output: 0
Similar Problems

Solution

Method 1 - Bit trick (x & -x)

Intuition

-x in two’s complement is equivalent to ~x + 1. The operation x & -x clears all bits except the rightmost 1. Intuitively, adding 1 to ~x propagates a carry to the first 1-bit from the right, which makes -x share only that bit with x when AND-ed.

Approach

  • If x == 0, return 0.
  • Compute ans = x & -x and return ans.

Edge cases:

  • Negative numbers: the expression works with two’s complement signed integers (the rightmost set bit of the bit-pattern is isolated).

Code

1
2
3
4
5
6

class Solution {
 public:
  long isolateRightmost(long x) {
    return x & -x;
  }
};
1
2
3
4
5
6

package main

// isolateRightmost returns a value with only the rightmost set bit of x preserved.
func isolateRightmost(x int64) int64 {
    return x & -x
}
1
2
3
4
5

class Solution {
  public long isolateRightmost(long x) {
    return x & -x;
  }
}
1
2
3

class Solution:
    def isolate_rightmost(self, x: int) -> int:
        return x & -x

Complexity

  • ⏰ Time complexity: O(1), computing x & -x takes constant time.
  • 🧺 Space complexity: O(1), only a constant number of variables used.

Method 2 - Bit scan (find position then mask)

Intuition

Scan bits from least-significant to most-significant to find the index of the first 1. Then return 1 << pos (or the equivalent mask) to isolate that bit.

Approach

  • If x == 0, return 0.
  • Initialize pos = 0.
  • While (x & 1) == 0, shift x >>= 1 and increment pos.
  • Return 1 << pos (or the mask with only that bit set).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
 public:
  long isolateRightmostScan(long x) {
    if (x == 0) return 0;
    int pos = 0;
    while ((x & 1) == 0) {
      x >>= 1;
      ++pos;
    }
    return 1L << pos;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package main

func isolateRightmostScan(x int64) int64 {
    if x == 0 {
        return 0
    }
    pos := int64(0)
    for (x & 1) == 0 {
        x >>= 1
        pos++
    }
    return 1 << pos
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
  public long isolateRightmostScan(long x) {
    if (x == 0) return 0;
    int pos = 0;
    while ((x & 1) == 0) {
      x >>= 1;
      ++pos;
    }
    return 1L << pos;
  }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def isolate_rightmost_scan(self, x: int) -> int:
        if x == 0:
            return 0
        pos = 0
        while (x & 1) == 0:
            x >>= 1
            pos += 1
        return 1 << pos

Complexity

  • ⏰ Time complexity: O(w) where w is the word size (number of bits); in practice this is O(1) for fixed-width integers but linear in the bit-length if considered variable.
  • 🧺 Space complexity: O(1).