Add Two Integers Using Only Bitwise Operators

Add two integers using only bitwise operators?

Here is an example for your amusement

unsigned int myAdd(unsigned int a, unsigned int b)
{
    unsigned int carry = a & b;
    unsigned int result = a ^ b;
    while(carry != 0)
    {
        unsigned int shiftedcarry = carry << 1;
        carry = result & shiftedcarry;
        result ^= shiftedcarry;
    }
    return result;
}

The loop could be unrolled. Number of times it executes, depends on the number of bits set in operands, but it's never greater than the width of unsigned int. Once carry becomes 0, next iterations don't change anything.

Total of two numbers ONLY with bitwise operators?

You say in the comments that the inputs must be no greater than 10^5. In that case, a finite number of carry propagation steps will suffice to eliminate the carry term and produce a final sum:

def binop_add(x, y):
    sum, carry = x, y
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 1
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 2
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 3
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 4
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 5
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 6
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 7
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 8
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 9
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 10
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 11
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 12
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 13
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 14
    sum, carry = (sum ^ carry), (sum & carry) << 1 # 15
    # assert carry == 0
    return sum

Each round of sum, carry = (sum ^ carry), (sum & carry) << 1 preserves the invariant that sum + carry == x + y. After each round, carry must end in at least one more 0 bit.

After 15 rounds, carry must end in at least 15 zero bits. For carry to be nonzero at this point, carry would have to be at least 1 << 15, which is 32768, higher than is possible. At this point, carry must be 0, so sum + carry == sum == x + y, and we return sum.

What is the best way to add two numbers without using the + operator?

In C, with bitwise operators:

#include<stdio.h>

int add(int x, int y) {
    int a, b;
    do {
        a = x & y;
        b = x ^ y;
        x = a << 1;
        y = b;
    } while (a);
    return b;
}

int main( void ){
    printf( "2 + 3 = %d", add(2,3));
    return 0;
}

XOR (x ^ y) is addition without carry. (x & y) is the carry-out from each bit. (x & y) << 1 is the carry-in to each bit.

The loop keeps adding the carries until the carry is zero for all bits.

Bitwise operations to add two numbers?

Yes. This approach does not work for additions that involve multiple carries. The simplest such case is 3 + 1; your function gives 0 as a result.

There is no simple general-case solution to solve this -- any solution must take into mind the width of an integer. See Wikipedia's article on gate-level implementations of addition for some approaches.

Sum of two numbers with bitwise operator

Think in entire bits:

public static int getSum(int p, int q)
{
    int result = p ^ q; // + without carry 0+0=0, 0+1=1+0=1, 1+1=0
    int carry = (p & q) << 1; // 1+1=2
    if (carry != 0) {
        return getSum(result, carry);
    }
    return result;
}

This recursion ends, as the carry has consecutively more bits 0 at the right (at most 32 iterations).

One can easily write it as a loop with p = result; q = carry;.

Another feature in algorithmic exploration is not going too far in differentiating cases.
Above you could also take the condition: if ((result & carry) != 0).

Add two numbers using bit manipulation

At each iteration, you have these steps:

carry <- x & y   // mark every location where the addition has a carry
x <- x ^ y       // sum without carries
y <- carry << 1  // shift the carry left one column

On the next iteration, x holds the entire sum except for the carry bits, which are in y. These carries are properly bumped one column to the left, just as if you were doing the addition on paper. Continue doing this until there are no more carry bits to worry about.

Very briefly, this does the addition much as you or I would do it on paper, except that, instead of working right to left, it does all the bits in parallel.

Adding two numbers without + operator (Clarification)

I find this a bit tricky to explain, but here's an attempt; think bit by bit addition, there are only 4 cases;

0+0=0 
0+1=1 
1+0=1 
1+1=0 (and generates carry)

The two lines handle different cases

sum = a ^ b

Handles case 0+1 and 1+0, sum will contain the simple case, all bit positions that add up to 1.

carry = (a & b) << 1

The (a & b) part finds all bit positions with the case 1+1. Since the addition results in 0, it's the carry that's important, and it's shifted to the next position to the left (<<1). The carry needs to be added to that position, so the algorithm runs again.

The algorithm repeats until there are no more carries, in which case sum will contain the correct result.

Btw, return sum should be return a, then both sum and carry could be regular local variables.

---

Related Topics