Thursday, September 21, 2023

How to Add Two Integer Numbers without using Plus + or ++ Arithmetic Operator in Java - Recursion example

In this article, we will take a look at another interview question about adding two numbers, but without using the + or ++ operator. The interview starts with a simple statement, Can you write a function to add two numbers (integers) without using + or plus arithmetic operator in Java? If you are good at maths, it wouldn’t take more than a second to say that, we can use subtraction or - operator to add two numbers because a-(-b)== a+b. Well, that’s correct, but the real question starts when the interviewer quickly points out that, you can not use any arithmetic operator including +,-,*,/++, or --

Programming and Coding questions are an integral part of any Java interview. You should always expect a couple of questions like this, e.g. swapping two numbers without using a temp variable

If you have been giving interviews, then you know that it will eventually come downs to the bitwise operator in Java. 

Yes, we can add two numbers by using bitwise and bit shift operators, which is not arithmetic. The interviewer will be happy by hearing a bitwise operator, but he would like to see the code. 

Well, if you know binary arithmetic or how to add numbers in binary format, you may be familiar with fact that the sum of two numbers can be obtained by using XOR operation and carry, by using AND operation

This is the fact, you must remember to solve this question or add two integers without using any arithmetic operator e.g. plus, minus etc. 

Sometimes interviewer may ask you to write both iterative and recursive solutions of the same question Since recursion is another confusing programming technique, it's favored more during interviews. 

In this Java tutorial, we will see both recursive and iterative versions of our add method, which calculates the sum of two numbers without using an arithmetic operator but using bitshift and bitwise operators in Java.




1. Iterative Solution to add two integers without using Arithmetic operator

How to add two integers without using plus arithmetic operator in JavaThe iterative solution uses any kind of loop, e.g. for, while, or do-while. As I said, the sum of two integers can be obtained by XOR bitwise operator, and carry can be obtained but AND bitwise operator. We also need to use a signed left shift Java operator to add carry into sum. Here is code for the iterative method to add two integers without using the plus or minus operator :

 public static int addIterative(int a, int b){  
        while (b != 0){
            int carry = (a & b) ; //CARRY is AND of two bits
          
            a = a ^b; //SUM of two bits is A XOR B
          
            b = carry << 1; //shifts carry to 1 bit to calculate sum
        }
        return a;
 }

Code is self-explanatory, we are calculating carry and keeping it in a separate variable, then we are storing the sum of two numbers into variable a, and shifts carry to 1 bit by using signed left shift operator, In order to add into sum.



2. Recursive Solution to add two integers without using Plus

The following method uses the recursion programming technique to calculate the sum of two numbers without an arithmetic operators e.g. +, - etc. It's a recursive version of our earlier iterative solution. 

Just like in the loop, we are testing for b=0, here also we are doing the same thing. We have just combined & bitwise and << signed left shift operator calculating and shifting carry.

public static int add(int a, int b){
        if(b == 0) return a;
        int sum = a ^ b; //SUM of two integer is A XOR B
        int carry = (a & b) << 1;  //CARRY of two integer is A AND B
        return add(sum, carry);
 }



3. How to add two integers without arithmetic operator Java Example

Here is a complete code example, which includes both iterative and recursive methods along with a simple JUnit test. I have tested both add methods for a couple of edge cases e.g. adding negative numbers, Integer.MAX_VALUE, adding zero, etc.

/**
 * Java program to calculate the sum of two number without using addition or subtraction
 * operator in Java. This solution, use bitwise and bitshift operator instead of maths operator.
 * @author Javin Paul
 */
public class AddTwoNumbersJava {
  
    public static void main(String args[]) {
      
       System.out.println(" Sum of 110 add 200 is : " + add(110, 200));
       System.out.println(" Sum of 0 and 0 is : " + add(0, 0));
       System.out.println(" Sum of -10 and +10 is : " + add(-10, 10));
       System.out.println(" Sum of -10 + 200 is : " + add(-10, 200));
       System.out.println(" Sum of 0 + 200 is : " + add(0, 200));
     
    }  
  
    /*
     * Adding two number without using + or plus arithmetic operator using
     * recursion in Java. This method uses XOR and AND bitwise operator to
     * calculate sum of two numbers;
     */
    public static int add(int a, int b){
        if(b == 0) return a;
        int sum = a ^ b; //SUM of two integer is A XOR B
        int carry = (a & b) << 1;  //CARRY of two integer is A AND B
        return add(sum, carry);
    }
 
    /*
     * Adding two integers without any arithmetic operator and using recursion.
     * This solution also uses XOR and AND bitwise and << left shift bitshift
     * operator
     */
    public static int addIterative(int a, int b){ 
        while (b != 0){
            int carry = (a & b) ; //CARRY is AND of two bits
          
            a = a ^b; //SUM of two bits is A XOR B
          
            b = carry << 1; //shifts carry to 1 bit to calculate sum
        }
        return a;
    }
 
}

