Geek Answers Handbook

How to add numbers without +

I was asked this question in an interview. I did not answer, and in fact I do not understand how this works.

int add(int x, int y) { while (y != 0) { int carry = x & y; x = x ^ y; y = carry << 1; } return x; }

I do not ask why it gives the correct answer ... First of all, why does the algorithm eventually stop? This is not so obvious to me.

To stop it, carry must be 0 . Can anyone explain this in a nutshell?

+5
source share
3 answers
 line 1 : int carry = x & y; line 2 : x = x ^ y; line 3 : y = carry << 1;

if x = 1; y = 2;

Binary for each number:

0 = 00

1 = 01

2 = 10

3 = 11

for line code 1,

& (bitwise AND) The binary AND operator copies a bit to the result if it exists on both operands

x is 1 => 01

y is 2 => 10

result carry is => 00 (0)

for line code 2,

^ (bitwise XOR) The binary XOR operator copies a bit if it is set on one operand but not both.

x is 1 => 01

y is 2 => 10

result x is => 11 (3)

for line 3 code, the carry variable requires a left shift for 1 bit, so now carry 0 => 00 and a 1 bit left shift means that the carry is now 0. The result y is (0). And while the loop stops, because y is now 0.

The final result for x is 3.

Hope this helps you.

+6
source

Take an example:

 x=13(1101) y=9(1001) Loop 1: ----------------- y!=0 -> carry=(1101)&(1001)=1001(9) [AND Op] x=(1101)^(1001)=0100(4) [XOR Op] y=carry<<1 -> y=(carry)x2=10010(18) Loop 2: ----------------- y!=0 -> carry=(0100)&(10010)=00000(0) x=(0100)^(10010)=10110(22) y=carry<<1 -> y=0 loop terminated.

therefore, x is equal to 22.So, x ^ y stores the total part and x & y stores the carrier part, and then the transfer (x & y) is shifted according to the digit with x ^ y and ultimately XOR them and store in x. x is the result.

+2
source

Briefly about using y (and "carry / x & y" it becomes) to change x until it becomes the sum of both ints. For instance,

 y=1 (....0001), x=anything (either .....0 or .....1) if x ends with 0, x&y=0 //x^y = x becomes ....001 (thereby adding 1) //since x&y=0 the loop stops if x ends with 1, x&y=1 //x^y = x //since y= x&y<<1, new y=(.....000010) if x ends with 01, x&y=0 //x^y = x becomes ....010 (thereby adding 1) //since x&y=0 the loop stops if x ends with 11, x&y=1 //x^y = .....01 //since y= x&y<<1, new y=(......000100) if x ends with 011 //stuff happens and x becomes ....100 (thereby adding 1) //loop stops if x ends with 111 //... //if x ends with 111111, x becomes ....1000000 (thereby adding 1) //if x ends with 1111111, x becomes ....10000000 (thereby adding 1) //if x ends with 11111111, x becomes ....100000000 (thereby adding 1) //well you get the idea

The same logic applies to all y values ​​and does not differ much from ordinary addition only in that now instead of 2 (from 0 to 9) there are 2 possible digits (0 and 1).

+1
source

More articles:


All Articles