Add Two Numbers Without the Addition Sign (Ruby)

A weird interview question for software development interviews is “add these two numbers without using the plus sign.” I was taken aback by how zen-like and strange this question sounds at first, but by using a bit of binary math I was able to solve it.

My First Approach

Example input: Add 5 and 8

In ruby, the to_s method can turn Fixnums into their binary form.

I’m going to add a “0” to the start of the binary representation of five so it’s the same length as the eight.

Adding 5 to 8 is a special case because there is no instance where you have to carry the one. My naive first approach was to use the | (or) operation on each digit and you will get the desired result.

0101 | 1010 => 1101

Because,

0 | 1 => 1

0 | 0 => 0

1 | 0 => 1

0 | 1 => 1

So our answer is “1101”, which is equal to our goal, 13. (1 + 4 + 8)

However, this will not work with something like 4 + 4. The binary form of 4 is “100” and 8 is “1000”. Trying the naive approach above,

100 | 100

0 | 0 => 0

0 | 0 => 0

1 | 1 => 1

100 + 100 = 100? Something went wrong. So, we need to literally “carry the one” when both digits equal 1

0 ? 0 => 0

1 ? 0 => 1

1 ? 1 => 10

0 ? 1 => 1

It took me quite a bit of trial and error to tackle this problem, but here is my solution.

The Plan

(1) Helper function to go from a decimal number to a binary number array, e.g., 5 -> [1, 0, 1]

(2) Helper function to add zeros to the front of the shorter array to equalize the length of two binary arrays, e.g.,

[1, 0, 1] and [1, 0, 0, 0] become

[0, 1, 0, 1]  and [1, 0, 0, 0]

(3) Function to add bits, e.g., 0 & 0, 1 & 0, and also take into account ‘carrying’ bits over.

(4) Function to add the entire binary array

(5) Function to convert back from binary array to decimal

(6) Function that puts it all together! Input two decimal numbers and output their sum.

The Ruby Program 

(1) Decimal to binary array

#input: decimal e.g. 5
#output: binary array e.g. [1,0,1]
def dec_to_bin_array(dec_num)
  #turn into array of string chars
  bin = dec_num.to_s(2).chars
  #convert to integers
  bin.map(&:to_i)
end

(2) Equalize length of two binary arrays

#input: two arrays of 0s and 1s
#insert leading zeros to beginning of shorter array to equalize length
def equalize_length(arr1, arr2)
  while arr1.length < arr2.length
    arr1.unshift(0)
  end
  while arr2.length < arr1.length
    arr2.unshift(0)
  end
end

(3) Add bits together and take into account carry operations

#input: bit1, bit2, amount to carry
#output: [digit to carry over, digit to insert to end of sum]
def add_bits(bit1, bit2, carry)
  return [1, 1] if bit1 == 1 && bit2 == 1 && carry == 1
  return [1, 0] if (bit1 == 1 || bit2 == 1) && carry == 1
  return [0, 1] if (bit1 == 0 && bit2 == 0) && carry == 1
  return [1, 0] if bit1 == 1 && bit2 == 1 && carry == 0
  return [0, 1] if (bit1 == 1 || bit2 == 1) && carry == 0
  [0, 0]
end

(4)  Add each bit of the arrays together to form the bit sum

def add_binary_arrays(arr1, arr2)
  sum = []
  equalize_length(arr1, arr2)
  carry_digit = 0
  while !arr1.empty?
    m = arr1.pop
    n = arr2.pop
    v = add_bits(m, n, carry_digit)
    carry_digit = v[0]
    sum.unshift(v[1])
  end
  sum.unshift(carry_digit)
  sum
end

(5) Go from binary array to decimal (recursive approach)

def bin_array_to_dec10(arr, n = 0, pow = 0)
  return n if arr.empty?
  n += arr.pop * (2**pow)
  bin_array_to_dec10(arr, n, pow + 1)
end

(6) Put all the above together to get the answer.

#input: two base10 numbers
#output: their sum 🙂
def add_two_numbers_using_bitwise_operations(a, b)
  m = dec_to_bin_array(a)
  n = dec_to_bin_array(b)
  v = add_binary_arrays(m, n)
  bin_array_to_dec10(v)
end

I found this problem enjoyable to work through because it helped me understand one of the most fundamental operations performed by the computer.

Leave a Reply

Your email address will not be published. Required fields are marked *