Decimal to Binary

excerpt: This covers iterative and recursive implementation of constructing base 2 expansions. tags: modulo-operator reduce-input-value tail-recursion

The basic building blocks such as modulus, reduce input and tail recursion is discussed in this article.

Iterative Implementation

Constructing Base 2 Expansions

A decimal number 𝑛 requires approximately log2 𝑛 bits for its binary representation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def binary_expansion(n)
  result = []
  
  while n > 0
    element = n % 2
    result << element
    n = n / 2
  end

  result  
end

result = binary_expansion(8)

while !result.empty?
  print result.pop
end

Building Blocks

• Modulus
• Reduce Input

Recursive Implementation

The recursive implementation for constructing base 2 expansions:

1
2
3
4
5
6
7
8

def binary_expansion(n)
  if n > 0
    binary_expansion(n/2)
    print n % 2
  end
end

binary_expansion(12)

Building Block

• Tail Recursion