Problem

Given an unsigned word x, produce a word (same width) that has a single 0-bit located at the position of the rightmost set bit (rightmost 1) in x, and 1 bits everywhere else. If x is all zeros, the result should be a word of all ones.

Examples

Example 1

1
2
3

Input:  x = 0b01011000
Output: 0b11110111
Explanation: rightmost `1` in `x` is at bit position 3 (0-based from LSB); resulting word has a single 0 there and 1s elsewhere.
Similar Problems

Solution

Method 1 — Bit trick: ~x | (x - 1)

Intuition

x - 1 clears the rightmost set bit of x and sets all less-significant bits to 1. The bitwise complement ~x has 0 where x has 1. At the position of the rightmost set bit both ~x and (x - 1) have a 0. OR-ing them produces a single 0 at that position and 1 everywhere else. For an all-zero input, x - 1 (as unsigned) wraps to all ones and ~x is also all ones, so the OR is all ones.

Approach

  • Treat x as an unsigned word of the desired width (machine word or explicit width).
  • Compute res = (~x) | (x - 1).
  • If your language has unbounded integers (Python) or you want to restrict to w bits, mask the result with mask = (1 << w) - 1.
Edge cases
  • If x == 0, x - 1 wraps to all ones (for unsigned) and the expression yields all ones.
  • Use unsigned types in C/C++ to avoid signed overflow/implementation-defined behaviour.

Dry Run

1
2
3
4

x            = 01011000
~x           = 10100111
x - 1        = 01010111
~x | (x - 1) = 11110111

Code

1
2
3
4
5
6
7

class Solution {
 public:
  // Works on unsigned machine word (e.g., 32-bit/64-bit depending on type)
  unsigned makeWord(unsigned x) {
    return (~x) | (x - 1u);
  }
};
1
2
3
4
5

package main

func MakeWord(x uint) uint {
    return ^x | (x - 1)
}
1
2
3
4
5

class Solution {
    public int makeWord(int x) {
        return ~x | (x - 1);
    }
}
1
2
3
4

class Solution:
    def make_word(self, x: int, width: int = 32) -> int:
        mask = (1 << width) - 1
        return ((~x) | (x - 1)) & mask

Complexity

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