Problem

Add two positive numbers without using + or ++ but only bitwise operators.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Iterative Half Adder - Using & and ^ Operator

To solve this problem, we rely on two fundamental bitwise operators: & (AND) and ^ (XOR).

  • The & operator is responsible for determining the carry bits.
  • The ^ operator performs the addition of two numbers excluding the carry, effectively functioning as a simple addition without overlaps.

For two bits, their sum can be computed using the XOR ^ operator, while the carry is derived by applying the AND & operator on the same bits. This concept mirrors the fundamental functioning of a Half Adder, a circuit that combines these operations to add two single bits.

We can expand this logic further to work with integers:

  • If two numbers, x and y, do not share set bits in the same positions, the XOR operation (x ^ y) gives us their sum.
  • To handle the positions where both numbers have set bits (i.e., generate a carry), the AND operation (x & y) identifies all the carry bits. Shifting these carry bits left by one position ((x & y) << 1) aligns them correctly for the addition process.

By combining these two results—x ^ y for the sum and (x & y) << 1 for the carry—we iteratively compute the final sum. This approach is directly inspired by the core principles of a half-adder.

The key idea is to break down the problem into two parts: sum without carry and carry itself. For example, let’s take the binary representations of 2 and 1 (10 and 1). Since no carry is required to add these numbers, their sum can be directly calculated using the XOR (^) operator:

1

10 ⊕ 1 = 11

Step by Step Logic for Decimal Numbers

  1. Start by adding 759 and 674 while ignoring any carry. The result is 323.
  2. Now add 759 and 674 while only accounting for the carry. This gives 1110.
  3. Add the results from the first two steps recursively, continuing until no carry remains: 1110 + 323 = 1433.

This method can be adapted for binary numbers.

Adapting logic for binary numbers

Now, how would we do this in binary?

  1. When adding two binary numbers without a carry, the resulting bit at position i will be 0 if both bits at that position in a and b are either 0 or 1. This corresponds to the XOR (^) operator.
  2. When adding two numbers and considering only the carry, there will be a 1 at a position i only if both bits at position i-1 in a and b are 1. This is equivalent to the AND (&) operator, followed by a left shift to account for the carry moving to the next higher position ((a & b) << 1).
  3. Repeat the above operations until no carry remains.

Breaking down the operations

Get the Carry

To calculate the carry for two numbers, a & b identifies all positions where both numbers have 1 bits. Left-shifting this result by one bit ((a & b) << 1) gives the carry:

  • Example: Adding 3 (011) and 2 (010) results in:
    • Carry = (a & b) << 1: 010 << 1 = 1 0 (binary) or 2 (decimal).
Get the Sum Except Carry
  • Carry = (a & b) << 1: 010 << 1 = 1 0 (binary) or 2 (decimal).

Example - Add 13 and 10 in Binary

Let a = 13 and b = 10 in binary:

Binary Representation

Let a = 13 and b = 10 in binary:

1
2
3
4

a      =  1 1 0 1
b      =  1 0 1 0
--------------------
a+b = (1) 0 1 1 1
Using ^ and &

Now we can break the addition into two parts, one is simple addition without taking care of carry, and other is taking the carry.

1) Sum Without Carry

Use XOR (^) to add without handling the carry:

1
2
3
4

a      =  1 1 0 1
b      =  1 0 1 0
--------------------
a^b    =  0 1 1 1

2) Carry

Use AND (&) to identify positions for carry, then left-shift by one bit:

1
2
3
4

(a ^ b) =   0 1 1 1 
carry   = 1 0 0 0 0
-------------------
Fina  =   1 0 1 1 1

1
2
3
4
5
6
7
8
9

simpleAddition(a, b):
a      =  1 1 0 1
b      =  1 0 1 0
--------------------
a+b    =  0 1 1 1  

carry(a, b):
carry = 1 0 0 0 0
*shift left by one, because we add the carry next left step :P

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = a & b;  // Get the carry bits
            a = a ^ b;          // Get the sum without carry
            b = carry << 1;     // Shift the carry bits to the left
        }
        return a;  // The result is stored in `a`
    }
}
1
2
3
4
5
6
7

class Solution:
    def getSum(self, a: int, b: int) -> int:
        while b != 0:
            carry: int = a & b  # Get carry bits
            a: int = a ^ b      # Get sum without carry
            b: int = carry << 1  # Shift carry bits to the left
        return a  # Final result is in `a`

Complexity

  • ⏰ Time complexity: O(n), where n is the number of bits in the larger of the two numbers. This is because, in each iteration, at least one higher-order bit of b becomes 0. In the worst-case scenario, it takes O(n) iterations to reduce b to 0.
  • 🧺 Space complexity: O(1), since no additional space is required apart from a constant number of variables (a, b, carry) used during the computation.

Method 2 - Recursive Half Adder

Same approach, but recursive

Code

1
2
3
4
5
6
7
8

class Solution {
    public int getSum(int a, int b) {
        if (b == 0) {
            return a; // Base case: no carry left
        }
        return getSum(a ^ b, (a & b) << 1); // Recursive step
    }
}
1
2
3
4
5

class Solution:
    def get_sum(self, a: int, b: int) -> int:
        if b == 0:
            return a  # Base case: no carry left
        return self.get_sum(a ^ b, (a & b) << 1)  # Recursive step

Complexity

  • ⏰ Time complexity: O(n), where n is the number of bits in the larger of the two numbers.The recursion depth depends on the number of bits in the input numbers. Similar to the iterative solution, there are at most O(n) recursive calls
  • 🧺 Space complexity: O(n). Each recursive call consumes stack space. In the worst case, there will be O(n) recursive calls