Problem

Add one to an integer without using the + or - operators.

This problem is similar to: Sum of Two Integers.

Examples

Example 1

1
2
3

Input: 7
Output: 8
Explanation: 7 (0111) -> 8 (1000)

Example 2

1
2
3

Input: 15
Output: 16
Explanation: 15 (1111) -> 16 (10000)

Notes

  • Work with standard fixed-width integers: behavior on overflow depends on the language/representation (e.g., wrapping for unsigned types).
Similar Problems

Solution

We provide two bitwise methods: one that directly flips the rightmost 0 and clears trailing 1s, and a second that performs binary addition using bitwise XOR/AND with a carry initialized to 1.

Method 1 – Flip Rightmost Zero (Bit-trick)

Intuition

When adding 1 to a binary number, you find the rightmost 0, change it to 1, and set all less-significant bits (to its right) to 0. Working with bit masks lets us locate that position and update the number without + or -.

Approach

  • Initialize a mask pos = 1 (represents the least-significant bit).
  • While pos & num is non-zero, shift pos left by one to find the first 0 bit.
  • Set that bit with num = num | pos.
  • Clear all lower bits (to the right) by iterating pos right and toggling those bits with num = num ^ pos until pos becomes zero.
  • Return num.

This handles cases like all-ones numbers (e.g., 1111 -> 10000) correctly using bit operations only.

Code

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

class Solution {
 public:
    int addOne(int num) {
        int pos = 1;
        while ((pos & num) != 0) {
            pos <<= 1;
        }
        num = num | pos;
        pos >>= 1;
        while (pos != 0) {
            num = num ^ pos;
            pos >>= 1;
        }
        return num;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

package main

func addOne(num int) int {
    pos := 1
    for (pos & num) != 0 {
        pos <<= 1
    }
    num = num | pos
    pos >>= 1
    for pos != 0 {
        num = num ^ pos
        pos >>= 1
    }
    return num
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int addOne(int num) {
        int pos = 1;
        while ((pos & num) != 0) {
            pos <<= 1;
        }
        num = num | pos;
        pos >>= 1;
        while (pos != 0) {
            num = num ^ pos;
            pos >>= 1;
        }
        return num;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def add_one(self, num: int) -> int:
        pos = 1
        while (pos & num) != 0:
            pos <<= 1
        num = num | pos
        pos >>= 1
        while pos != 0:
            num = num ^ pos
            pos >>= 1
        return num

Complexity

  • ⏰ Time complexity: O(b), where b is the number of bits in num. We may inspect each bit once in the worst case.
  • 🧺 Space complexity: O(1), constant extra space for masks and counters.

Method 2 – Bitwise Adder Loop (XOR + AND carry)

Intuition

Binary addition can be implemented using bitwise XOR for sum without carry, and bitwise AND (shifted) to compute carry. Repeating these two operations until there is no carry mimics num + 1 without using + or -.

Approach

  • Initialize carry = 1 (we want to add 1).
  • Loop while carry != 0:
    • Compute sum = num ^ carry (sum without carry).
    • Compute carry = (num & carry) << 1 (propagated carry).
    • Set num = sum.
  • When carry becomes zero, num contains the final result.

This is essentially the bitwise full-adder repeated until completion.

Code

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

class Solution {
 public:
    int addOne(int num) {
        int carry = 1;
        while (carry != 0) {
            int sum = num ^ carry;
            carry = (num & carry) << 1;
            num = sum;
        }
        return num;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

package main

func addOne(num int) int {
    carry := 1
    for carry != 0 {
        sum := num ^ carry
        carry = (num & carry) << 1
        num = sum
    }
    return num
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int addOne(int num) {
        int carry = 1;
        while (carry != 0) {
            int sum = num ^ carry;
            carry = (num & carry) << 1;
            num = sum;
        }
        return num;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def add_one(self, num: int) -> int:
        carry = 1
        while carry != 0:
            s = num ^ carry
            carry = (num & carry) << 1
            num = s
        return num

Complexity

  • ⏰ Time complexity: O(b), where b is the number of bits — each iteration clears at least one carry bit or shifts it left, so the loop runs at most b times.
  • 🧺 Space complexity: O(1), constant extra space.