Turn off the rightmost 1-bit

Problem

Given an integer x, clear (turn off) its rightmost set bit (the least-significant 1) and return the resulting integer. If x has no set bits (i.e., x == 0), the result is 0.

Examples

Example 1

1
2
3

Input: x = 0b00101010
Output: 0b00101000
Explanation: the rightmost `1` (bit 1) is turned off.

Example 2

1
2
3

Input: x = 0b00010000
Output: 0b00000000
Explanation: the only `1` is turned off.

Example 3

1
2
3

Input: x = 0b00000000
Output: 0b00000000
Explanation: no bits set, remains zero.

Solution

Method 1 — Turn off rightmost 1-bit using x & (x-1) (recommended)

Intuition

Subtracting 1 from x clears the rightmost 1 and sets all less-significant bits to 1. AND-ing the original x with x-1 therefore clears only the rightmost 1 and preserves higher bits.

Approach

• Compute result = x & (x - 1).
• This works for unsigned or signed integers when using language semantics that define subtraction and bitwise AND as expected; for x == 0 the result remains 0.
• Be mindful of integer width and signedness in languages where x may be signed.

Code

1
2
3
4
5
6

class Solution {
 public:
    unsigned int turnOffRightmostOne(unsigned int x) {
        return x & (x - 1u);
    }
};

1
2
3
4
5

package main

func turnOffRightmostOne(x uint32) uint32 {
        return x & (x - 1)
}

1
2
3
4
5

class Solution {
    public int turnOffRightmostOne(int x) {
        return x & (x - 1);
    }
}

1
2
3

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

Complexity

• ⏰ Time complexity: O(1), constant-time arithmetic and bitwise operations.
• 🧺 Space complexity: O(1).

Method 2 — Explicit mask using (x & -x) to isolate then subtract (alternate)

Intuition

Isolate the rightmost set bit with lsb = x & -x (two’s complement) then subtract lsb from x to clear it: x - lsb.

Approach

• Compute lsb = x & -x which is a value with only the rightmost 1 set.
• Return x - lsb.
• This is equivalent to x & (x - 1) but uses explicit isolation of the least-significant set bit.

Code

1
2
3
4
5
6
7

class Solution {
 public:
    unsigned int turnOffRightmostOneAlt(unsigned int x) {
        unsigned int lsb = x & -x;
        return x - lsb;
    }
};

1
2
3
4
5
6

package main

func turnOffRightmostOneAlt(x uint32) uint32 {
        lsb := x & -x
        return x - lsb
}

1
2
3
4
5
6

class Solution {
    public int turnOffRightmostOneAlt(int x) {
        int lsb = x & -x;
        return x - lsb;
    }
}

1
2
3
4

class Solution:
        def turn_off_rightmost_one_alt(self, x: int) -> int:
                lsb = x & -x
                return x - lsb

Complexity

• ⏰ Time complexity: O(1).
• 🧺 Space complexity: O(1).