Minimum One Bit Operations to Make Integers Zero

Gray-code position equals the answer — XOR-fold all bits with cumulative XOR scan from the top.

Hard

Time O(log n) Space O(1)

May 16, 2026 2 min read

Problem#

Operations: flip bit 0; flip bit i+1 iff bit i is set and bits 0..i-1 are all 0. Return the minimum number of operations to reduce n to 0.

Examples#

n=3 → 2.
n=6 → 4; n=0 → 0.

Constraints#

0 <= n <= 10^9.

Approach#

n is the Gray code of the answer. To invert Gray code: XOR-fold from the most significant bit downward — each bit of the answer is the XOR of n’s bits from that position upward.

Solution#

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int ans = 0;
        while (n) {
            ans ^= n;
            n >>= 1;
        }
        return ans;
    }
};

func minimumOneBitOperations(n int) int {
    ans := 0
    for n != 0 {
        ans ^= n
        n >>= 1
    }
    return ans
}

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        ans = 0
        while n:
            ans ^= n
            n >>= 1
        return ans

function minimumOneBitOperations(n) {
    let ans = 0;
    while (n) {
        ans ^= n;
        n >>= 1;
    }
    return ans;
}

class Solution {
    public int minimumOneBitOperations(int n) {
        int ans = 0;
        while (n != 0) {
            ans ^= n;
            n >>= 1;
        }
        return ans;
    }
}

function minimumOneBitOperations(n: number): number {
    let ans = 0;
    while (n) {
        ans ^= n;
        n >>= 1;
    }
    return ans;
}

Editorial#

The operations exactly model standard binary reflected Gray code transitions in reverse. The closed-form inverse (binary → Gray) is b ^ (b >> 1); the inverse (Gray → binary) is the cumulative XOR from MSB. The loop is its compact form: XOR n into ans and shift n right at each step.

Complexity#

Time: O(log n).
Space: O(1).

Concept revision#

Reverse Bits

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#