0:02

Let us recall what is the decimal system.

So we would like to represent numbers by sequences of digits.

Consider, for example, the following sequence of digits three,

nine, two, and six.

It represents the number 3,926 in our decimal system.

So, but what is this number?

Note that this number can be written using arithmetic operations.

It can be written as an arithmetic expression.

So it is equal to 3,000 plus 900 plus 20 plus six.

And now, we can even modify it even more.

We can say that it is three times 10 to the power of three plus nine times

10 squared plus two times 10 plus six times 10 to the power zero,

10 to the power zero is just one.

Okay. So this is a way to express our number in arithmetic expression,

and note that this is a general trick.

It can be applied to any number.

And in the general case,

digits will be multiplied by powers of 10.

So we have a sequence of powers of 10 and we multiply digits by 10,

and we get the results and this is our number.

This is the computation of our number.

Okay. So, note that

each non-negative integer has a unique representation in our decimal system.

Okay.

So now, you can also consider a binary system.

And then here is that you can do just exactly the same,

but instead of powers of 10,

we will use powers of two.

And then this is called the binary system.

And then we only have two digits, two bits,

zero and one instead of 10 digits in decimal system.

And here's an example of a binary representation, one, zero, one, one, zero, one.

And let's see which number it corresponds to.

There is we just write down,

we multiply digits by powers of two and we add this up.

So we have multiplied the last digit by two to the zero which is just one.

The digit which is second from the end is multiplied by two

to the one then the previous digit is multiplied by two to the power of two.

And then the previous digit by two to the three and so on.

Some of the powers of two are multiplied by zero here.

So overall, we have here two to the five plus two

to the three plus two to the two and plus two to the zero,

which is 32 + 8 + 4 + 1 and we can compute it.

This is just 45. So we have expressed

number 45 in binary system, in binary representation.

And, why do we even care?

So why do we talk about binary system?

Binary system is important for one simple reason,

computers use the system.

So computers store information in binary system.

So binary system is important.

Okay. We can make the following observation with binary system with division by two.

Suppose we divide a by two with a remainder.

Then the remainder is just the last bit of a binary representation of a,

and the quotient is the number which is formed

by all bits of the binary representation of a except the last bit.

Recall that we had very similar statement for decimal system and division by 10,

the remainder, if we try to divide a by

10 then the remainder is the last digit in decimal system.

And here we have a very similar statement

but for division by two in binary representation.

And actually the proof is basically the same.

So for simplicity, just consider some specific number.

For example, consider the number 11101 in binary representation.

Okay. So let's write down this number which is one times two to

the four plus one times two to the three plus one times two to the two, and so on.

So, if we look at the sums,

note that all sums except the last one are divisible by two.

So, we can move two out of the brackets and so we

have two the three plus two to the two plus two to the one times two plus one.

And so, this is the expression for division of our number,

the remainder division by two and one now is the remainder.

And the expression in the brackets is the quotient.

And note that what happened with the quotient just all powers of two reduced by

one and we removed the last sum from our original sum.

So the quotient expressed as the number is

the same binary representation as original number but we just removed the last bit.

So we have this lemma.

And so, the remainder is one and the quotient is 1110.

And, of course this proof applies

to any number we just consider some specific number for simplicity.

Okay.

Now, let's make the following observation.

We do not prove here the correctness of binary system.

And what we are talking about,

so we can ask the following question: Why the system works?

Why every integer can be represented here?

Why the representation is unique?

So, why actually the system give us unique representation for any number?

So, we omit the proof of this statement.

However, note that the proof is not hard.

And for example, it is possible to prove it,

it is not hard to prove it using our previous Lemma,

with combination, with induction.

So note that our previous lemma

reduces the question of binary representation of a reduces

the construction of binary representation of a to

the construction of binary representation of smaller number over quotient of a,

when we divide it by two.

So, and note that this is also a way to

construct a binary representation of a given number.

We can apply the previous lemma and recursion.

So, it is not hard to prove that binary system works.

It has unique representation for any number,

what we will just need is proof.

Okay. Now, let's consider one more question related to the binary system.

Suppose we have some number a, how many bits are needed to represent this number?

Okay. Let's start with some simple cases.

Consider number which is two to the n. And note that we need exactly n plus one bits.

Two to the four, for example,

is one followed by four zeros.

This is exactly the expression for two to the four in binary representation.

So, numbers of the form two to the n

has simple binary representation one followed by n zeros.

And note on the other hand,

that two to the n is the smallest number that requires n plus one bits.

For example, consider two to the four minus one.

Then it is not hard to see that it is equal to

the three plus to the two plus two to the one plus one.

This number has a binary representation 1111.

So, just four ones.

So, two to the n is the smallest number that requires n plus one,

four to the minus one it is already enough to have n bits in binary representation.

So we can extend now this to arbitrary number a.

The number of bits that is needed to represent

a in binary representation is determined by the largest n,

such that two to the n is at most a.

So, note that if we increase number a then two to the n is

the smallest number for which we require n plus one bits in the representation.

So, if a is between two to the n and

may be equal to two to the n but is strictly less than two to the n plus one,

then it requires exactly n plus one bits in the representation.

And note that this is connected to the notion of logarithm.

Let's recall what is logarithm?

Consider some real number x.

So here, we're not dealing with integers.

Here, x can be arbitrary real number, but this should be positive,

then by logarithm of x we denote the number y,

which is also real such that two to the power of y is equal to x.

That's just the definition of logarithm. And note that logarithm,

what is the meaning of logarithm?

Logarithm is the inverse function to exponentiation.

So, if we apply exponentiation to some number,

if we consider some number y and consider

the number two to the power of y then logarithm is the inverse function.

A logarithm base two of two to the power y is equal to y.

Okay.

In particular, logarithm base two of two to the n is equal to n. So,

now we can connect the notion of logarithm to binary representations of integer numbers.

And here is the statement, the number of bits that is needed to represent some integer a

is equal to the integer part of logarithm base two of a plus one.

And here by integer part of x,

we denote the largest integer which is less or

equal than our possibly non-integer number x.

So we apply this operation to

some real number x and obtain an integer number which is less or equal than our x.

So, why this lemma is true?

It is not hard to see now and

just recall that the number of bits in binary representation of

a is equal to n plus one where n is

the largest number such that two to the n is at most equal to a.

Now, let's apply logarithm to both sides of the last inequality and then we will see

that n here is the largest number such that n is at most logarithm of a.

So n is exactly integer part of a.

So we obtain our lemma to represent number a in binary representation,

we need n plus one bits where n is integer part of logarithm base two of a.