Thursday, July 22, 2010
Add two integers
22nd, July 2010
Adding two integers without arithmetic operator
I heard this question multiple times, it is to judge our ability to link our understanding of digital circuits. I know, we can have some out-of-the box solutions. Given below, how I got the solution.
From digital circuits, recap that half adder can add two bits and full adder can add two bits along with carry bit, i.e. three bits. Can we augment the same logic here in software? The bitwise AND generates carry and XOR generates sum. C/C++ provides low level features to access bit level information.
Having understood the adder circuit logic, our algorithm can be depicted in the following steps,
1. Inputs operands M and N
2. Set sum = M XOR N
3. Repeat the following steps until no carry
a. Shift left the previously generated carry
b. Save intermediate sum
c. Update sum = sum XOR carry
I have provided working code in the following links, http://ideone.com/gNi77 Try with negative numbers.Question asked here http://geeksforgeeks.org/?p=8198#comment-1722