CPSC120
Fundamentals of Computer Science

Binary Representation of Positive Integers

Binary Vs Decimal

Computers use binary, or base 2, to represent numbers. Binary numbers have only 2 symbols, 0 and 1, to represent numbers. Decimal, or base 10, is the number representation system you learned as a child that has 10 symbols, 0 through 9, to represent numbers. People probably adopted the decimal number system because it was convenient to count using 10 fingers. Although there are some cultures that count using the gaps between fingers so they use octal, or base 8, to represent numbers. Computers, however, use binary because it is easier to build computers that only represent two symbols. Although there have been computers built that use decimal, including the first electronic programmable computer ENIAC.

Digits

In decimal numbers, a digit is a single symbol, from 0 to 9. Decimal numbers require multiple digits to represent numbers larger than 9. When representing numbers larger than 9, the location, or place, of a digit determines how much it represents. For example, in the number 123 the digit 1 represents a hundred while the digit 2 represents twenty. Therefore, the decimal number 123 can be rewritten in the following way.

123 = 1 ⋅ 100 + 2 ⋅ 10 + 3 ⋅ 1

Note that the multipliers in the above equation can be rewritten using exponents as follows:

123 = 1 × 10² + 2 × 10¹ + 3 × 10⁰

This equation is useful because it makes it clear how the base, 10, is expressed in this definition of a decimal number.

Bits

In binary numbers, a bit is a single symbol, 0 or 1. Binary numbers require multiple digits to represent numbers larger than 1. When representing numbers larger than 1, the location, or place, of a bit determines how much it represents. Just as with decimal numbers, binary numbers can be rewritten using an equation that utilizes multipliers of the base, 2, raised to sequentially decreasing powers. For example, the binary number 101 can be rewritten in the following way.

101 = 1 × 2² + 0 × 2¹ + 1 × 2⁰

Note that in the right side of the above equation all numbers are in decimal. Therefore, the decimal value of the binary number 101 can be computed by evaluating the right side of the above equation.

101 = 1 × 2² + 0 × 2¹ + 1 × 2⁰
101 = 1 × 4 + 0 × 2 + 1 × 1
101 = 4 + 0 + 1
101 = 5

The above equation can be generalized to convert any positive integer in binary to decimal.

bit₀ × 2⁰ + bit₁ × 2¹ + . . . + bit_n − 1 × 2^n − 1

Note that the bits in a binary number are indexed from right to left from 0 to n − 1

Decimal to Binary

Converting a number from binary to decimal is the sum of a series of powers of two. Converting a number from decimal to binary can be accomplished by finding the unique powers of two that sum to the decimal number from largest to smallest. Another more algorithmic way of converting decimal numbers to binary is as follows.

The remainder of the decimal number divided by two is a bit in the binary number.
The decimal number is changed to the floor of half the decimal number.
If the decimal number is greater than 0, go back to step 1.
The bits generated in step 1 from right to left are the equivalent binary number.

For example, the decimal number 123 would be converted to binary using this algorithm as follows:

123 / 2 = 61 remainder 1
61 / 2 = 30 remainder 1
30 / 2 = 15 remainder 0
15 / 2 = 7 remainder 1
7 / 2 = 3 remainder 1
3 / 2 = 1 remainder 1
1 / 2 = 0 remainder 1

Therefore, the decimal number 123 is equal to the binary number 1111011. This can be verified by converting the binary number 1111011 to decimal.