Algorithms and Data Structures

Convert Decimal Numbers into Binary

Understanding how to convert decimal numbers (the numbers we use every day) into binary numbers (used by computers) is a fundamental skill in computer science. In the binary system, each digit's position represents a specific power of two. Think of a binary number as a way to indicate which powers of two are needed so that their sum equals the given number.
Number in base-10
128
64
32
16
8
4
2
1
Sum
114
0
1
1
1
0
0
1
0
114 = 64 + 32 + 16 + 2
12
0
0
0
0
1
1
0
0
12 = 8 + 4
13
0
0
0
0
1
1
0
1
13 = 8 + 4 + 1
Each 1 in the binary representation indicates that the corresponding power of two is part of the sum, while each 0 indicates that it’s not. The beauty of the binary system lies in its simplicity and uniqueness.
💡
Each number has one and only one binary representation, which is made up of a sum of distinct powers of two.

Finding the Rightmost Bit

To start, let's consider how to find the rightmost bit in the binary representation of a number. In the decimal system, if we want to find the last digit of a number, we can simply take the remainder when divided by 10, often denoted as % 10 in programming languages. Similarly, in binary, the rightmost bit of a number can be found by taking the remainder when the number is divided by 2, or % 2. This also means that the rightmost bit is always 1 for odd numbers and 0 for even numbers.
For example:
  • For 114 its rightmost bit is equal to 0, since 114 % 2 = 0.
  • For 13 its rightmost bit is equal to 1, since 13 % 2 = 1.

Shifting a Binary Number

Once we've found the rightmost bit, the next step is to shift the entire binary number one position to the right. This operation is equivalent to floor-division of the number by 2 (often denoted as / 2 in most programming languages or // 2 in Python). This operation effectively removes the rightmost bit, making the next bit in line the new rightmost bit.
  • Shifting 114 ( in binary) to the right yields which is equal to 114 / 2 = 57 in base-10.
  • Shifting 13 ( in binary) to the right yields which is 13 / 2 = 6 in base-10.

The Conversion Algorithm

Having these two operations of finding the rightmost bit and shifting the number, we can devise a simple algorithm to convert a decimal number to binary:
  1. Initialize an empty string to store the binary representation.
  1. While the number is greater than 0:
      • Find the rightmost bit by taking the remainder when divided by 2.
      • Add this bit to the left of your binary string.
      • Floor-divide the number by 2 to shift it to the right.
  1. Return the binary string if it’s not empty, and 0 otherwise.
Using this algorithm, you can convert any base-10 number to its unique binary representation.

Minimal Implementation

b, d = '101001101', 0   # binary and decimal numbers
power = 1               # Current power of 2 (1, 2, 4, 8, 16, ...)

for bi in b[::-1]:      # Loop from the least to most significant bit
    d += int(bi) * power
    power *= 2

print(d)
binary → decimal conversion
b, d = '', 5234         # binary and decimal numbers

while d > 0:            # While there are still bits to process
    b = str(d % 2) + b  # Insert the bit to the left of the string
    d //= 2             # Shift the number to the right

print(b if b != '' else 0)
decimal → binary conversion
 
To check your solution you need to sign in
Sign in to continue