Thursday 5 November 2015

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



To solve this problem, you need to work on binary representation of numbers and bitwise operators.

Approach to solve this problem is:-

-   If you 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.

-   If you add two numbers together but only carry, you will have a 1 in bit[i] if bit[i-1] in a and b are both 1’s.This is an AND, shifted.

-   Now, recurse until there’s nothing to carry.


Sample Program:-

 /**  
  * @author Dixit  
  *   
  */  
 public class AddNumber {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           int a = 2;  
           int b = 3;  
           System.out  
                     .println("Addition of two number without using addition operator:"  
                               + add(a, b));  
      }  
      static int add(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(sum, carry); // recurse  
      }  
 }  


Output:-

Addition of two number without using addition operator:5  

How Solution Works?

-- Initially a=2 and b=3,call add(2,3)

-- Apply the XOR operation on ‘a’ and ‘b’ i.e. 2^3 but don’t consider carry. So you get sum as                        1(0001)

-- Apply (a & b) << 1, returns carry as 4(0100)

-- Call add(1,4) recursive call.

-- Again,Apply the XOR operation on ‘a’ and ‘b’ i.e. 1^4 but don’t consider carry. So you get sum as              5(0101)

-- Apply (a & b) << 1, returns carry as 0(0000)

-- Recursively call (5,0) which returns 5 if ‘b’ is 0.


Enjoy Programming.


1 comment: