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.
Similar Problems 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#
Cpp
Go
Java
Python
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#
Cpp
Go
Java
Python
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).