Right propagate the rightmost 1-bit

Problem

Given an integer x, right-propagate the rightmost set bit: set all bits to the right of the rightmost 1 (inclusive) to 1, leaving higher-order bits unchanged. Formally return x | (x - 1).

Examples

Example 1

1
2

Input: x = 0b01010000
Output: 0b01011111

Example 2

1
2

Input: x = 0b00000000
Output: 0b11111111  # behavior on unsigned underflow; see notes

Solution

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

Intuition

• Subtracting 1 from x clears the rightmost 1 bit and sets all lower bits to 1 (they were zeros). OR-ing with the original x therefore preserves higher-order bits and turns all lower bits (including the rightmost 1) into 1.

Approach

• If x == 0, note that x - 1 underflows in unsigned arithmetic and will be all ones; x | (x - 1) will therefore produce all ones.
• Otherwise compute and return ans = x | (x - 1).

Code

1
2
3
4
5
6

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

1
2
3
4
5

package main

func rightPropagate(x uint32) uint32 {
    return x | (x - 1)
}

1
2
3
4
5

class Solution {
  public int rightPropagate(int x) {
    return x | (x - 1);
  }
}

1
2
3

class Solution:
    def right_propagate(self, x: int) -> int:
        return x | (x - 1)

Complexity

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

Method 2 — Find rightmost set bit then apply mask

Intuition

• Locate the index pos of the rightmost set bit and construct a mask of pos lower bits set to 1 ((1 << pos) - 1). OR this mask with x to turn on all lower bits.

Approach

1. If x == 0, return ~0 for unsigned underflow behavior or 0 if you prefer a guarded return.
2. Find pos such that (x >> pos) & 1 == 1 and (x & ((1 << pos) - 1)) == 0 (scan LSB upward).
3. Compute mask = (1u << pos) - 1u and return x | mask.

Edge cases:

• This method avoids relying on underflow semantics if you prefer explicit behavior for x == 0.

Code

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

class Solution {
 public:
  unsigned int rightPropagate(unsigned int x) {
    if (x == 0) return ~0u; // or return 0 if guarded behavior desired
    unsigned int pos = 0;
    unsigned int tmp = x;
    while ((tmp & 1u) == 0u) {
      tmp >>= 1;
      ++pos;
    }
    unsigned int mask = (1u << pos) - 1u;
    return x | mask;
  }
};

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

package main

func rightPropagate(x uint32) uint32 {
    if x == 0 {
        return ^uint32(0) // or 0 for guarded behavior
    }
    pos := uint32(0)
    tmp := x
    for (tmp & 1) == 0 {
        tmp >>= 1
        pos++
    }
    mask := (uint32(1) << pos) - 1
    return x | mask
}

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

class Solution {
  public int rightPropagate(int x) {
    if (x == 0) return ~0; // or 0 if you prefer
    int pos = 0;
    int tmp = x;
    while ((tmp & 1) == 0) {
      tmp >>>= 1;
      pos++;
    }
    int mask = (1 << pos) - 1;
    return x | mask;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def right_propogate(self, x: int) -> int:
        if x == 0:
            return ~0  # or return 0 for guarded behavior
        pos = 0
        tmp = x
        while (tmp & 1) == 0:
            tmp >>= 1
            pos += 1
        mask = (1 << pos) - 1
        return x | mask

Complexity

• ⏰ Time complexity: O(w) where w is the word size (number of bits) due to scanning bits; in practice O(1) for fixed-width integers.
• 🧺 Space complexity: O(1).

Notes

• The canonical one-line trick is x | (x - 1) (Method 1). Be aware that when x == 0 this expression produces all 1 bits due to unsigned underflow; choose guarded behavior if that is undesirable.
• Reference: original bit-hacks collection in source_links.