Decimal to Binary

While I am spending most of my time at RC focusing on algorithms and data structures, there are a handful of smaller areas of interest that I wanted to investigate. One of these items is: why is the binary number system so prevalent in computing?

Why use a base-2 number system?

CPU computations use bits to store pieces of information as ‘0’ and ‘1’ digits; it’s a binary number system (a base-2 number system) that maps to no-voltage (0) and a voltage (1) for computational tasks. Because a computer is an electronic device, this makes sense given a current is flowing or not flowing. Hypothetically, more than two voltages can be used for computations, but it risks miscalculations due to voltages being slightly off. The binary format ensures computations are exact.

Converting Decimal to Binary

The decimal system uses a base-10 system; each place value uses a consecutive power of 10. In comparison, the base-2 system uses…you guessed it, a consecutive power of 2 for each place value.

To calculate the base-2 of a decimal number, get the largest value of 2ⁿ that fits into the most significant digit. For 2017, that’s 2¹⁰. The next largest is 2⁹. The process is repeated until the values in each place add up to the decimal number.

This can get somewhat tricky, as you don’t want to calculate a decimal number larger than the one desired. In the above image, 2⁴ to 2² are 0. Why? because giving those place values a 1 will give us a different decimal number (one that is larger than 2017). It isn’t until 2⁰ that we include a place value again.

This logic can be converted to an algorithm. We can do the following to calculate the base-2 of a decimal number:

def dec_to_bin(n):
    nums = []
    while n > 0:
        nums.insert(0, n%2)
        n = n/2
    return int(''.join(map(str, nums)))

What’s happening here? The function accepts an integer as a parameter n, and it decreases n by half on each iteration of the while-loop. Inside each iteration, it calculates the remainder using modulo (or mod for short) of 2 (which is the base of the base-2 system).

What is mod doing exactly? Given a dividend and a divisor:

dividend: 15

divisor: 2

perform integer division ⌊dividend/divisor⌋

15 \ 2 => 7

multiply the result of the integer division (7) by the divisor (2)

7 * 2 => 14

subtract the result of the multiplication (14) from the dividend (15):

15 - 14 => 1

15 % 2 = 1

The function pushes the remainder to the head of the list. Why not just append to the tail? the remainders are calculated from largest n to smallest n, so prepending to the end of the list would give us the reverse binary.

It could be argued that appending to the end of the list during the while-loop iterations, then reversing the list is more performant. After all, inserting to the head of the list means all list items are being copied over one index position upon each insertion, followed by a possible resize.

Finally, each integer item in the list is converted to a string, concatenated, and then returned to an integer.

Or…just use bin() :)

What’s next?

I am planning on writing follow up posts on hexidecimal format, signed versus unsigned integers, and bit manipulation in the future.

Resources used

Kenneth R. Koehler - Binary and Hexadecimal Numbers Stack Overflow: how does modulus division work?