Add two numbers without using of arithmetic operators

Write a function that adds two numbers You should not use + or any arithmetic operators.

My initial thoughts:
We should take care of two things: adding and carry. Addition can be done using XOR(^). Carry can be done using AND(&). The only tricky part is that when we have two bits like 1 and 0 but then we have carry from previous position, then 1 & 0 = 0 suggests no carry but actually 1 + 0 + 1 will produce a carry. So we branch into two case: 1 + 1 will definitely produce a carry no matter what; 1 + 0 + 1 will produce new carry.

My initial codes:

	public static int add(int a, int b) {
		int result = 0;
		int carry = 0;
		for (int i = 0; i < Integer.SIZE; ++i) {
			int bitIAtA = a & (1 << i);
			int bitIAtB = b & (1 << i);
			carry &= (1 << i);
			result |= bitIAtA ^ bitIAtB ^ carry;
			carry |= ((bitIAtA & bitIAtB) << 1 | ((bitIAtA ^ bitIAtB) & carry) << 1);
		}
		return result;
	}

Solution:
To investigate this problem, let’s start off by gaining a deeper understanding of how we add numbers. We’ll work in Base 10 so that it’s easier to see. To add 759 + 674, we would usually add digit[0] from each number, carry the one, add digit[1] from each number, carry the one, etc. You could take the same approach in binary: add each digit, and carry the one as necessary.
Can we make this a little easier? Yes! Imagine we decided to split apart the “addition” and “carry” steps. That is, we do the following:

  1. Add 759 + 674, but “forget” to carry we then get 323
  2. Add 759 + 674 but only do the carrying, rather than the addition of each digit. We then get 1110
  3. Add the result of the first two operations (recursively, using the same process de- scribed in step 1 and 2): 1110 + 323 = 1433

Now, how would we do this in binary?

  1. If we add two binary numbers together but forget to carry, bit[i] will be 0 if bit[i] in a and b are both 0 or both 1. This is an XOR
  2. If we add two numbers together but only carry, we will have a 1 in bit[i] if bit[i-1] in a and b are both 1’s. This is an AND, shifted
  3. Now, recurse until there’s nothing to carry
	public static int add_no_arithm(int a, int b) {
		if (b == 0)
			return a;
		int sum = a ^ b; // add without carrying
		int carry = (a & b) << 1; // carry, but don't add
		return add_no_arithm(sum, carry); // recursion
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: