☕ DSA Java Articles

Topics › Bit Manipulation › Learn Bit Manipulation

Set/Unset the rightmost unset bit

Easy TUF ID 2410 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a non-negative integer n. Two operations are asked for:

Constraints: 0 ≤ n ≤ 2^31 - 1.

Example 1 (set)

n = 6
answer = 7           // 110 -> 111

Example 2 (set)

n = 11
answer = 15          // 1011 -> 1111, the lowest 0 sits above two trailing 1s

Example 3 (set, nothing to do)

n = 15
answer = 15          // 1111 has no unset bit

Example 4 (unset)

n = 12
answer = 8           // 1100 -> 1000

Approach 1: Brute force, scan from bit 0 upward

Intuition. Walk the positions 0, 1, 2, ... and test each bit with (n >> i) & 1. For the “set” operation stop at the first 0 and OR in 1 << i; for “unset” stop at the first 1 and AND with ~(1 << i). The only care needed is the stopping rule for “set”: we must not run past the highest set bit, or we would set a leading zero and turn 7 into 15. So compute the number of binary digits first and scan only inside it.

Algorithm (set).

  1. Compute len, the number of binary digits of n (1 for n = 0).
  2. For i from 0 to len - 1: if bit i is 0, return n | (1 << i).
  3. If the loop finishes every digit was 1; return n.
static int bitLength(int n) {
    int len = 0;
    do {
        len++;
        n >>>= 1;
    } while (n != 0);
    return len;
}

static int setRightmostUnsetBruteForce(int n) {
    int len = bitLength(n);
    for (int i = 0; i < len; i++) {
        if (((n >> i) & 1) == 0) return n | (1 << i);
    }
    return n;                                   // every digit is already 1
}

Algorithm (unset).

  1. For i from 0 to 30: if bit i is 1, return n & ~(1 << i).
  2. If the loop finishes, n was 0; return n.
static int unsetRightmostSetBruteForce(int n) {
    for (int i = 0; i < 31; i++) {
        if (((n >> i) & 1) == 1) return n & ~(1 << i);
    }
    return n;                                   // n == 0, nothing to clear
}

Complexity. Time O(log n) for each: at most one pass over the digits. Space O(1).

Approach 2: Optimal, let the carry find the bit

Intuition for “set”. Adding 1 to n is exactly a search for the rightmost 0: the carry turns each trailing 1 into 0, then lands on the first 0 and turns it into 1. So n + 1 has the right bit set, but the trailing ones have been wiped. OR-ing with the original n puts them back. Hence n | (n + 1) sets the rightmost unset bit in two operations. The one special case is n = 2^k - 1, all ones: there n + 1 is 2^k, a brand-new digit, and the OR would produce 2^(k+1) - 1. The problem says to leave such n alone, and the test for “all ones” is itself a bit trick: n & (n + 1) == 0, because n + 1 has no bit in common with n only when the carry ran all the way off the top. n = 0 also satisfies that test, but its single digit is a 0 that should be set, so it is excluded explicitly.

Algorithm (set).

  1. If n != 0 and (n & (n + 1)) == 0, return n.
  2. Otherwise return n | (n + 1).
static int setRightmostUnsetOptimal(int n) {
    if (n != 0 && (n & (n + 1)) == 0) return n; // n is 2^k - 1, all ones, nothing to set
    return n | (n + 1);
}

Dry run on n = 11 = 1011:

step binary value
n 1011 11
n + 1 1100 12 (carry cleared the two trailing 1s and set bit 2)
n | (n + 1) 1111 15

And on n = 15 = 1111: n + 1 = 10000, n & (n + 1) = 0, so return 15.

Intuition for “unset”. Subtracting 1 is the mirror image: the borrow turns each trailing 0 into 1, then lands on the first 1 and turns it into 0. So n - 1 differs from n exactly in the lowest set bit and the zeros below it. AND-ing with n keeps everything above (identical in both) and clears the lowest set bit (now 0 in n - 1), and the borrowed-in ones below are killed by the zeros in n. For n = 0 the result is 0 & -1 = 0, which is the required answer with no special case.

Algorithm (unset).

  1. Return n & (n - 1).
static int unsetRightmostSetOptimal(int n) {
    return n & (n - 1);
}

On 12 = 1100: n - 1 = 1011, 1100 & 1011 = 1000 = 8.

Complexity. Time O(1), space O(1) for both.

A third sibling: isolate the rightmost set bit

Having removed the lowest set bit, you often want its value on its own, for instance to iterate over the bits of a mask one at a time. -n is ~n + 1: flipping all bits and adding one turns the trailing zeros back into zeros, turns the lowest set bit back into a 1, and leaves everything above inverted. So n and -n agree only at that one bit, and n & -n isolates it. Equivalently it is n - (n & (n - 1)), which the Java file checks for every n up to 5000.

static int isolateRightmostSet(int n) {
    return n & -n;
}

On 12 = 1100: -12 = ...110100, 1100 & 0100 = 0100 = 4.

Edge cases and pitfalls