Output:
Sum of 110 add 200 is : 310
Sum of 0 and 0 is : 0
Sum of -10 and +10 is : 0
Sum of -10 + 200 is : 190
Sum of 0 + 200 is : 200

And here is the JUnit test case to test add() and addIterative() method, If you notice carefully, I have used the static import feature of Java 1.5, to import various assert methods like assertEquals(expected, actual)

By the way, I just realized that I made an error here, which won't affect the result but it's a mistake. If you can point it out then let me know :

import org.junit.Test;
import static org.junit.Assert.*;
import static test.AddTwoNumbersJava.*;

/**
 * JUnit tests for addition without using maths operator in Java.
 * @author
 */
public class AddTwoNumbersJavaTest {  

    /**
     * Test of add method, of class AddTwoNumbersJava.
     */
    @Test
    public void testAdd() {
        assertEquals(add(0, 0), (0 + 0));
        assertEquals(add(100, 210), (100 + 210));
        assertEquals(add(-10, 10), (-10 + 10));
        assertEquals(add(0, 200), (0 + 200));
        assertEquals(add(10, 0), (10 + 0));
        assertEquals(add(Integer.MAX_VALUE, 10), (Integer.MAX_VALUE + 10));
    }

    /**
     * Test of addIterative method, of class AddTwoNumbersJava.
     */
    @Test
    public void testAddIterative() {
        assertEquals(addIterative(0, 0), (0 + 0));
        assertEquals(addIterative(100, 210), (100 + 210));
        assertEquals(addIterative(-10, 10), (-10 + 10));
        assertEquals(addIterative(0, 200), (0 + 200));
        assertEquals(addIterative(10, 0), (10 + 0));
        assertEquals(addIterative(Integer.MAX_VALUE, 10), (Integer.MAX_VALUE + 10));
    }
}



That's all on How to add two numbers without using the plus + arithmetic operator in Java. As I said, you need to remember that sum of two integers in binary is equal to the XOR of two numbers, and carry is equal to AND operation of two numbers.

By using bitwise and bit shift operators in Java, you can easily calculate the sum of two numbers without any arithmetic operator.

Further Reading on Bit Twiddling
Bitwise and bit shift operators are quite extensively used in programming interviews, and many problems like the above can be solved by their usages. 

Hackers delight is one of the greatest books on writing code using bit twiddling and bit manipulation and in fact, the Java library uses many bit twiddling techniques from this book.

The Art of Computer Programming by Donald E. Knuth
Cracking the Coding Interview: 150 Programming Questions and Solutions
Hacker's Delight (2nd Edition) By Henry S. Warren



And, now quiz time? What is difference between && and & operator in Java? and | and || operator in Java? Can we use one in place of other?

6 comments :

Anonymous said...

Another solution would be to use BigInteger:

public static int add(int a, int b) {
BigInteger i = BigInteger.valueOf(a);
BigInteger j = BigInteger.valueOf(b);
BigInteger sum = i.add(j);
return sum.intValue();
}

Anonymous said...

Nice post!!!
Can you please post the explanation of why it works?
I mean mathematically or some other proof..
I can see it works for every integer, but i can't understand why it works?

Unknown said...

Good day, my assignment is similar to this can you help me??? I really dont know what to do. My professor posted this: Objectives:
- To let the participants experience the use of loops and operators.

Create a Java Application using the class BasicMathOperation. The application will initialize two integer values and display the ff:
a. Product without using the multiplication (‘*’) operator.
b. Integer quotient without using the division (‘/’) operator.
c. Integer remainder without using the modulo (‘%’) operator.
d. Take note that inside the whole code, you are NOT allowed to use the ff: operators: ‘*’, ‘/’, and ‘%’.

Save your file as ICS112_Section_Exercise3_Surname_ComputerNumber.java (ie: ICS112_1ITB_Beltran_25.java)

Class BasicMathOperation UML Diagram
BasicMathOperation
- operand1 : int
- operand2 : int
//constructor
+ BasicMathOperation(int num1, int num2)
//setters
+ setOperand1(int num1) : void
+ setOperand2(int num2) : void
//getters
+ getOperand1() : int
+ getOperand2() : int
//basic methods
+ multiplyUsingLoop() : int
+ divideUsingLoop() : int
+ moduloUsingLoop() : int
Note: To avoid division by zero, the operand2 must have no value of zero. Same is true to modulo by zero, that is, the operand2 must have no value of zero. And this condition must be checked in the methods divideUsingLoop() and moduloUsingLoop(). If this happen, the output is “Error division by zero” or “Error modulo of zero”, respectively. And the program exit using the command System.exit(1).

Samrat said...

Want its mathematical proof.How it works?

Anonymous said...

can you tell me how many times the while loop gets executed
while (b != 0){
int carry = (a & b) ; //CARRY is AND of two bits

a = a ^b; //SUM of two bits is A XOR B

b = carry << 1; //shifts carry to 1 bit to calculate sum
}
So I wanted to write it as a for loop
Could anyone help me

Unknown said...

Can you please discuss the complexity of code

Post a Comment