# Scala algorithm: Add numbers without using addition (plus sign)

Published

## Algorithm goal

Add two numbers without using addition (+ sign). Can be done with bitwise operations.

For example, 5 + 3 is 8; in binary it is 101 + 011 = 1000.

## Test cases in Scala

```
assert(add(0, 0) == 0)
assert(add(1, 0) == 1)
assert(add(1, 1) == 2)
assert(add(1, 2) == 3)
assert(add(1, 3) == 4)
assert(add(1, 4) == 5)
assert(add(1, 5) == 6)
assert(add(2, 2) == 4)
assert(add(2, 3) == 5)
assert(add(2, 4) == 6)
assert(add(2, 5) == 7)
assert(add(2004, 9123) == 11127)
assert(
add(Int.MaxValue / 2, Int.MaxValue / 2) == (Int.MaxValue / 2) +
(Int.MaxValue / 2),
"We can sum the largest pair of numbers"
)
assert(
{
val ra = scala.util.Random.nextInt(1000000)
val rb = scala.util.Random.nextInt(1000000)
add(ra, rb) == ra + rb
},
"Random pair of digits add up"
)
assert(digitAfterAdding(0, 0, 0) == 0)
assert(carryDigitAfterAdding(0, 0, 0) == 0)
assert(digitAfterAdding(1, 1, 1) == 1)
assert(carryDigitAfterAdding(1, 1, 1) == 1)
assert(digitAfterAdding(1, 1, 0) == 0)
assert(carryDigitAfterAdding(1, 1, 0) == 1)
assert(digitAfterAdding(1, 0, 1) == 0)
assert(carryDigitAfterAdding(1, 0, 1) == 1)
assert(digitAfterAdding(1, 0, 0) == 1)
assert(carryDigitAfterAdding(1, 0, 0) == 0)
assert(digitAfterAdding(0, 0, 1) == 1)
assert(carryDigitAfterAdding(0, 0, 1) == 0)
```

## Algorithm in Scala

19 lines of Scala (version 2.13), showing how concise Scala can be!

## Explanation

Recommended to draw out a table of additions: from the table you learn that binary addition uses the same principles of carrying a number when the base (in this case 2) is exceeded (eg 0b1 + 0b1 = 0b10, and 0b11 + 0b01 = 0b10 + 0b10 = 0b100).

The key tasks here are to add up the number bit-wise, while considering the possibility of a carry-number. (this is Â© from www.scala-algorithms.com)

## Scala concepts & Hints

### Def Inside Def

A great aspect of Scala is being able to declare functions inside functions, making it possible to reduce repetition.

It is also frequently used in combination with Tail Recursion.

### Stack Safety

Stack safety is present where a function cannot crash due to overflowing the limit of number of recursive calls.

This function will work for n = 5, but will not work for n = 2000 (crash with java.lang.StackOverflowError) - however there is a way to fix it :-)

In Scala Algorithms, we try to write the algorithms in a stack-safe way, where possible, so that when you use the algorithms, they will not crash on large inputs. However, stack-safe implementations are often more complex, and in some cases, overly complex, for the task at hand.

### Tail Recursion

In Scala, tail recursion enables you to rewrite a mutable structure such as a while-loop, into an immutable algorithm.