Coding Challenge: Converting Integers to Binary String Representations in Ruby

Lately I've been trying to challenge myself by taking a stab at some common coding questions asked in software engineering job interviews. After years of working on apps you would think that this kind of thing comes easy, but software development in the modern age comes with a heavy side of Googling and lookup, so challenging your brain in this way to implement an algorithm or process from just its definition is good practice to keep you sharp.

I had come across a practice coding question which required me to compare integers and binary strings, and I realized that I had forgotten how to convert an integer to binary. Looking it up, the algoritm is pretty simple:

To convert integer to binary, start with the integer in question and divide it by 2 keeping notice of the quotient and the remainder. Continue dividing the quotient by 2 until you get a quotient of zero. Then just write out the remainders in the reverse order.
Angular in Depth

Here's how I implemented that in ruby.

Basically, we need to keep dividing by 2 and record the remainder, so this sounds to me like a while loop, or even a recursive function. I'll implement both here, and at the end, I'll show you an even easier method to use with built-in ruby methods. We will only deal with integers >= 0, and output a string representation of the integer written in binary. For example, an input of 9 would output "1001", and an input of 1337 would output "10100111001".

Starting with a simple test case to prove our results are correct:

def convert_to_binary(integer)
  return integer.to_s
end

integer = 1337
binary = convert_to_binary(integer)
puts "CORRECT: #{binary == '10100111001'}\n#{integer} -> #{binary}"

Running that of course is going to fail:

CORRECT: false
1337 -> 1337

So let's get to work implementing the while method. We want to take the input n and divide it by 2, but how do we do that while "keeping notice of the quotient and the remainder"? We can get the quotient by simply running a standard divide by the integer 2, as ruby will always round down. If we divide by a float 2.0, ruby would provide a float return and we could see if the portion to the right of the decimal was > 0 or not, but I think there is a better way using the mod operator: %. This mod operator only returns the remainder as an integer, not as a fraction. Because we are dividing by 2, the remainder will always be either 1 or 0, and thus the mod will always return either 1 or 0, already conveniently in base2, or binary representation.

def convert_to_binary(integer)
  binary = []
  while integer > 0
    binary << integer % 2
    integer /= 2
  end
  binary.reverse.join
end

Line by line, we first initialize an empty array to hold the binary digits. We do a while loop over integer while it is sill larger than 0, and on each iteration we add the remainder of a mod operation to the empty binary array, then divide our integer by 2 for the next iteration. After we have hit 0, the binary array will be holding all of our digits, but in the wrong order, and as integers. So we reverse the array, then join it, which will automatically convert each array value to a string and concatenate them.

Running this through the test gives:

CORRECT: true
1337 -> 10100111001

Ok so this works, is easy to understand, and is relatively short. Let's try to make it recursive. Whatever is in the while loop should be able to be pulled out and recursed upon. The base case would be when we have an integer of 0 or 1, we can simply return that integer. Because we can combine the elements in the correct order as part of our recursive step, we don't need an array, and will call to_s on the base case and the remainder to always return a correct binary string representation.

def convert_to_binary_recursive(integer)
  if integer <= 1
    integer.to_s
  else
    convert_to_binary_recursive(integer / 2) + (integer % 2).to_s
  end
end

Running this through the test also gives correct results:

CORRECT: true
1337 -> 10100111001

Let's expand our testing a little bit by checking all numbers 0 through n, and testing them out. How can we test for correctness without manually typing out each value's string representation? Here is where I show you the much easier built-in method for converting that already exists in ruby. Are you ready for it?

integer.to_s(2)

A ruby Integer has the ability to change its base through the to_s method. To convert an integer to binary, being base 2, you simply call .to_s(2) to get the binary string representation. Knowing this, we can write a test suite to check the correctness of our method much more exhaustively, with over 1 million checks.

n = 2**20

%i(convert_to_binary convert_to_binary_recursive).each do |method|
  failed = []
  t1 = Time.now
  (0..n).each do |i|
    binary = self.send(method, i)
    correct = (binary == i.to_s(2))
    failed << i if !correct
  end
  t2=Time.now
  puts "\n#{method}"
  puts " - CORRECT: #{failed.empty?}"
  puts " - FAILED: #{failed}" if failed.any?
  puts " - #{t2-t1}sec"
end

convert_to_binary
- CORRECT: false
- FAILED: [0]
- 6.815202sec

convert_to_binary_recursive
- CORRECT: true
- 3.98154sec

Running this, we spot an error! Turns out the while loop method fails for 0. Let's add a simple check for that edge case:

def convert_to_binary(integer)
  return integer.to_s if integer <= 1

  binary=[]
  while integer > 0
    binary << integer % 2
    integer /= 2
  end
  binary.reverse.join
end

Running the fix, we are all good now.

  convert_to_binary
  - CORRECT: true
  - 7.444135sec

  convert_to_binary_recursive
  - CORRECT: true
  - 4.553685sec
  

So, the recursive method is about twice as fast as the iterative one, but how does they compare to the native method? Let's add a third method convert_to_binary_native and run the tests again.

def convert_to_binary_native(integer)
  integer.to_s(2)
end

convert_to_binary
- CORRECT: true
- 7.444135sec

convert_to_binary_recursive
- CORRECT: true
- 4.553685sec

convert_to_binary_native
- CORRECT: true
- 0.710849sec

Ruby's implementation is faster by an order of magnitude. Their implementation of to_s on a Fixnum bubbles down a couple of lower level methods until it hits a core C function in the numeric.c source. It's been awhile since I've worked in C, but it appears that there is a base case when the number is 0, then a do/while loop which the current digit is shifted and modded by the base. This method is essentially what we have in our convert_to_binary method as defined above, but is obviously much faster as it is written in pure C.

Was this page helpful for you? Buy me a slice of 🍕 to say thanks!