Binary Representation of Natural Numbers

We are familiar with the decimal representation of natural numbers in terms of the one-digit numbers or simply digits 0, 1, 2, 3,…,8 and 9 with e g

  • 1492  = 1 x 1000 + 4 x 100 + 9 x 10 + 2,

where 10 = 9 + 1, 100 = 10 x 10 = 10^2, 1000 = 10 x 10 x 10 = 10^3 and x represents multiplication. Here 10 is referred to the base of the representation with the number of multiplicative factors of the base given by the exponent.

This is a positional representation where the position from right to left indicating the relevant power of 10 starting with 1 = 10^0, 10 = 10^1, 100 = 10^2 = 10 x 10, 1000 = 10^3 = 10 x 10 x 10, and so on.

We shall start with instead a positional binary representation in terms of the two digits 0 and 1 as follows, with corresponding decimal number in parenthesis:

  • 10 = 1 + 1                     (2)
  • 11  = 10 + 1                  (3)
  • 100 = 11 + 1                 (4)
  • 101 = 100 + 1               (5)
  • 110 = 100 + 10             (6)
  • 111 = 100 + 10 + 1        (7)
  • 1000 = 111 + 1              (8)

where 1 = (1) is called a one-bit, 10 = (2) is called a two-bit, 100 = (2 x 2 = 2^2 = 4) is called  four-bit , 1000 = (2 x 2 x2 = 2^3 = 8) is called an eight-bit, and so on. Compare binary and decimal representation and

DigiMat introduces binary representation before decimal representation because it is easier for a fresh preschool mind to understand and use, as  illustrated by the pedagogical app Ada’s World.

With binary representation already a three year old child can understand and use and enjoy basic operations with natural numbers. When binary representation is understood and internalised, it is a quick easy step to extend to e g decimal representation. In addition, the computer uses a binary representation because it is easier to compute with. Binary representation is an expression of the close connection between mathematics and computer in DigiMat.

Every natural number can be uniquely represented as a sum of such binary bits at most one of each kind with the position telling which type of bit it is. To meet the principle of a most one of each bit we use the following scheme

  • 2 one-bits make (is replaced by) 1 two-bit
  • 2 two-bits make 1 four-bit
  • 2 four-bits make 1 eight-bit
  • and so on

As soon as we meet 2 bits of the same kind we replace by 1 of the next kind, for example 2 four-bits are replaced by 1 eight-bit as indicated. In this way we can uniquely represent natural numbers using only two digits 0 and 1.

Compare with  Counting.

To understand this representation principle, which is analogous to the positional decimal system with the base 2 instead of 10, run this program illustrating the principle that two of one kind (e g green) is to be replaced by one of the next kind (yellow).

We know that the computer works with binary numbers with only the two digits 0 and 1, because of its construction with electrical circuits being on = 1 or off = 0. An advantage is that computation with binary numbers is much simpler than with decimal numbers. Addition is thus specified by the very short table:

  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 10

expressing the principle that addition of two of one kind makes one of next kind, while adding 0 does not change anything.

We can construct the natural numbers in binary form using a horisontal abacus with just one bean,  which can have two positions up and down as shown in this one-bead binary abacus.

Recall the the common vertical abacus used in pre-school has several rows of 9 beads with each row representing a power of 10. You start with all beads shifted to the left and count 1, 2, 3, …, by shifting beads from left to right on row one and when there are no more beads to the left (after 9 shifts), shift all beads on row one back to the left and shift one bead to the right on the second row, and so on.

The next step is to inspect the above p5js codes to see how they are constructed. We will then need the programming tool of a do-loop allowing us to express repetition of the task of always replacing 2 bits of one kind with 1 bit of the next kind.

We will then number the bits by bit[1] = one-bit, bit[2] = two-bit, bit[3] = four-bit, bit[4] = eight-bit, using decimal numbers, and the representation principle can be expressed as

  • for n = 1, 2, 3, … do:
  • if bit[n] = 2 then bit[n+1] = 1 and bit[n] = 0.

The natural numbers can now be constructed in binary form by repeating

  • bit[1] = bit[1] + 1

followed by the above successive carry of bits.

Extension of the set of natural numbers as positive integers to the negative integers -1, -2, -3, et cet, is done with the operation -1 as the inverse of +1 with n -1 = m defined so that m + 1 = n, giving the set of integers as 0, \pm 1, \pm 2, \pm 3,....

We are now ready to inspect the codes constructing the natural numbers with display on the screen. The numbering of the bits and the do-loop are then for simplicity expressed using decimal numbers, which of course can be replaced by binary numbers once created.

We now turn the elementary operations of addition, subtraction, multiplication and division of natural numbers (extended to integers by the basic operation of -1), which in binary form take simple algorithmic form.

The objective is now to write codes for the elementary operations on numbers, which can serve as pocket calculator but not black box, for you to use because you have constructed it yourself.