Clever Geek Handbook

The logic behind adding two numbers without using +?

I found this code online. But I cannot get the logic of the following code:

public static int add(int a, int b) {
    if (b == 0) return a;
    int sum = a ^ b; // add without carrying
    System.out.println("sum is : "+sum);
    int carry = (a & b) << 1; // carry, but don’t add
    return add(sum, carry); // recurse
}
+3


source to share


4 answers


See an example (using just 8 bits for this)

  a = 10010110
  b = 00111101

a^b

is the xor that gives 1

for places where there is 1

in one number and 0

in another. In our example:

a^b = 10101011

Since 0 + 0 = 0

, 0 + 1 = 1

and 1 + 0 = 1

, the only columns left for consideration are those that have 1

in both numbers. In our example, a^b

is the short answer to



      00010100
    + 00010100

there is. In binary 1 + 1 = 10

, so the answer to the specified amount is

      00101000

or (a & b) << 1

. Therefore, the sum a^b

and (a & b) << 1

coincides with a + b

.

So, assuming the process is complete, the answer is correct. But the process will end, because every time we call sum

recursively, the second parameter has at least one more 0

at the end, due to bit shifting <<

. Therefore, we ensure that we end up with a second argument that is all 0

s, so that the string if (b == 0) return a;

can terminate the process and give us an answer.

+1


source


We add integer-to-bit conversion and use of bitwise operators.

EXOR ie ^: 0 ^ 0 and 1 ^ 1 = 0, other cases give 1.

And ie and 1 ^ 1 = 1, other cases give 0.

<<or left shift. shift left and add 0 bits: 0010 will become 0100



eg.

add(2,3)

2= 0010
3=0011

exor both : to get initial sum :  0001

carry : a &b = 0010  

Left shift by 1 bit : 0100 i.e 4

add(1,4)

exor both : 0001 0100 and u get 0101 i.e 5

carry = 0000 <<1 i.e 0000 ..

since carry is 0 it stops adding and returns the previous sum

+1


source


Consider for example 5+7

:

5     = 101 (Base 2)
7     = 111 (Base 2)

Now let's look at adding two (base 2) digits:

0+0 =  0 = 0 carry 0
1+0 =  1 = 1 carry 0
0+1 =  1 = 1 carry 0
1+1 = 10 = 0 carry 1

The sum (without carry) A+B

is equal A^B

, and the carry is A&B

; and when you carry a number, it is shifted one digit to the left (hence (A&B)<<1

).

So:

5    =  101 (Base 2)
7    =  111 (Base 2)
5^7  =  010 (sum without carrying)
5&7  = 101  (the carry shifted left)

Then we can re-add the wrap:

A    =   010
B    =  1010
A^B  =  1000 (sum without carrying)
A&B  = 0010  (the carry shifted left)

Then we can go back again, as we carry even more:

A'    =  1000
B'    =   100 (without the leading zeros)
A'^B' =  1100 (sum without carrying)
A'&B' = 0000  (the carry shifted left)

Now there is nothing to bear - so we can stop and the answer 1100 (base 2) = 12 (base 10)

.

The algorithm simply implements decimal addition as a (long) binary addition using or

for append and bit-shifted and

to find the carry and will return until there is nothing else to carry (which will always be the case as the bit-shift adds another zero to the carry every time, so when each recursion at least one bit will not generate a carry value every time).

+1


source


This is the table to add:

+   0  1
   -- --
0 | 0  1
1 | 1 10
      ▲

If you ignore the carry bit ▲

, you will see that it is the same as the XOR table:

^   0  1
   -- --
0 | 0  1
1 | 1  0

So, if you combine two numbers with a bitwise XOR, you get a bitwise complement with no carry.

Now what is transfer? It's a bit that only there when both inputs are 1.

You can get it with AND:

&   0  1
   -- --
0 | 0  0
1 | 0  1

But it must be added to the sum after shifting one position to the left, because it is "carried over", hence (a & b) << 1

So you can compute the addition without carry and carry itself. How do you add them together without using the add-on? Just! Recursive by this very definition of add!

See @pbabcdefp's answer on why the recursion always completes.

0


source






More articles:


All Articles