What is the weight of a position in the number system. What is a number system? What number systems are used by experts to communicate with a computer
Acquaintance with Leaf
The inventor Listik invented a device for transmitting numbers. His device transmitted messages in the form of a chain of short and long signals. In his notes, Listik denoted a short signal with the number “0”, and a long one with the number “1”. When transmitting numbers, he used the following code for each digit:
The number 12, consisting of the numbers 1 and 2, Leaflet wrote down for transmission as follows:
The device transmitted this message in a chain of such signals: three short, one long, two short, one long and one short.
The number 77 according to Listik's system was coded as follows:
Information coding
Encoding is the translation of information into a form that is convenient for transmission or storage.
For example, texts are encoded using letters and punctuation marks. Moreover, one and the same record can be encoded in different ways: in Russian, in English, in Chinese ...
Numbers are encoded using numbers. The numbers we are used to are called Arabic numbers. Roman numerals are sometimes used. In this case, the method of encoding information changes. For example, 12 and XII are different ways of writing the same number.
Music can be encoded using special characters - notes. Road signs are coded messages to drivers and pedestrians using pictograms.
Products in the store are marked with a barcode that contains information about the product and its manufacturer.
A barcode is a sequence of black and white stripes that encodes information in a form that is easy to read by technical devices. In addition, a code in the form of a series of numbers can be placed under the barcode.
Information is always stored and transmitted in the form of codes. You can't just store information, without a carrier. In the same way, it is impossible to store and transmit just information: it always has some form, that is, it is encoded.
Binary encoding
Binary coding is the encoding of information using zeros and ones. This way of presenting information has proven to be very convenient for computer technologies.
The point is that computers are built on elements that can be in two possible states. One such state is designated by the number 0, the other by the number 1.
An example of a binary device is an ordinary light bulb. It can be in one of two states: on (state 1) or off (state 0).
You can build electrical memory on light bulbs and store in it, for example, numbers using Leaf's binary code.
Four bulbs are required to store each decimal digit. This is how you can remember the number 6:
Set the switches to the desired position - and let's go have tea! If the electricity is not turned off, the information will be saved.
Light bulbs, of course, are not suitable for the production of computers: they are large, burn out quickly, are expensive (after all, there are millions of them) and they heat the environment very much.
In modern computers, an electronic device, a transistor, is used as a memory element.
The transistor can pass current through itself (state 1) or not (state 0).
There was a time when each transistor was manufactured separately and was significant in size.
Now transistors, like other electronic elements, are made in a manner similar to photo printing. One microcircuit the size of a fingernail, several million transistors can be “imprinted”.
The code that Listik used to encode messages is actually used to work with numbers in a computer.
With binary coding, you don't have to look at this table at all, but remember the simple rule for translating a binary code into a decimal digit.
The one in the code in the first place on the right gives the number
lo 1, on the second - 2, on the third - 4, on the fourth - 8. To obtain a decimal digit, the numbers are added. For example, the code “0101” is translated into digit 5 (the sum of the numbers 4 and 1).
The same rule can be used for decoding as well. For example, digit 6 is written as the sum of numbers 4 and 2, which means that its code will be “0110”.
A tablet with numbers written in the numeral system that was used in Ancient Babylon. Around 1700 BC Deciphered in 1945.
Number systems
Leaf code and coding of numbers
The previous lesson showed you how to write numbers using zeros and ones. Leaflet encodes every digit number four binary signs.
So, the number 102 by the Leaf code is written using 12 binary characters:
Leaflet encodes separately each of 10 digits and uses 4 binary digits for this. But four binary characters can encode not 10, but 16 values:
It turns out that 6 Leaf codes (which is more than half of 10) are wasted!
Is it possible to code more economically?
You can if you encode not numbers(of which the number is collected), and immediately the numbers! So, the number 102, with this encoding method, can be written not in twelve, but only in seven binary digits (we save 5 digits):
This coding will be covered in this tutorial. But let's start in order.
Decimal number system
As you know, numbers are built from numbers, and there are only ten numbers, here they are:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
How can large numbers be written with only ten digits? We will see this now, but first, let's remember the definition:
The way of writing numbers is called number system.
Scholarly word dead reckoning, consonant with the word "calculation" already means "a way of writing numbers". But it seemed to mathematicians that the phrase notation sounds better. Never mind, we'll master this two-word term! Now let's deal with that number system, to which they are accustomed.
Look at the number 253. In this entry, the first digit on the right (it is called least significant digit) means “three ones”, five means “five tens”, and two ( highest digit) - "two hundred".
It turns out: 253 = 2 · 100 + 5 · 10 + 3 · 1.
We are talking: "Two hundred fifty three"... This means the number that is obtained by adding:
two hundred (2 100 = two hundred),
five dozen (5 10 = fifty) and
three units (3 1 = three).
We see that the value of the digit in the number recording depends on positions in which the digit is located. Digit positions are called differently discharges numbers.
The least significant digit means units:
The second digit from the right means tens:
The third digit from the right means hundreds:
We see that the contribution of the digit to the number increases from right to left.
Number systems in which the contribution of a digit to a number depends on positions the numbers in the entry are called positional number systems.
The number system familiar to us is positional, as we have seen. Note that in basis it is supposed to be number 10 - the number of digits used.
The lowest digit shows the number of units in the number, the second from the right - the number of tens (1 · 10). The third shows hundreds (10 10), the fourth shows thousands (10 100) and so on.
We count as units, units add up to tens (ten units are replaced by one ten), tens - into hundreds (ten tens are replaced by one hundred), and so on.
The number 10 is the basis of the usual number system, therefore it is called decimal system, or by the number system basis 10.
Look again at how 2789 translates to a number.
The number is obtained by adding deposits numbers included in it:
The contribution of each digit is obtained by multiplying that digit by a position dependent multiplier associated with the radix of the system.
Position multipliers are calculated according to the following rule:
1. The multiplier of the first (right) position is 1 .
2. The multiplier of each next position is obtained by multiplying the base of the system (the number 10 ) by a factor of the previous position.
The position multipliers will be called weights of positions, or positional weights.
The number is equal to the sum of the deposits. The contribution is equal to the product of the figure and the positional weight. The weight of the first position is 1, the second is 10, the third is 100, and so on. That is, the weight of each position (except the first) is obtained from the weight of the previous one by multiplying by the base of the system. The weight of the first position is equal to one.
Here's how: they multiplied, added and did not suspect! It turns out that we write numbers in base ten positional notation! Why is the base of our system equal to 10? Well, this is understandable: after all, we have 10 fingers, it is convenient to count by bending them in order.
But for a computer, as you already know, the binary system is more familiar, that is positional base two.
Binary number system
There are only two digits in the binary system:
If in the decimal system the position weights are obtained by multiplying by ten, then in the binary system - by multiplying by two:
It turns out: 1011 2 = 1 2 · 4 + 0· 2 · 2 + 1 2 · 1 + 1 1 .
In the binary system, they are considered to be ones, ones are added to twos (two ones are replaced by one two), twos are added to fours (two twos are replaced by one four), and so on.
When it is necessary to clarify in which system a number is written, the base of the system is attributed to it from below:
1011 2 - the number is written in the binary system.
It is not difficult to convert it to the decimal system, you just need to perform the operations of multiplication and addition:
1011 2 = 1 2 · 4 + 0· 2 · 2 + 1 2 · 1 + 1 1 =
1 8 + 0 4 + 1 2 + 1 1 = 11 10.
Binary to Decimal Conversion
In the binary system, the contribution of one in the first place on the right is the number 1, in the second - 2, in the third - 4, in the fourth - 8, and so on. Contributions of zeros, of course, are equal to zero regardless of their positions.
We get the following rule:
To convert from binary to decimal, you need to write the weight of its position above each binary digit and add the numbers written above the units.
10111 2 = 16 + 4 + 2 + 1 = 23 10 .
Another example, the number 100110:
100110 2 = 32 + 4 + 2 = 38 10 .
Decimal to Binary Conversion
To convert from decimal to binary, we will use the previous scheme with position weights:
Suppose you need to translate the number 26 into the binary system. We select the beginning of the binary number (the most significant digit) according to the scheme. 32 is a lot, so we start with 16:
Part of the original number, namely 16, is encoded, it remains to encode 26 - 16 = 10. Take 8 (the largest possible positional weight):
It remains to encode 10 - 8 = 2. Four is a lot. We write to position 0 and take 2:
We have encoded the entire number, which means that the last digit should be zero:
It turns out: 26 10 = 11010 2.
The rule for converting from decimal to binary can be formulated as follows.
To better understand this algorithm, work on the Tester's bench. Click the button Reset, dial a number. Then press the button Start: you will see how the Tester performs the binary conversion algorithm step by step.
Please note: in the algorithm record, the item that will be executed is highlighted. after pressing the button Start... For example, if the item is highlighted “Repeat until the number turns to zero”, then after clicking on Start The tester will check the current number for equality to zero and decide whether to continue repeating.
(Perform work with the Tester on the page of the electronic application.)
Positional systems with other bases
Vasya loves the decimal system, his computer is binary, and curious mathematicians love different positional number systems, because you can take any number as a base, not just 2 or 10.
Let's take a ternary number system as an example.
Ternary number system
The ternary number system uses, as you might guess, three numbers:
In the ternary system, they are considered to be units, ones are added to threes (three ones are replaced by one three), threes - to nines (three threes are replaced by one nine), and so on.
Interestingly, in 1958, under the leadership of N.P. Brusentsov, the Setun computer was created at Moscow State University, and it worked with numbers not in binary, but in ternary number system! The first prototype "Setun" is shown in the photo:
Converting from ternary to decimal
Let us denote in the diagram the positional contributions of digits in the ternary number system:
To convert to the decimal system, add the digits multiplied by their positional weights (positions with zero digits, of course, can be omitted):
10212 3 = 1 81 + 2 9 + 1 3 + 2 1 = 104 10 .
In the binary system, we dispensed with multiplication (there is no point in multiplying by 1). There is a number 2 in the ternary system, so you have to double the corresponding positional weights.
Decimal to ternary conversion
Let the number 196 need to be translated into the ternary system. We select the beginning of the ternary number according to the scheme. 243 is a lot, so we start with 81 and the number 2 (2 81< 196):
Part of the original number, namely 162 = 2 · 81, is encoded, it remains to encode 196 - 162 = 34. Take 27 and the number 1 (number 2 gives 54, which is too much):
It remains to encode 34 - 1 · 27 = 7. Position with weight 9 gives too much, write 0 in it and take position with weight 3 and number 2:
It remains to encode 7 - 2 · 3 = 1. This is exactly the value of the remaining least significant digit:
It turns out: 196 10 = 21021 3.
Positional systems: basic rules
Let us formulate the general rules for constructing numbers in positional number systems.
The number is written in numbers, for example:
To determine the value of a number, you need to multiply the numbers by the weights of their positions and add the results.
Positions are numbered from right to left. The weight of the first position is 1.
The weight of each next position is obtained from the weight of the previous one by multiplying by the base of the system.
It turns out that the weight of the second position is always equal to the base of the system.
The base of the system shows the number of digits that are used in the given system. So, in a base 10 system, ten digits, in a base 5 system, five digits.
Let's look at an example. If the entry
means a number in the base 5 system, then it is equal to
3242 5 = 3 125 + 2 25 + 4 5 + 2 1 = 447 10 .
The same entry in the base 6 system means the number
3242 6 = 3 216 + 2 36 + 4 6 + 2 1 = 746 10 .
Non-positional number systems
Positional number systems did not appear immediately, primitive people designated the number of some objects as equal to the number of others (they were considered pebbles, sticks, bones).
More convenient methods of counting were also used: notches on a stick, dashes on a stone, knots on a rope.
Sometimes modern people also use such a number system, noting, for example, the number of days that have passed by notches.
That's an example non-positional unit number system: used for counting alone number (stone, stick, bone, dash, knot ...), and the contribution of this figure does not depend on its place (position), it is always equal to one unit.
It is clear that it is much more convenient to use positional number systems.
Actions on numbers
Actions on numbers in the positional system with any base are performed in the same way as in the decimal system: they are based on the tables of addition and multiplication of the digits of the corresponding number systems.
It would be strange if in different systems you had to add, subtract, multiply and divide in different ways! Indeed, in all number systems, numbers are constructed in the same way, which means that actions on them must be performed in the same way.
Let's look at a few examples.
Addition
5 + 7 = 12. In the least significant bit we write 2, and add one to the next bit.
Let's build an octal addition table:
According to the addition table 5 + 7 = 14 8. We write 4 in the least significant digit, and add one to the next digit.
Subtraction
We occupy 1 in the second place and subtract 7 from the number 15. Similarly in the octal system:
We occupy 1 in the second digit and subtract 7 from the number 15 8. According to the addition table in line 7, we find the number 15. The number of the corresponding column gives the result of the difference - the number 6.
This is probably convenient for spiders to use
octal number system!
Multiplication
2 7 = 14. We write 4, and 1 goes to "mind" (add to the next category). 4 · 7 = 28. We write 9 (8 plus 1 from the "mind") and transfer 2 to the next category.
Let's build an octal multiplication table:
2 7 = 16 8. We write 6, and 1 goes to “mind” (add to the next category). 4 7 = 34 8. We write 5 (4 plus 1 from "mind") and 3 we carry over to the next digit.
Division
3 5< 17 < 4·5, поэтому первая цифра результата - 3. Из 17 вычитаем 5·3 = 15. К разности 2 приписываем цифру 5, получается 25. 25 = 5 ·5. Из 25 вычитаем 25=5·5, получается 0 - деление закончено.
In the multiplication table on line 5 we find the appropriate number 17 8 = 5 3:
This means that the first digit of the result is 3. From 17 8 we subtract 17 8 = 5 · 3. To the difference 0 we assign the last digit 5. 5 = 5 · 1. Subtract 5 from 5, it turns out 0 - the division is over.
Questions and Answers
1. Give a definition to the term "number system".
2. Give a definition to the term "positional number system".
3. Explain the principles of constructing numbers in decimal notation using the example of the number 548.
4. What is called the weight of a position? Tell us the algorithm for finding the weight of a position. What is the weight of the third position from the right in the decimal notation of the number? And in binary? And in the ternary?
5. What is meant by a discharge? What place is the number 5 in the decimal number 1532?
6. What is called the contribution of numbers? What is the contribution of the number 7 to the number 1745 10? And the contribution of the number 4 to the number 1432 5?
7. Give a definition to the term “base of the positional number system”. How is the base of a system related to the number of digits in this system? How many digits are there in 5-ary number system? And in hexadecimal? What about a base 25 system?
8. Where is the least significant digit in the number record? And the eldest?
9. Tell us the algorithm for converting a binary number to the decimal number system and perform this algorithm for the number 101101 2.
10. Tell the algorithm for converting a decimal number to a binary number system and perform this algorithm for the number 50 10.
11. How to convert a number from any positional number system to the decimal system? Explanation is based on the example of a system with a base 4.
Hometasks
Option 1. Performed without a computer, "on paper"
1. Read tongue twisters, replacing binary numbers with decimal:
Ate well done
100001 2 pies with pie,
Yes, all with cottage cheese.
There were 101000 2 mice,
Carried 101000 2 grosz,
A 10 2 mice are smaller
They carried 10 2 grosz each.
2. Solve the binary-letter puzzles:
3. Perform the calculations and write down the answer in decimal notation:
1) 100 2 5 8 =
2) 100 3 + 100 5 =
3) 10 9 10 100 - 10 900 =
4) 33 4 + 44 5 =
5) 15 6 + 51 8 =
4. Translate the given numbers into the indicated number systems:
Option 2. Performed on a computer
1. Write down the arithmetic expression for solving the following problem and calculate the answer:
Our clever Malvina
Takes care of Buratino
And I bought it for him
What he needs most of all:
10 2 covers, 11 2 rulers
And for 111 2 rubles stickers.
On the covers - Barmaley,
The price of each is 101 2 rubles.
On the rulers that I bought
101010 2 rubles was enough.
How much did the purchases cost?
On reflection - half a minute.
2. Try to use the standard Calculator program to convert numbers from a poem into the usual decimal notation ( View- Engineering, Bin- binary representation of a number, Dec- decimal representation of the number). Write down algorithms for converting numbers using the Calculator from binary to decimal and vice versa, from decimal to binary.
Option 3. For the curious
1. Prove that writing 10 in any positional number system means a number equal to the base of this system.
2. Determine the base of the positional number system b for each equality:
1) 10 b = 50 10 ;
2) 11 b = 6 10 ;
3) 100 b = 64 10 ;
4) 101 b = 26 10 ;
5) 50 b = 30 10 ;
6) 99 b = 909 10 ;
7) 21 b = 15 6 ;
8) 10 2 b = 100 b ;
9) 12 2 b = 22 b ;
10) 14 b· b = 104 b .
p ALIGN = "JUSTIFY"> 3. The hexadecimal number system uses 16 digits. The first ten digits coincide with the digits of the decimal system, and the last are denoted by letters of the Latin alphabet:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.
Value |
|
Let's translate, for example, the number A8 16 into the decimal system:
A8 16 = 10 16 + 8 1 = 168 10 .
In each task, find the value of the number x:
1) 25 16 = x 10 ; 4) 170 10 = x 16 ;
2) AB 16 = x 10 ; 5) 2569 10 = x 16 ;
3) FD 16 = x 10 ; 6) 80 32 = x 16 .
4. Complete the following tasks.
1) Find the weight of the third position in the number record if you know that the weight of the second position is 7. Numbering of positions from right to left.
2) The number system uses 5 digits. Find the weight of the fourth position from the right in the number notation.
3) The number is written in the form of two units: 11. In what number system is it written if in decimal it is equal to 21?
4) In a certain number system, the number looks like 100. How many digits does this number system use if in the decimal system the number is 2500?
5) Two numbers are written as 100, but in systems with different radix. It is known that the base of the first system is twice the base of the second. Which number is greater and how many times?
6) Find the base of the system, if it is known that the number 101, written in this system, means the decimal number 37.
7) In which number system, to double a number, do you need to add zero to the right of its entry?
8) Multiplying by 10 in the decimal system means adding zero to the right to the number. Formulate the rule of multiplication by 10 b in a system with a base b.
5. Formulate an algorithm for converting a number from decimal to ternary number system.
6. Build tables of addition and multiplication for the fourfold number system. Using these tables, perform the following actions on the numbers in a column (while remaining in the quaternary number system):
1.a) 1021 4 + 333 4;
b) 3333 4 + 3210 4;
2.a) 321 4 - 123 4;
b) 1000 4 - 323 4;
3. a) 13 4 · 12 4;
b) 302 4 23 4;
4.a) 1123 4:13 4;
b) 112003 4: 101 4.
7. Build tables of addition and multiplication for the binary number system. Using these tables, perform the following steps on the numbers in a column (remaining in the binary number system):
1.a) 1001 2 + 1010 2;
b) 10111 2 + 1110 2;
2. a) 1110 2 - 101 2;
b) 10000 2 - 111 2;
3. a) 101 2 · 11 2;
b) 1110 2 · 101 2;
4.a) 1000 110 2: 101 2;
b) 100000100 2: 1101 2.
Workshop
On the pages of the electronic application, work with the performer Encoder.
Exercises contain the following groups of tasks:
Decimal
1. From binary to decimal
2. From ternary to decimal
3. From five to decimal
4. From hexadecimal to decimal
From decimal
1. Decimal to Binary
2. From decimal to ternary
3. From decimal to five
4. Decimal to Hexadecimal
Crediting class 1
2. 1101 2 = ? 10
3. 11101 2 = ? 10
Crediting class 2
10. 1001 2 = ? 16
Teacher material
Positional number systems
In the positional number system, a number is written as a chain of special characters:
a n a n – 1 ... a 2 a 1 (1)
Symbols a i are called figures... They denote ordinal countable quantities, starting from zero and up to the value of one less number. q called basis number system. That is, if q- base, then the values of the digits lie in the interval (including boundaries).
The position of the digit in the record of the number (1) is called it position, or discharge.
Note 1. On these pages, the term “position” is preferred. First, the word “position” is in good agreement with the concept of “positional number system”, and secondly, the term “positional weight” or “position weight” sounds better, clearer and simpler than “bit weight” or “bit weight”. However, the teacher can and should remind students from time to time that “position” and “rank” are equivalent terms.
Remark 2. The definition of the positional number system given in the texts for the student is not entirely accurate. The dependence of the contribution of the figure on the position alone is not enough. For example, in the Roman numeral system, the contribution of the digit also depends on the position (the numbers IV and VI are different), but this system is not positional. An exact definition can be considered the entire set of rules for constructing a number, given in this context for a teacher (that is, along with the fact of positional dependence, the definition includes: the finiteness of the set of digits and the rule for finding a number by its recording).
Positions are numbered from right to left. The number in the first position is called the younger digit of a number, in the last - senior.
Each position is associated with a number, which we will call its weight ( weighting position).
Position weights are determined according to the following recursive rule:
1. The weight of the lowest position is 1.
2. The weight of each next position is obtained from the weight of the previous one by multiplying by the base of the system.
Let be q- the base of the number system. Then the rule for calculating positional weights w i can be written more concisely as a recurrent formula:
1. w 1 = 1.
2. w i = w i-one · q(for all i > 1).
In the positional numeral system, the record
a n a n – 1 ... a 2 a 1 (1)
means number N, equal to the sum of the products of digits by their positional weights:
N = a n· w n + a n-one · w n–1 + ... + a 2 w 2 + a one · w 1 . (2)
The product of a digit by its positional weight (i.e. a i· w i) will be called positional contribution of numbers.
Formula (2) is the basis for the rules for translating numbers from one system to another, proposed in the texts for the student.
In the decimal system, numbers are written using ten Arabic characters: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
The positional weights of this system are: ..., 1000, 100, 10, 1.
4627 10 = 4 1000 + 6 100 + 2 10 + 7 1.
In the binary system, numbers are written using two Arabic characters: 0 and 1. Positional weights of this system: ..., 256, 128, 64, 32, 16, 8, 4, 2, 1.
For example, the entry 10101 is “decrypted” like this:
10101 2 = 1 16 + 0 8 + 1 4 + 0 2 + 1 1.
Note that the recursive rule for calculating weights implies that w i = q i–1 and, therefore, notation (2) is equivalent to the traditional notation in the form of a power polynomial:
N = a n· q n–1 + a n-one · q n–2 + ... + a 2 q + a 1 . (3)
Let us prove this by induction. Induction base at i= 1 is checked directly: w 1 = q 0 = 1.
Induction hypothesis: let the statement be true for some n:
w n = q n–1 .
Let us prove that it will also be valid for n + 1.
That is, we will prove the validity of equality:
w n + 1 = q n.
Indeed, w n+1 = w n· q(according to the recursive definition of the position weight), and w n = q n–1 by induction hypothesis. It turns out:
w n + 1 = w n· q = q n-one · q = q n.
Let us prove that any number is representable in the form (1) (Theorem 1) in a unique way (Theorem 2).
Theorem 1 (existence). Any number m can be represented in the form (1) for any q > 1.
Evidence. Let us prove it by induction. For m = 0
and m= 1 it is easy to construct the required representation - these are, respectively, 0 and 1 (for any q> 1). Let's say we managed to represent the number m in the form (1). We then find a representation for m+ 1. For this, it is enough to convert the sum
a n q n–1 + a n-one · q n–2 + ... + a 2 q + a 1 + 1 to form (1).
If a a 1 < (q-1), then the desired representation is obtained by replacing the digit a 1 on a " 1 = a 1 + 1.
If a a 1 = (q–1), we get the transfer of the unit to the next position:
a n q n F – 1 + a n-one · q n–2 + ... + (a 2 + 1) q + 0.
Next, we reason in a similar way. If a a 2 < (q-1), then the desired representation is obtained by replacing the digit a 2 on a " 2 = a 2 + 1. If a 2 = (q–1), then a 2 is replaced by zero and one is transferred to the next position.
Or on some i < n we will finish the construction, or we will get a record 1000 ... 0 - one and n zeros to the right. The proof is complete.
Before Theorem 2, we prove the lemma.
Lemma. The contribution of each non-zero digit in record (1) exceeds the sum of contributions of the digits located to the right of it.
a n a n – 1 ... a 2 a 1 . (1)
Evidence. Let us prove that for any n > 1:
a n q n–1 > a n-one · q n–2 + ... + a 2 q+ a 1 .
Numbers a i lie in the interval, so it is enough to prove the inequality for the smallest nonzero digit on the left side and maximum digits on the right:
q n – 1> ( q-one)· q n–2 + ... + (q-one)· q + (q–1).
On the right side, we take out the factor ( q–1) outside the bracket:
(q-one)· q n–2 + ... + (q-one)· q + (q–1) =
= (q-one)·( q n–2 + ... + q + 1).
We calculate the sum of the geometric progression in the last bracket using the well-known formula:
(q-one)·( q n–2 + ... + q + 1) =
= (q-one)·( q n–1 –1)/(q–1) = q n–1 – 1.
We obtain an obvious inequality that proves the lemma:
q n – 1> q n–1 – 1.
Theorem 2 (uniqueness). The number in the form (1) is represented in the only way.
Evidence. It follows from the lemma that numbers with a different number of digits in their notation (non-significant zeros on the left are not counted) cannot be equal: a number with a large number of digits is always greater. Hence, it is only necessary to prove that if a i not equal b i for all i from 1 to n then records
a n a n – 1 ... a 2 a 1 (4)
b n b n – 1 ... b 2 b 1 (5)
cannot mean the same number.
Let's look through records (4) and (5) from left to right in search of mismatched digits. Let it be a k and b k let it go a k – b k = d.
On the k-th place in the record, there was a difference in d· q k-one . This difference should be compensated by the contributions of the positions located to the right. But this is impossible, since, according to the lemma, the sum of the contributions of the positions located to the right is always less than the contribution of the current position. The theorem is proved.
Conversion to decimal
To translate numbers from a radix system q in the decimal system, you can use the formula (2), performing multiplication and addition in it.
N = a n· w n + a n-one · w n–1 + ... + a 2 w 2 + a one · w 1 (2)
When translating from a binary system, only addition is involved (because you can not multiply by 1). Thus, we get the translation rule formulated in the Reading Room:
To convert from binary to decimal, you need to write the weight of its position above each binary digit and add the numbers written above the ones.
So, for example, for the number 10111 we get:
10111 2 = 16 + 4 + 2 + 1 = 23 10
General rule of transfer from q-ary system to decimal sounds like this:
To transfer from q-ary system in decimal, you need to write down the weight of its position above each digit and find the sum of the products of digits by their positional weights (that is, find the sum of positional contributions).
So, for example, for the number 10212 3 we get:
We add the numbers multiplied by their positional weights (positions with zero digits, of course, can be omitted):
10212 3 = 1 81 + 2 9 + 1 3 + 2 1 = 104 10 .
Translation into q- personal
To convert numbers from decimal to radix q we will continue to rely on formula (2):
N = a n· w n + a n-one · w n–1 + ... + a 2 w 2 + a one · w 1 . (2)
Algorithm of translation.
I. Repeat until the number turns to zero:
1. Find the first position on the left, the weight of which is not more than the current number. Write in the position the maximum possible digit, such that its positional contribution (the product of the digit by the weight) does not exceed the current number.
2. Decrease the current number by the contribution of the constructed position.
II. Write zeros in the positions not occupied by the constructed digits.
In each position, the maximum possible digit is taken, since, according to the lemma, the contribution of this digit cannot be compensated for by the digits located to the right. The algorithm will work due to the proven existence (Theorem 1) and uniqueness (Theorem 2) of the representation of a number in the form (1).
For a binary system, we get a variant of the algorithm given in the material for the student.
To convert to binary, you need to build a template with weights of binary digits:
The number is translated according to the following algorithm:
I. Repeat until the number turns to zero:
1. Write 1 in the first position on the left, the weight of which is not more than the current number.
2. Decrease the current number by the weight of the constructed unit.
II. Write zeros in the positions not occupied by ones.
In practice, this method of translation turns out to be much easier and faster than the traditional algorithm with finding residuals.
When converting from a decimal system to a ternary system, one has to take into account both the positional weights themselves and their doubling. For a quick translation, you can build a table, the lines of which correspond to the positions of the numbers, the columns - to the numbers, and the cells - to the contributions of the number to the number, depending on its position in the number record:
position 729 |
||
position 243 |
||
position 81 |
||
position 27 |
||
position 9 |
||
position 3 |
||
position 1 |
Let's say the contribution of the number 2 in position 243 is the number 486, and in position 9 is the number 18.
To translate into a ternary system, you need to scan the table line by line in search of the largest number that does not exceed the current value.
For example, let's translate the number 183 into ternary system. A suitable value is located in the third row and first column:
position 729 |
||
position 243 |
||
position 81 |
||
position 27 |
||
position 9 |
||
position 3 |
||
position 1 |
Hence, the ternary number begins with the digit 2:
183 10 = 202?? 3
For the number 21-18 = 3 there is an exact meaning in the table, the translation is finished:
183 10 = 20210 3 .
For systems with a large base, the corresponding tables will, of course, be more voluminous. As a final example, let's build a table for converting to a hexadecimal number system:
Let the number 4255 be converted to the hexadecimal system. We are looking for the first number in the table (from left to right, row by row, starting from the top), which turns out to be no more than the original number 4255:
We get the first digit 1 in position 4096:
It remains to encode 4255 - 4096 = 159.
We skip line 256 (the corresponding digit will be 0), and in line 16 we find the appropriate value 144:
We get the numbers in positions 256 and 16:
It remains to encode 159 - 144 = 15. It is clear that this is the value of the least significant digit:
It turns out: 4255 10 = 109F 16.
Actions on numbers
This section is presented in the material for the student schematically, for informational purposes.
A separate, large and rather interesting lesson can be devoted to the topic, but there is already a lot of material - it is difficult to grasp the immensity!
In a simple, introductory version, it is shown that actions on numbers in any number system are performed in the same way as in the decimal system. It is strange if it would be otherwise, because numbers in all positional systems are built according to the same rules, which means that actions on them must be performed in the same way.
The section is supported by homework assignments for option 3. These exercises can be recommended to curious schoolchildren as individual assignments.
Chapter 4. Arithmetic Foundations of Computers
4.1. What is a number system?
There are positional and non-positional number systems.
In non-positional number systems the weight of a digit (that is, the contribution that it makes to the value of the number) does not depend on her position in the notation of the number. So, in the Roman numeral system, in the number XXXII (thirty-two), the weight of the figure X in any position is just ten.
In positional number systems the weight of each digit changes depending on its position (position) in the sequence of digits representing the number. For example, in the number 757.7, the first seven means 7 hundred, the second - 7 units, and the third - 7 tenths of one.
The very same notation of the number 757.7 means an abbreviated notation of the expression
700 + 50 + 7 + 0,7 = 7 . 10 2 + 5 . 10 1 + 7 . 10 0 + 7 . 10 -1 = 757,7.
Any positional number system is characterized by its basis.
Any natural number can be taken as the base of the system - two, three, four, etc. Hence, countless positioning systems possible: binary, ternary, quaternary, etc. Writing numbers in each of the radix systems q means shorthand expression
a n-1 q n-1 + a n-2 q n-2 + ... + a 1 q 1 + a 0 q 0 + a -1 q -1 + ... + a -m q -m ,
Where a
i
- numeral numbers; n
and m
- the number of integer and fractional digits, respectively.
For example:
4.2. How are integers generated in positional number systems?
In each number system, numbers are ordered according to their meanings: 1 is greater than 0, 2 is greater than 1, etc.
To advance the number 1 means to replace it with 2, to advance the number 2 means to replace it with 3, etc. High Digit Promotion(for example, the numbers 9 in decimal) means replacing it with 0... In a binary system that uses only two digits, 0 and 1, advancing 0 means replacing it with 1, and advancing 1 means replacing it with 0.
Integers in any number system are generated using Account rules [44
]:
Applying this rule, let's write the first ten integers
in binary: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001;
in the ternary system: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100;
in the fivefold system: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14;
in octal: 0, 1, 2, 3, 4, 5, 6, 7, 10, 11.
4.3. What number systems do specialists use to communicate with a computer?
In addition to decimal, systems with a base that is an integer power of 2 are widely used, namely:
binary(numbers 0, 1 are used);
octal(numbers 0, 1, ..., 7 are used);
hexadecimal(for the first integers from zero to nine, the digits 0, 1, ..., 9 are used, and for the next integers from ten to fifteen, the characters A, B, C, D, E, F are used as digits).
It is useful to remember the entry in these number systems for the first two tens of integers:
Of all number systems especially simple and therefore interesting for technical implementation in computers binary number system.
4.4. Why do people use decimal and computers use binary?
People prefer the decimal system, probably because since ancient times they counted with their fingers, and people have ten fingers on their hands and feet. Not always and not everywhere people use the decimal number system. In China, for example, the five-fold number system was used for a long time.
And computers use a binary system because it has a number of advantages over other systems:
to implement it, you need technical devices with two steady states(there is a current - no current, magnetized - not magnetized, etc.), and not, for example, with ten, as in decimal;
presentation of information by means of only two states reliably and anti-jamming;
possibly Boolean Algebra Apparatus Application to perform logical transformations of information;
binary arithmetic is much simpler than decimal.
The disadvantage of the binary system is rapid increase in the number of digits required to write numbers.
4.5. Why do computers also use octal and hexadecimal number systems?
A binary system, convenient for computers, is inconvenient for humans because of its cumbersomeness and unusual recording.
Converting numbers from decimal to binary and vice versa is done by the machine. However, in order to use a computer professionally, you must learn to understand the word machine. For this, the octal and hexadecimal systems have been developed.
Numbers in these systems are read almost as easily as decimal ones, they require, respectively, three (octal) and four (hexadecimal) times fewer digits than in the binary system (after all, the numbers 8 and 16 are, respectively, the third and fourth powers of the number 2) ...
For example:
For example,
4.6. How to convert an integer from decimal system to any other positional number system?
Example: Let's convert the number 75 from decimal system to binary, octal and hexadecimal:
Answer: 75 10 = 1 001 011 2 = 113 8 = 4B 16.
4.7. How to translate the correct decimal number into any other positional number system?
To translate the correct decimal numberF to radixq necessaryF multiply byq , written in the same decimal system, then multiply the fractional part of the resulting product byq, and so on, until the fractional part of the next product becomes equal to zero, or the required accuracy of the number is achieved F inq -paired system. Representation of the fractional part of a numberF in the new number system, there will be a sequence of whole parts of the obtained works, written in the order of their receipt and depicted by one q -a number. If the required precision of the number conversionF isk decimal places, then the maximum absolute error is equal toq - (k + 1) / 2. |
Example. Let's convert the number 0.36 from decimal system to binary, octal and hexadecimal:
4.8. How to convert a number from binary (octal, hexadecimal) to decimal?
Converting a number to the decimal systemx
recorded inq
-ary numeral system (q
= 2, 8 or 16) in the formx
q
= (a
n
a
n-1
... a
0
, a
-1
a
-2
... a
-m
)
q
is reduced to calculating the value of the polynomial x 10 = a n q n + a n-1 q n-1 + ... + a 0 q 0 + a -1 q -1 + a -2 q -2 + ... + a -m q -m
|
Examples:
4.9. Summary table of translations of integers from one number system to another
Consider only those number systems that are used in computers - decimal, binary, octal and hexadecimal. For definiteness, we take an arbitrary decimal number, for example 46, and for it we perform all possible consecutive translations from one number system to another. The order of translations is determined in accordance with the figure:
This figure uses the following conventions:
the bases of the number systems are written in circles;
arrows indicate the direction of translation;
the number next to the arrow means the serial number of the corresponding example in the summary table 4.1.
For example: means a translation from binary to hexadecimal, which has a sequence number 6 in the table.
Pivot table of integer translationstwosections- the theory of statistics ... statistics, informatics as disciplines ... KR (electronic version editions). ".... EP Microeconomic statistics: Textbook. allowance... - M .: Delo, 2000. ... magazine. the Internet- Rosstat websites ...
& quot the formation of open databases of information resources &
ReportReference editions. Bibliographic benefits. Section 1. Reference publications ... of conciliation procedures. the Internet-version journal provides access ... URSS / the Internet-score consistsoftwo departments: ... specialists of the Office informatics and telecommunications ...
Notation is a method of writing a number using a specified set of special characters (numbers).
Notation:
- gives a representation of a set of numbers (integers and / or real);
- gives each number a unique representation (or at least a standard representation);
- displays the algebraic and arithmetic structure of a number.
Writing a number in a certain number system is called number code.
A separate position in the display of a number is called discharge, which means that the position number is rank number.
The number of bits in the number is called bitness and matches its length.
Number systems are divided into positional and non-positional. Positional number systems are divided
on the homogeneous and mixed.
octal number system, hexadecimal number system and other number systems.
Translation of number systems. Numbers can be translated from one number system to another.
Correspondence table of numbers in various number systems.
There are positional and non-positional number systems.
In non-positional number systems the weight of a digit (that is, the contribution that it makes to the value of the number) does not depend on her position in the notation of the number. So, in the Roman numeral system in the number XXXII (thirty two), the weight of the figure X in any position is just ten.
In positional number systems the weight of each digit changes depending on its position (position) in the sequence of digits representing the number. For example, in the number 757.7, the first seven means 7 hundred, the second - 7 units, and the third - 7 tenths of one.
The very same writing of the number 757.7 means an abbreviated notation of the expression
700 + 50 + 7 + 0,7 = 7 . 10 2 + 5 . 10 1 + 7 . 10 0 + 7 . 10 -1 = 757,7.
Any positional number system is characterized by its basis.
Any natural number can be taken as the base of the system - two, three, four, etc. Hence, countless positioning systems possible: binary, ternary, quaternary, etc. Writing numbers in each of the radix systems q means shorthand expression
a n-1 q n-1 + a n-2 q n-2 + ... + a 1 q 1 + a 0 q 0 + a -1 q -1 + ... + a -m q -m ,
Where a i - numeral numbers; n and m - the number of integer and fractional digits, respectively. For example:
What number systems do specialists use to communicate with a computer?
In addition to decimal, systems with a base that is an integer power of 2 are widely used, namely:
binary(numbers 0, 1 are used);
octal(numbers 0, 1, ..., 7 are used);
hexadecimal(for the first integers from zero to nine, the digits 0, 1, ..., 9 are used, and for the next integers from ten to fifteen, the characters A, B, C, D, E, F are used as digits).
It is useful to remember the entry in these number systems for the first two tens of integers:
|
|
|
Of all number systems especially simple and therefore interesting for technical implementation in computers binary number system.
