Set the Rightmost Unset Bit — Editorial

Opening the reading…

Intuitionwhy adding one reveals exactly the bit to set

Start with the definition: scan the binary representation from the least significant bit until you find the first 0. Setting that bit changes the number by adding its place value, while every bit to its right stays unchanged because those bits are already 1.

Adding 1 to n flips the trailing run of 1 bits to 0 and changes the first 0 immediately to their left into 1. The new value n + 1 therefore contains the required bit, but it has lost the trailing ones. Bitwise OR restores those trailing ones, so n | (n + 1) keeps every original 1 and sets exactly the rightmost unset bit.

Approachturning the carry from n + 1 into a mask

Compute n + 1, because binary addition carries through every trailing 1 and turns the first zero to their left into 1.

Combine n and n + 1 with bitwise OR, because every bit already set in n must remain set and the new 1 marks the required position.

Return the OR result directly, because the carry operation changes only the trailing bits and the OR restores them without changing any higher bits.

Complexityconstant work regardless of the bit pattern

MEASURE	BOUND	WHY
Time	O(1)	The solution performs one addition and one bitwise OR on a fixed-width integer. It does not scan individual bits, so the running time does not increase for larger values of n within the integer type.
Space	O(1) extra	Only the input, n + 1, and the returned integer are held. The returned value is required output and is excluded from working memory; the bound does not degrade for any bit pattern, including a number made entirely of ones.

The only input symbol is n, the given positive integer. The output value is excluded from the extra-space bound.

Annotated solutionC++ · constant-time bit identity · the compact version

CPPSet the rightmost unset bit by OR-ing n with n + 1.

#include <iostream>

using namespace std;

class Solution {
public:
    int setBit(int n) {
        return n | (n + 1);
    }
};

The expression works because n + 1 changes the first zero after the trailing run of ones into a one. For example, 6 is 110 and 7 is 111, so 6 | 7 is 7. For 15, the fixed-width view is 01111 and 16 is 10000; their OR is 11111, which sets the next position to the left and produces 31.

The scanning alternativea slower arrangement that mirrors the definition

CPPScan upward with a mask, then OR the first mask whose bit is zero.

#include <iostream>

using namespace std;

class Solution {
public:
    int setBit(int n) {
        int mask = 1;

        while ((n & mask) != 0) {
            mask <<= 1;
        }

        return n | mask;
    }
};

This version is not an optimisation: it takes O(log n) time in the number of bit positions examined, while the identity takes constant time for the fixed-width integer type. It is nevertheless a useful implementation to understand and test, because mask starts at position 0 and the loop naturally continues past the highest set bit when all lower positions are one.