Menu
For free
Registration
home  /  Self-development/ Binary arithmetic. Binary arithmetic Rules for arithmetic operations in the binary number system

Binary arithmetic. Binary arithmetic Rules for arithmetic operations in the binary number system

Arithmetic operations in positional number systems

Let's take a closer look at arithmetic operations in the binary number system. Binary number system arithmetic is based on the use of tables for adding, subtracting and multiplying digits. Arithmetic operands are located in the top row and first column of the tables, and the results are at the intersection of columns and rows:

Let's look at each operation in detail.

Addition. The binary addition table is extremely simple. Only in one case when addition is performed 1+1, there is a transfer to the most significant digit. ,

Subtraction. When performing a subtraction operation, the smaller number is always subtracted from the larger number in absolute value and the corresponding sign is placed. In the subtraction table, a 1 with a bar means a loan in the highest rank.

Multiplication. The multiplication operation is performed using a multiplication table according to the usual scheme used in the decimal number system with sequential multiplication of the multiplicand by the next digit of the multiplier.

Division. The division operation is performed using an algorithm similar to the algorithm for performing the division operation in the decimal number system.

Example 1. Find X if To transform the left side of the equality, we successively use De Morgan’s law for logical addition and the law of double negation: According to the distributive law for logical addition: According to the law of exclusion of the third and the law of exclusion of constants: We equate the resulting left side to the right: X = B We finally get: X = B. Example 2. Simplify the logical expression Check the correctness of the simplification using the truth tables for the original and resulting logical expression. According to the law of general inversion for logical addition (de Morgan’s first law) and the law of double negation: According to the distributive law for logical addition: According to the law of contradiction: According to the law of idempotency We substitute the values ​​and, using the commutative law and grouping the terms, we get : According to the law of exclusion (gluing) Substitute the values ​​and get: According to the law of exclusion of constants for logical addition and the law of idempotency: Substitute the values ​​and get: According to the distributive law for logical multiplication: According to the law of exclusion of the third: Substitute the values ​​and finally get: 2 Logical foundations of a computer A discrete converter, which, after processing the input binary signals, produces an output signal that is the value of one of the logical operations, is called a logical element. Below are symbols (circuits) of basic logical elements that implement logical multiplication (conjunctor), logical addition (disjunctor) and negation (inverter). Rice. 3.1. Conjunctor, disjunctor and inverter Computer devices (adders in the processor, memory cells in RAM, etc.) are built on the basis of basic logical elements. Example 3. For a given logical function F(A, B) = =B&АÚB&A, construct a logical circuit. The construction must begin with a logical operation, which must be performed last. In this case, such an operation is logical addition, therefore, there must be a disjunctor at the output of the logical circuit. Signals are supplied to it from two connectors, which in turn are supplied with one normal and one inverted input signal (from inverters). Example 4. A logic circuit has two inputs X and Y. Determine the logical functions F1(X,Y) and F2(X,Y), which are implemented at its two outputs. The function F1(X,Y) is implemented at the output of the first conjunctor, that is, F1(X,Y) = X&Y. At the same time, the signal from the connector is fed to the input of the inverter, at the output of which the X&Y signal is realized, which, in turn, is fed to one of the inputs of the second connector. The signal Xv Y from the disjunctor is supplied to the other input of the second conjunctor, therefore, the function F2(X,Y) = X&Y&,(XvY). Let's consider a scheme for adding two n-bit binary numbers. When adding the digits of the i-ro digit, ai and bi are added, as well as Pi-1 - the transfer from the i-1 digit. The result will be st - the sum and Pi - the transfer to the most significant digit. Thus, a one-bit binary adder is a device with three inputs and two outputs. Example 3.15. Construct a truth table for a one-bit binary adder using the table for adding binary numbers. Trigger. Triggers are used to store information in the computer's RAM, as well as in the internal registers of the processor. The trigger can be in one of two stable states, which allows you to remember, store and read 1 bit of information. The simplest trigger is the .RS trigger. It consists of two NOR gates that implement the F9 logic function (see Table 3.1). The inputs and outputs of the elements are connected by a ring: the output of the first is connected to the input of the second and the output of the second is connected to the input of the first. The trigger has two inputs S (from the English set - installation) and I (from the English reset - reset) and two outputs Q (direct) and Q (inverse). Rice. 2 Logic circuit of an RS flip-flop Example 3.16. Build a table describing the state of the inputs and outputs of the RS flip-flop. If the inputs receive signals R = 0 and S = 0, then the flip-flop is in storage mode; the previously set values ​​are stored at the outputs Q and Q. If a 1 signal is received at the setting input S for a short time, then the flip-flop goes into state 1 and after the signal at the S input becomes 0, the flip-flop will maintain this state, that is, it will store 1. When 1 is applied to the input R, the flip-flop will go to state 0. Applying a logical one to both inputs S and R can lead to an ambiguous result, therefore such a combination of input signals is prohibited. Tasks for independent completion 1. There are 16 logical functions of two variables (see table 3.1). Construct their logic circuits using basic logic gates: conjunctor, disjunctor, and inverter. 2. Prove that the logic circuit considered in Example 3.10 is a one-bit binary half-adder (the carry from the low-order bit is not taken into account). 3. Prove by constructing a truth table that the logical function P = (A&B)v(A&,P0)v(B&P0) determines the transfer to the most significant digit when adding binary numbers (A and B are terms, Po is a transfer from the least significant digit). 4. Prove by constructing a truth table that the logical function S = (AvBvP0)&Pv(A&.B&P0) determines the sum when adding binary numbers (A and B are terms, Po is a carryover from the low-order digit). 5. Construct a logical circuit of a one-bit binary adder. How many basic logic gates are needed to implement a 64-bit binary number adder? 6. How many basic logical elements form the RAM of a modern computer with a capacity of 64 MB? 1. Write down the numbers in expanded form: a) A8=143511; d)A10=143.511; 6)A2=100111; e)A8=0.143511; c)A16=143511; e)A1e=1AZ,5C1. 2. Write down the following numbers in collapsed form: a) A10=9-101+1*10+5"10-1+3-10~2; b)A16=A-161+1-16°+7-16" 1+5-16~2. 3. Are the numbers written correctly in the corresponding number systems: a) A10 = A,234; c) A16=456.46; b)A8=-5678; d)A2=22.2? 4. What minimum base does the number system have if the numbers 127, 222, 111 are written in it? Determine the decimal equivalent of these numbers in the found number system. 5. What is the decimal equivalent of the numbers 101012, 101018 1010116? 6. A three-digit decimal number ends with the digit 3. If this digit is moved two digits to the left, that is, the recording of a new number begins with it, then this new number will be one more than triple the original number. Find the original number. 2.22. A six-digit decimal number begins on the left with the digit 1. If this digit is moved from the first place on the left to the last place on the right, then the value of the resulting number will be three times greater than the original one. Find the original number. 2.23. Which of the numbers 1100112, 1114, 358 and 1B16 is: a) the largest; b) the smallest? 2.27. Is there a triangle whose side lengths are expressed by the numbers 12g, 1116 and 110112? 2.28.What is the largest decimal number that can be written in three digits in binary, octal and hexadecimal number systems? 2.29. “Frivolous” questions. When 2x2=100? When 6x6=44? When 4x4=20? 2.30. Write down the whole decimal numbers belonging to the following numerical intervals: a) ; b) ; V) . 2.31. There are 11,112 girls and 11,002 boys in the class. How many students are there in the class? 2.32. There are 36 students in the class, of which 21 are girls and 15 are boys. In what number system were students counted? 2.33. There are 100q fruit trees in the garden, of which 33q apple trees, 22q pears, 16q plums and 5q cherries. In what number system are trees counted? 2.34. There were 100q of apples. After each of them was cut in half, there were 1000q halves. In the number system, with what base were they counted? 2.35.I have 100 brothers. The youngest is 1000 years old, and the oldest is 1111 years old. The eldest is in class 1001. Could this be possible? 2.36. Once upon a time there was a pond in the center of which grew one leaf of a water lily. Every day the number of such leaves doubled, and on the tenth day the entire surface of the pond was already filled with lily leaves. How many days did it take to fill half the pond with leaves? How many leaves were there after the ninth day? 2.37.By selecting the powers of the number 2, which add up to a given number, convert the following numbers into the binary number system: a) 5; at 12; e) 32; b) 7; d) 25; f) 33. Check the correctness of the translation using the Advanced Converter program. 2.3. Converting numbers from one number system to another 2.3.1. Translating integers from one number system to another You can formulate an algorithm for converting integers from a system with base p to a system with base q: 1. Express the base of the new number system in digits of the original number system and perform all subsequent actions in the original number system. 2. Consistently divide the given number and the resulting integer quotients by the base of the new number system until we obtain a quotient that is smaller than the divisor. 3. The resulting remainders, which are digits of numbers in the new number system, are brought into accordance with the alphabet of the new number system. 4. Compose the number in new system calculation, writing it down starting from the last remainder. Example 2.12. Convert the decimal number 17310 to the octal number system: ■ We get: 17310=2558. Example 2.13. Convert the decimal number 17310 to hexadecimal number system: - We get: 17310=AD16. Example 2.14. Convert the decimal number 1110 to the binary number system. We get: 111O=10112. Example 2.15. Sometimes it is more convenient to write the translation algorithm in the form of a table. Let's convert the decimal number 36310 to binary. 2.3.2. Converting fractional numbers from one number system to another You can formulate an algorithm for converting a proper fraction with base p into a fraction with base q: 1. Express the base of the new number system in digits of the original number system and perform all subsequent actions in the original number system. 2. Consistently multiply the given number and the resulting fractional parts of the products by the base of the new system until the fractional part of the product becomes equal to zero or the required accuracy of number representation is achieved. 3. The resulting integer parts of the products, which are digits of the number in the new number system, are brought into accordance with the alphabet of the new number system. 4. Compose the fractional part of the number in the new number system, starting from the integer part of the first product. Example 2.16. Convert the number 0.6562510 to the octal number system. Example 2.17. Convert the number 0.6562510 to hexadecimal number system. Example 2.18. Convert the decimal fraction 0.562510 to the binary number system. Example 2.19. Convert the decimal fraction 0.710 to the binary number system. Obviously, this process can continue indefinitely, giving more and more new signs in the image of the binary equivalent of the number 0.710. So, in four steps we get the number 0.10112, and in seven steps the number 0.10110012, which is a more accurate representation of the number 0.710 in binary, and so on. Such an endless process is terminated at a certain step, when it is believed that the required accuracy of number representation has been obtained. 2.3.3. Translation of arbitrary numbers Translation of arbitrary numbers, that is, numbers containing an integer and a fractional part, is carried out in two stages. Translated separately whole part, separately - fractional. In the final recording of the resulting number, the integer part is separated from the fractional part. Example 2.20. Convert the number 17.2510 to the binary number system. Translating the whole part: Translating the fractional part: Example 2.21. Convert the number 124.2510 to octal. 2.3.4. Converting numbers from a number system with base 2 to a number system with base 2n and back Converting integers - If the base of the q-ary number system is a power of 2, then converting numbers from the q-ary number system to binary and back can be carried out using more simple rules . In order to write an integer binary number in the number system with base q = 2", you need to: 1. Divide the binary number from right to left into groups of n digits each. 2. If the last left group has fewer n digits, then it must be add zeros on the left to the required number of digits. 3. Consider each group as an n-bit binary number and write it with the corresponding digit in the number system with base q = 2p. Example 2.22. The number 1011000010001100102 is converted into the octal number system. We divide the number from right to left into triads and under each of them we write the corresponding octal digit: We get the octal representation of the original number: 5410628. Example 2.23. We convert the number 10000000001111100001112 into the hexadecimal number system. We divide the number from right to left into tetrads and under each of them we write the corresponding hexadecimal digit: We get the hexadecimal representation of the original number : 200F8716. Translation of fractional numbers. In order to write a fractional binary number in a number system with base q = 2", you need to: 1. Divide the binary number from left to right into groups of n digits each. 2. If the last right group contains fewer than n digits, then it must be supplemented on the right with zeros to the required number of digits. 3. Consider each group as an n-bit binary number and write it with the corresponding digit in the number system with the base q = 2n. Example 2.24. Let's convert the number 0.101100012 to the octal number system. We divide the number from left to right into triads and under each of them we write the corresponding octal digit: We get the octal representation of the original number: 0.5428. Example 2.25. Let's convert the number 0.1000000000112 to the hexadecimal number system. We divide the number from left to right into tetrads and under each of them we write the corresponding hexadecimal digit: We get the hexadecimal representation of the original number: 0.80316. Translation of arbitrary numbers. In order to write an arbitrary binary number in the number system with base q - 2n, you need: [ 1. Divide the integer part of a given binary number from right to left, and the fractional part from left to right into groups of n digits each. 2. If the last left and/or right groups contain less than n digits, then they must be supplemented on the left and/or right with zeros to the required number of digits. 3. Consider each group as an n-bit binary number and write it with the corresponding digit in the number system with the base q = 2n. Example 2.26. Let's convert the number 111100101.01112 to the octal number system. We divide the integer and fractional parts of the number into triads and under each of them write the corresponding octal digit: We get the octal representation of the original number: 745.34S. Example 2.27. Let's convert the number 11101001000.110100102 to the hexadecimal number system. We divide the integer and fractional parts of the number into tetrads and under each of them write the corresponding hexadecimal digit: We obtain a hexadecimal representation of the original number: 748,D216. Converting numbers from number systems with base q = 2 into the binary system. In order to convert an arbitrary number written in a number system with base q = 2 into the binary number system, you need to replace each digit of this number with its n-digit equivalent in the binary number system . Example 2.28. Let's convert the hexadecimal number 4AC351b into the binary number system. In accordance with the algorithm: i We get: 10010101100001101012. Tasks for independent completion 2.38. Fill out the table, in each row of which the same integer must be written in different number systems. 2.39. Fill out the table, in each row of which the same fractional number must be written in different number systems. 2.40. Fill out the table, in each row of which the same arbitrary number (the number can contain both an integer and a fractional part) should be written in different number systems. 2.4. Arithmetic operations in positional number systems

Arithmetic operations in the binary number system.


Example 2.29. Let's look at some examples of adding binary numbers:

Subtraction. When performing a subtraction operation, the smaller number is always subtracted from the larger number in absolute value and the corresponding sign is placed. In the subtraction table, a 1 with a bar means a loan in the highest rank.


Example 2.31. Let's look at some examples of multiplying binary numbers:

You see that multiplication comes down to shifts of the multiplicand and additions.

Division. The division operation is performed using an algorithm similar to the algorithm for performing the division operation in the decimal number system.


Addition in other number systems. Below is an addition table in the octal number system:

2.42. Arrange the signs of arithmetic operations so that the following equalities are true in the binary system:

Write the answer for each number in the indicated and decimal number systems. 2.44. What number precedes each of the following:

2.45. Write down the integers belonging to the following numerical intervals:

a) in the binary system;

b) in the octal system;

c) in hexadecimal system.

Write the answer for each number in the indicated and decimal number systems.



2.47. Find the arithmetic mean of the following numbers:

2.48.Sum of octal numbers 17 8 + 1700 8 + 170000 3 + 17000000 8 +
+ 1700000000 8 converted to hexadecimal number system.
Find the fifth digit from the left in the number equal to this amount.


Recover the unknown numbers indicated by a question mark in
the following examples on addition and subtraction, having first determined
Le, in what system the numbers are depicted.

Sections: Computer science

Target: teach students to perform arithmetic operations in the binary number system .
Tasks:
educational:
- repetition and consolidation of students’ knowledge about number systems;
- to develop in schoolchildren the ability to perform correctly arithmetic operations in the binary number system;
developing:
- develop logical thinking students;
- develop the cognitive interest of students.

During the classes.

Learning new material.
Addition rules:
0+0=0
0+1=1
1+0=1
1+1=10
Draw students' attention to the fact that when adding two units in the binary number system, the result is 0, and the unit is transferred to the next digit. When adding three units, the result is 1 in the entry, and the unit is transferred to the next digit. (1+1+1=11).

Example 1.
101+10=111

Example 2.
10011+11=1110


1001+11=1100
110+110=1100

Multiplication rules:
0*0=0
0*1=0
1*0=0
1*1=1

Example 1.
101*11=1111

Explanation:
We multiply each digit of the second factor by each digit of the first factor, the results of the products are added together according to the rules of addition in the binary number system. (Mathematics - 3rd grade).

Example 2.
1011*101=110111

Solution:

Students solve the following examples independently:
1001*101=101101
1001*11=11011

Subtraction rules:
0-0=0
1-0=1
1-1=0
0-1=-1
Draw students’ attention to the fact that the “minus” in the last rule means “take rank (1).”

Example 1.
10110-111=1111

Explanation:
Subtraction is done in the same way as in mathematics. If the digit in the minuend is less than the digit of the subtrahend, then for this subtraction it is necessary to occupy the digit (1), because 10-1=1. If there is a 0 to the left of such a subtraction, then we cannot occupy a rank. In this case, we occupy the digit in the minuend of the unit closest to the left of the given subtraction. In this case, all zeros from which we could not occupy a digit must be changed to one, because 0-1=-1. It is advisable to write down all changes in numbers on top of this subtraction. Perform further subtraction with the resulting numbers from above.

Example 2.
100000-11=11101

Students solve the following examples independently:
100010-100=
101011-10111=

Division rule:
Division is performed according to the rules of mathematics, not forgetting that we perform operations in the binary number system.

Example 1.
101101:1001=101

Explanation:
In the quotient, feel free to write the first 1, because a number in the binary system cannot begin with 0. We multiply this 1 by the divisor, and write the result correctly under the dividend, observing the bit depth. We perform subtraction according to the rules of subtraction in the binary number system. We take down the next digit of the dividend and compare the resulting number with the divisor. In this case, the resulting number is less than the divisor; in the quotient we write 0 (otherwise, 1). We take down the next digit of the dividend. We get a number equal to the divisor, write 1 in the quotient, etc.

Example 2.
101010:111=110

Examples for independent solutions:
1001000:1000=1001
111100:1010=110

Homework.
Follow these steps:
1100+1101=
101+101=
1011*101=
111*101=
11011-110=
10001-1110=
1011010:1010=

home \ Documentation \ For computer science teacher

When using materials from this site - and placing a banner is MANDATORY!!!

Binary arithmetic

The numbers we are used to using are called decimal and the arithmetic we use is also called decimal. This is because each number can be composed from a set of numbers containing 10 characters - numbers - "0123456789".

Mathematics developed in such a way that this particular set became the main one, but decimal arithmetic is not the only one. If we take only five digits, then on their basis we can construct five-digit arithmetic, and from seven digits - seven-digit arithmetic. In areas of knowledge related to computer technology, arithmetic is often used in which numbers are made up of sixteen digits; accordingly, this arithmetic is called hexadecimal. To understand what a number is in non-decimal arithmetic, we first find out what a number is in decimal arithmetic.

Take, for example, the number 246. This notation means that there are two hundreds, four tens and six ones in the number. Therefore, we can write the following equality:

246 = 200 + 40 + 6 = 2 * 10 2 + 4 * 10 1 + 6 * 10 0

Here, equal signs separate three ways of writing the same number. The third form of notation is most interesting to us now: 2 * 10 2 + 4 * 10 1 + 6 * 10 0 . It is structured as follows:

Our number has three digits. The leading digit "2" is number 3. So it is multiplied by 10 to the second power. The next digit "4" has a serial number of 2 and is multiplied by 10 in the first one. It is already clear that digits are multiplied by ten to the power of one less than the serial number of the digit. Having understood the above, we can write down the general formula for representing a decimal number. Let's be given a number with N digits. We will denote i-th digit through a i. Then the number can be written in the following form: a n a n-1 ....a 2 a 1 . This is the first form, and the third entry form will look like this:

a n a n-1 ….a 2 a 1 = a n * 10 n-1 + a n-1 * 10 n-2 + …. + a 2 * 10 1 + a 1 * 10 0

where a i is a character from the set "0123456789"

The role of the ten is very clearly visible in this recording. Ten is the basis for the formation of numbers. And by the way, it is called “the base of the number system,” and the number system itself is why it is called “decimal.” Of course, the number ten does not have any special properties. We can easily replace ten with any other number. For example, a number in the five-digit number system can be written like this:

a n a n-1 ….a 2 a 1 = a n * 5 n-1 + a n-1 * 5 n-2 + …. + a 2 * 5 1 + a 1 * 5 0

where a i is a character from the set "01234"

In general, we replace 10 with any other number and get a completely different number system and different arithmetic. The simplest arithmetic is obtained if 10 is replaced by 2. The resulting number system is called binary and the number in it is defined as follows:

a n a n-1 ….a 2 a 1 = a n * 2 n-1 + a n-1 * 2 n-2 + …. + a 2 * 2 1 + a 1 * 2 0

where a i is a character from the set "01"

This system is the simplest of all possible, since in it any number is formed only from two digits 0 and 1. It is clear that it couldn’t be simpler. Examples of binary numbers: 10, 111, 101.

Very important question. Can a binary number be represented as a decimal number and vice versa, can a decimal number be represented as a binary number.

Binary to Decimal. It's very simple. The method of such translation is given by our way of writing numbers. Let's take, for example, the following binary number 1011. Let's expand it into powers of two. We get the following:

1011 = 1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0

Let's perform all the recorded actions and get:

1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0 = 8 + 0+ 2 + 1 = 11. Thus, we get that 1011 (binary) = 11 (decimal). A slight inconvenience of the binary system is immediately visible. The same number, which is written in the decimal system with one digit in the binary system, requires four digits for its recording. But this is the price for simplicity (nothing comes for free). But the binary system gives a huge gain in arithmetic operations. And we will see this later.

Express the following binary numbers as a decimal.

a) 10010 b) 11101 c) 1010 c) 1110 d) 100011 e) 1100111 f) 1001110

Addition of binary numbers.

The method of column addition is generally the same as for a decimal number. That is, addition is performed bitwise, starting with the least significant digit. If, when adding two digits, the SUM is greater than nine, then the digit = SUM - 10 is written, and the WHOLE PART (SUM / 10) is added in the most significant digit. (Add a couple of numbers in a column, remember how this is done.) The same with a binary number. Add one by one, starting with the lowest digit. If the result is more than 1, then 1 is written down and 1 is added to the most significant digit (they say “off the top of my head”).

Let's do the example: 10011 + 10001.

First category: 1+1 = 2. We write 0 and 1 as it comes to mind.

Second category: 1+0+1(memorized unit) =2. We write down 0 and 1, it came to mind.

Third category: 0+0+1(memorized unit) = 1. Write 1.

Fourth category 0+0=0. We write 0.

Fifth category 1+1=2. We write down 0 and add 1 to the sixth digit.

Let's convert all three numbers to the decimal system and check the correctness of the addition.

10011 = 1*2 4 + 0*2 3 + 0*2 2 + 1*2 1 + 1*2 0 = 16 + 2 + 1 =19

10001 = 1*2 4 + 0*2 3 + 0*2 2 + 0*2 1 + 1*2 0 = 16 + 1 = 17

100100 = 1*2 5 + 0*2 4 + 0*2 3 + 1*2 2 + 0*2 1 + 0*2 0 =32+4=36

17 + 19 = 36 correct equality

Examples for independent solutions:

a) 11001 +101 =

b) 11001 +11001 =

c) 1001 + 111 =

e) 10011 + 101 =

e) 11011 + 1111 =

e) 11111 + 10011 =

How to convert a decimal number to binary. The next operation is subtraction. But we will deal with this operation a little later, and now we will consider the method of converting a decimal number to binary.

In order to convert a decimal number to binary, it must be expanded to powers of two. But if the expansion in powers of ten is obtained immediately, then how to expand in powers of two requires a little thought. First, let's look at how to do this using the selection method. Let's take the decimal number 12.

Step one. 2 2 = 4, this is not enough. Also 2 3 = 8 is not enough, but 2 4 = 16 is already a lot. Therefore, we leave 2 3 =8. 12 - 8 = 4. Now you need to represent it as a power of two 4.

Step two. 4 = 2 2 .

Then our number is 12 = 2 3 + 2 2. The highest digit has the number 4, the highest degree = 3, therefore, there must be terms with powers of two 1 and 0. But we don’t need them, so in order to get rid of unnecessary degrees and leave the necessary ones, we write the number like this: 1*2 3 + 1* 2 2 +0*2 1 + 0*2 0 = 1100 - this is the binary representation of the number 12. It is easy to notice that each successive power is the largest power of two, which is less than the decomposed number. To consolidate the method, let's look at another example. Number 23.

Step 1. The nearest power of two is 2 4 = 16. 23 -16 = 7.

Step 2. Nearest power of two 2 2 = 4. 7 - 4 = 3

Step 3. Nearest power of two 2 1 = 2. 3 - 2 = 1

Step 4. Nearest power of two 2 0 =1 1 - 1 =0

We get the following expansion: 1*2 4 + 0*2 3 +1*2 2 +1*2 1 +1*2 0

And our desired binary number is 10111

The method discussed above solves the problem assigned to it well, but there is a method that is algorithmized much better. The algorithm for this method is written below:

As long as the NUMBER is greater than zero, do

NEXT DIGIT = remainder of NUMBER divided by 2

NUMBER = integer part of NUMBER divided by 2

When this algorithm completes its work, the sequence of calculated NEXT DIGITS will represent a binary number. For example, let's work with the number 19.

Algorithm start NUMBER = 19

NEXT DIGIT = 1

NEXT DIGIT = 1

NEXT DIGIT = 0

NEXT DIGIT = 0

NEXT DIGIT = 1

So, as a result, we have the following number 10011. Note that the two methods discussed differ in the order in which the next digits are obtained. In the first method, the first digit received is the most significant digit of the binary number, and in the second, the first digit received is, on the contrary, the least significant.

Convert decimal numbers to binary in two ways

a) 14 b) 29 c) 134 d) 158 f) 1190 g) 2019

How to convert a fraction to a decimal number.

It is known that any rational number can be represented as a decimal and an ordinary fraction. Common fraction, that is, a fraction of the form A/B can be regular and irregular. A fraction is called proper if A<В и неправильной если А>IN.

If a rational number is represented by an improper fraction, and the numerator of the fraction is divided by the denominator by a whole, then this rational number is an integer; in all other cases, a fractional part appears. The fractional part is often a very long number and even infinite (an infinite periodic fraction, for example 20/6), so in the case of fractional part We have not just the task of translating one representation into another, but translation with a certain accuracy.

Rule of accuracy. Suppose you are given a decimal number, which in the form decimal representable up to N digits. In order for the corresponding binary number to be of the same precision, it is necessary to write M - signs in it, so that

Now let’s try to get the translation rule, and first let’s look at example 5,401

Solution:

We will obtain the integer part according to the rules already known to us, and it is equal to the binary number 101. And we will expand the fractional part in powers of 2.

Step 1: 2 -2 = 0.25; 0.401 - 0.25 = 0.151. - this is the remainder.

Step 2: Now we need to represent 0.151 as a power of two. Let's do this: 2 -3 = 0.125; 0.151 - 0.125 = 0.026

Thus, the original fractional part can be represented as 2 -2 +2 -3. The same thing can be written in this binary number: 0.011. The first fractional digit is zero, this is because in our expansion there is no power of 2 -1.

From the first and second steps it is clear that this representation is not accurate and it may be desirable to continue the expansion. Let's look at the rule. It says that we need so many signs of M that 10 3 is less than 2 M. That is, 1000<2 M . То есть в двоичном разложении у нас должно быть не менее десяти знаков, так как 2 9 = 512 и только 2 10 = 1024. Продолжим процесс.

Step 3: Now we are working with the number 0.026. The closest power of two to this number is 2 -6 = 0.015625; 0.026 - 0.015625 = 0.010375 Now our more accurate binary number is: 0.011001. There are already six places after the decimal point, but this is not enough yet, so we perform one more step.

Step 4: Now we are working with the number 0.010375. The closest power of two to this number is 2 -7 = 0.0078125;

0,010375 - 0,0078125 = 0,0025625

Step 5: Now we are working with the number 0.0025625. The closest power of two to this number is 2 -9 = 0.001953125;

0,0025625 - 0,001953125 = 0,000609375

The last resulting remainder is less than 2 -10 and if we wanted to continue approximating the original number, we would need 2 -11, but this already exceeds the required accuracy, and therefore the calculations can be stopped and the final binary representation of the fractional part can be written down.

0,401 = 0,011001101

As you can see, converting the fractional part of a decimal number to binary is a little more complicated than converting the integer part. Table of powers of two at the end of the lecture.

Now let’s write down the conversion algorithm:

Initial data of the algorithm: Through A we will denote the original proper decimal fraction written in decimal form. Let this fraction contain N characters.

Algorithm

Action 1. Determine the number of required binary digits M from the inequality 10 N< 2 M

Action 2: Cycle for calculating the digits of the binary representation (digits after zero). The digit number will be denoted by the symbol K.

  1. Digit number = 1
  2. If 2 -K > A

Then we add zero to the binary number

    • add 1 to the binary number
    • A = A - 2 -K
  1. K = K + 1
  2. If K > M
  • then the algorithm is completed
  • Otherwise, go to point 2.

Convert decimal numbers to binary

a) 3.6 b) 12.0112 c) 0.231 d) 0.121 d) 23.0091

Subtracting binary numbers. We will also subtract numbers in a column and the general rule is the same as for decimal numbers, subtraction is performed bit by bit and if there is not enough one in the digit, then it is carried out in the highest one. Let's solve the following example:

First category. 1 - 0 =1. We write down 1.

Second category 0 -1. One is missing. We occupy it in the senior category. A unit from a senior digit goes into a junior one, like two units (because the senior digit is represented by a two of a higher degree) 2-1 = 1. We write down 1.

Third category. We occupied a unit of this rank, so now in rank 0 there is a need to occupy a unit of the highest rank. 2-1 =1. We write down 1.

Let's check the result in the decimal system

1101 - 110 = 13 - 6 = 7 (111) Correct equality.

Another interesting way to perform subtraction involves the concept of two's complement code, which allows you to reduce subtraction to addition. The result of a number in two's complement code is extremely simple: we take the number, replace the zeros with ones, on the contrary, replace the ones with zeros and add one to the least significant digit. For example, 10010, the additional code will be 011011.

The rule of subtraction through two's complement states that subtraction can be replaced by addition if the subtrahend is replaced by a number in two's complement.

Example: 34 - 22 = 12

Let's write this example in binary form. 100010 - 10110 = 1100

The additional code of the number 10110 will be like this

01001 + 00001 = 01010. Then the original example can be replaced by addition like this: 100010 + 01010 = 101100 Next, you need to discard one unit in the most significant digit. If we do this, we get 001100. Let’s discard insignificant zeros and get 1100, that is, the example was solved correctly

Perform subtractions. In the usual way and in additional code, having previously converted decimal numbers to binary:

Check by converting the binary result to the decimal number system.

Multiplication in the binary number system.

First, consider the following interesting fact. In order to multiply a binary number by 2 (decimal two is 10 in the binary system), it is enough to add one zero to the left of the number being multiplied.

Example. 10101 * 10 = 101010

Examination.

10101 = 1*2 4 + 0*2 3 + 1*2 2 + 0*2 1 +1*2 0 = 16 + 4 + 1 = 21

101010 =1*2 5 + 0*2 4 + 1*2 3 + 0*2 2 +1*2 1 +0*2 0 = 32 + 8 + 2 = 42

If we remember that any binary number can be expanded into powers of two, then it becomes clear that multiplication in the binary number system is reduced to multiplication by 10 (that is, by decimal 2), and therefore, multiplication is a series of successive shifts. General rule is as follows: as for decimal numbers, binary multiplication is performed bitwise. And for each digit of the second multiplier, one zero is added to the right of the first multiplier. Example (not yet in a column):

1011 * 101 This multiplication can be reduced to the sum of three digit multiplications:

1011 * 1 + 1011 * 0 + 1011 * 100 = 1011 +101100 = 110111 The same can be written in a column like this:

Examination:

101 = 5 (decimal)

1011 = 11 (decimal)

110111 = 55 (decimal)

5*11 = 55 correct equality

Decide for yourself

a) 1101 * 1110 =

b) 1010 * 110 =

e) 101011 * 1101 =

e) 10010 * 1001 =

Note: By the way, the multiplication table in the binary system consists of only one item 1 * 1 = 1

Division in the binary number system.

We have already looked at three actions and I think it is already clear that, in general, actions on binary numbers differ little from actions on decimal numbers. The only difference is that there are two numbers and not ten, but this only simplifies arithmetic operations. The situation is the same with division, but for a better understanding, we will analyze the division algorithm in more detail. Suppose we need to divide two decimal numbers, for example 234 divided by 7. How do we do this.

We select to the right (from the most significant digit) such a number of digits that the resulting number is as small as possible and at the same time larger than the divisor. 2 is less than the divisor, therefore the number we need is 23. Then we divide the resulting number by the divisor with a remainder. We get the following result:

We repeat the described operation until the resulting remainder is less than the divisor. When this happens, the number obtained under the line is the quotient, and the last remainder is the remainder of the operation. So the operation of dividing a binary number is performed in exactly the same way. Let's try

Example: 10010111 / 101

We are looking for a number whose first digit is greater than the divisor. This is the four-digit number 1001. It is in bold. Now you need to find a divisor for the selected number. And here we again win in comparison with the decimal system. The fact is that the selected divisor is necessarily a number, and we only have two numbers. Since 1001 is clearly greater than 101, then everything is clear with the divisor: 1. Let’s perform the operation step.

So, the remainder of the completed operation is 100. This is less than 101, so to perform the second division step, you need to add the next digit to 100, this is the digit 0. Now we have the following number:

1000 is greater than 101, so in the second step we will again add the number 1 to the quotient and get the following result (to save space, we will immediately omit the next digit).

Third step. The resulting number 110 is greater than 101, so at this step we will write 1 into the quotient. It will turn out like this:

The resulting number 11 is less than 101, so we write the number 0 in the quotient and lower the next number down. It turns out like this:

The resulting number is greater than 101, so we write the number 1 into the quotient and perform the actions again. It turns out this picture:

1

0

The resulting remainder 10 is less than 101, but we have run out of digits in the dividend, so 10 is the final remainder, and 1110 is the required quotient.

Let's check in decimal numbers

This concludes the description of the simplest arithmetic operations that you need to know in order to use binary arithmetic, and now we will try to answer the question “Why is binary arithmetic needed?” Of course, it has already been shown above that writing a number in the binary system significantly simplifies arithmetic operations, but at the same time the recording itself becomes much longer, which reduces the value of the resulting simplification, so it is necessary to look for problems whose solution is much simpler in binary numbers.

Task 1: Retrieving all samples

Very often there are problems in which you need to be able to construct all possible combinations from a given set of objects. For example, this task:

Given a large pile of stones, arrange the stones into two piles so that the mass of the two piles is as equal as possible.

This task can be formulated as follows:

Find a selection of stones from a large pile such that its total mass differs as little as possible from half the mass of the large pile.

There are quite a lot of tasks of this kind. And they all boil down, as has already been said, to the ability to obtain all possible combinations (hereinafter we will call them samples) from a given set of elements. And now we will look at the general method of obtaining all possible samples using the binary addition operation. Let's start with an example. Let there be a set of three objects. Let's construct all possible samples. We will denote objects by serial numbers. That is, there are the following items: 1, 2, 3.

Samples: (0, 0, 1); (0, 1, 0); (0, 1, 1); (100); (1, 0, 1); (1, 1, 0); (1, 1, 1);

If the position with the next number is one, then this means that an element with a number equal to this position is present in the selection, and if there is a zero, then the element is not present. For example, sample (0, 1, 0); consists of one element with number 2, and the selection is (1, 1, 0); consists of two elements with numbers 1 and 2.

This example clearly shows that a sample can be represented as a binary number. In addition, it is easy to see that all possible one, two and three-digit binary numbers are written above. Let's rewrite them as follows:

001; 010; 011; 100; 101; 110; 111

1; 10; 11; 100; 101; 110; 111

We have received a series of consecutive binary numbers, each of which is obtained from the previous one by adding one. You can check this. Using this observed pattern, we can construct the following algorithm for obtaining samples.

Algorithm input data

Given a set of objects N - pieces. In what follows we will call this set the set of initial elements. Let's number all the elements of the original set from 1 to N. Let's make a binary number from N insignificant zeros. 0000… 0 N This zero binary number will denote the zero sample with which the sampling process will begin. The digits of a number are counted from right to left, that is, the leftmost digit is the most significant.

Let's agree to denote this binary number in capital letters BINARY

Algorithm

If a BINARY number consists entirely of ones

Then we stop the algorithm

    • We add one to a BINARY number according to the rules of binary arithmetic.
    • From the resulting BINARY number we make the next sample, as described above.

Problem 2: Finding large prime numbers

To begin with, let us remember that a prime number is a natural number that is divisible only by 1 and itself. Examples of prime numbers: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Finding large prime numbers is very important math problem. Large prime numbers necessary for reliable encryption of messages using certain encryption algorithms. Moreover, they are necessary not only big numbers, but very large. The larger the number, the more reliable the cipher built on this number.

Note. A strong cipher is a cipher that takes a very long time to decipher.

Why? A prime number acts as a key for encryption and decryption. In addition, we know that prime numbers occur in the series natural numbers not too often. There are quite a lot of them among the first thousand, then their number begins to quickly decrease. Therefore, if we take as a key not very big number, the decipherer, using even a not very fast computer, will be able to get to it (by trying out all the simple ones as a key, one after another) in a limited time.

A fairly reliable code can be obtained if you take a simple one, for example 150 characters. However, finding such a simple one is not so easy. Suppose that a certain number A (very large) needs to be checked for primality. This is the same as looking for its divisors. If we can find divisors in the range from 2 to the square root of A, then it is not prime. Let's estimate the number of numbers that need to be tested for the ability to divide the number A.

Let's say number A has 150 digits. The square root of it will contain at least 75 characters. To enumerate such a number of possible divisors we will need a very powerful computer and great time, which means that the problem is practically unsolvable.

How to deal with this.

Firstly, you can learn to quickly check for the divisibility of one number by another, and secondly, you can try to select the number A in such a way that it is prime with a high degree of probability. It turns out this is possible. The mathematician Mersen discovered that numbers of the following form

They are simple with a high degree of probability.

To understand the phrase written above, let’s count how many prime numbers are in the first thousand and how many Mersen numbers are prime in the same thousand. So, the Mersen numbers in the first thousand are as follows:

2 1 - 1 = 1 ; 2 2 -1 = 3 ; 2 3 - 1 = 7 ; 2 4 - 1 = 15; 2 5 - 1 = 31 ; 2 6 -1 = 63;

2 7 - 1 =127 ; 2 8 -1 = 255; 2 9 - 1 = 511;

Prime numbers are marked in bold. There are 5 prime numbers for 9 Mersen numbers. As a percentage, this is 5/9*100 = 55.6%. At the same time, for every 1000 first natural numbers, there are only 169 prime numbers. As a percentage, this is 169/1000*100 = 16.9%. That is, in the first thousand, in percentage terms, primes among Mersen numbers are found almost 4 times more often than among simple natural numbers

___________________________________________________________

Now let's take a specific Mersen number, for example 2 4 - 1. Let's write it as a binary number.

2 4 - 1 = 10000 - 1 = 1111

Let's take the following Mersen number 2 5 -1 and write it as a binary number. We get the following:

2 5 -1 = 100000 - 1 = 11111

It is already clear that all Mersen numbers are a sequence of ones and this fact itself gives a big gain. Firstly, in the binary number system it is very simple to obtain the next Mersen number, just add one to the next number, and secondly, looking for divisors in the binary system is much easier than in the decimal system.

Quick decimal to binary conversion

One of the main problems with using the binary number system is the difficulty in converting a decimal number to binary. This is quite a labor-intensive task. Of course, it is not too difficult to translate small numbers of three or four digits, but for decimal numbers with 5 or more digits this is already difficult. That is, we need a way to quickly convert large decimal numbers into binary.

This method was invented by the French mathematician Legendre. Let, for example, be given the number 11183445. We divide it by 64, we get a remainder of 21 and the quotient is 174741. We divide this number again by 64, we get a remainder of 21 and a quotient of 2730. Finally, 2730 divided by 64 gives a remainder of 42 and a quotient of 42 But 64 in binary is 1000000, 21 in binary is 10101, and 42 is 101010, Therefore, the original number is written in binary as follows:

101010 101010 010101 010101

To make it more clear, here is another example with a smaller number. Let's convert the binary representation of the number 235. Divide 235 by 64 with a remainder. We get:

QUANTIATE = 3, binary 11 or 000011

REMAINDER = 43, binary 101011

Then 235 = 11101011. Let's check this result:

11101011 = 2 7 + 2 6 + 2 5 + 2 3 + 2 1 + 2 0 = 128+64+32+8+2+1 = 235

Notes:

  1. It is easy to see that the final binary number includes all remainders and, at the last step, both the remainder and the quotient.
  2. The quotient is written before the remainder.
  3. If the resulting quotient or remainder has less than 6 digits in binary representation (6 zeros contains the binary representation of the number 64 = 1000000), then insignificant zeros are added to it.

And one more complex example. The number is 25678425.

Step 1: 25678425 divided by 64

Private = 401225

Remaining = 25 = 011001

Step 2: 401225 divided by 64

Quotient = 6269

Remainder = 9 = 001001

Step 3: 6269 divided by 64

Quotient = 97

Remaining = 61 = 111101

Step 4: 97 divided by 64

Quotient = 1 = 000001

Remaining = 33 = 100001

Number result = 1.100001.111101.001001.011001

In this number, the intermediate results included in it are separated by a dot.

Convert numbers to binary representation:

APPENDIX: TABLE 1

0,015625

0,0078125

0,00390625

0,001953125

0,0009765625

0,00048828125

0,000244140625

0,0001220703125

0,00006103515625

0,000030517578125

0,0000152587890625

0,00000762939453125

0,000003814697265625

0,0000019073486328125

0,00000095367431640625

0,000000476837158203125

Converting a number from binary to decimal

Converting a number from the binary system to the decimal system can be carried out for the integer and fractional parts of the number using one algorithm by calculating the sum of the products of a digit of a binary number by the weight of its familiarity:

11100011 2 =1*2 7 +1*2 6 +1*2 5 +0*2 4 +0*2 3 +0*2 2 +1*2 1 +1*2 0 =128+64+32+2+1=227 10

0,10100011 2 =1*2 -1 +0*2 -2 +1*2 -3 +0*2 -4 +0*2 -5 ++0*2 -6 +1*2 -7 +1*2 -8 =0.5+0.125+0.0078+0.0039=0.6367

Converting a number from decimal to binary

Converting a number from the decimal system to the binary system is carried out separately for the integer and fractional parts of the number using the following algorithms:

a) an integer decimal number is divided evenly by the base 2, then all quotients of integer division are successively divided by 2 until the quotient is less than the base. The result includes the last quotient and all remainders from the division, starting from the last. For example:

convert the number 227 to binary form:

227:2=113 (we write the remainder of division 1 as the result), 113:2=56 (we write the remainder of division 1 as the result), 56:2=28 (we write the remainder of division 0 as the result), 28:2=14 (we write the remainder of division 0 as the result), 14:2=7 (we write the remainder of division 0 as the result), 7:2=3 (we write the remainder of division 1 as the result), 3:2=1 (we write the remainder as the result from division 1), we write the last quotient into the result - 1. Total we get: 227 10 = 11100011 2. Let's check with a reverse translation:

1*2 0 +1*2 1 +0*2 2 +0*2 3 +0*2 4 +1*2 5 +1*2 6 +1*2 7 =1+2+32+64+128=227

b) decimal is sequentially multiplied by base 2, and immediately after each multiplication operation, the resulting integer part is written to the result and does not participate in further multiplication (discarded). The number of multiplication operations depends on the required precision, for example:

Let's convert the number 0.64 into binary form:

0.64*2=1.28 (discard 1 and write 1 to the result)

0.28*2=0.56 (we write 0 as the result)

0.56*2=1.12 (discard 1 and write 1 to the result)

0.12*2=0.24 (we write 0 as the result)

0.24*2=0.48 (we write 0 as the result)

0.48*2=0.96 (we write 0 as the result)

0.96*2=1.82 (write 1 as result)

Total: 0.64 10 =0.1010001 2

Let's check with a reverse translation:

1*2 -1 +0*2 -2 +1*2 -3 +0*2 -4 +0*2 -5 +0*2 -6 +1*2 -7 = 0.5*0+0.125+0+0+0+0.0078=0.6328

Computer representation of negative numbers

It should be borne in mind that in computer memory binary numbers are stored in registers consisting of 8 cells, i.e. The minimum binary number that can be stored in memory must be eight bits. In this case, zeros are written in the unfilled register cells (in the most significant bits).

Unlike the decimal system, the binary number system does not have special symbols to indicate the sign of a number: positive (+) or negative (-), so the following two forms are used to represent binary negative numbers.

Signed value form– the most significant (left) digit is marked as signed and contains information only about the sign of the number:

1 is a negative number, 0 is a positive number.

The remaining categories are allocated to absolute value numbers.

5 10 = 0000 0101 2 ; -5 10 =1000 0101 2 .

The computer is designed in such a way that negative numbers are represented in two's complement code, since this provides significant time savings when performing arithmetic operations with them.

A form of reverse complement code, the translation into which is carried out using the following algorithm:

1) Discard the sign bit;

2) invert all digits of a number;

3) add one to the resulting code;

4) restore one in the sign bit.
For example:

Converting the number -5 10

We write it in binary form: 1000 0101; discard the sign bit: 000 0101; invert all digits: 111 1010; add one: 111 1010 + 1 = 111 1011; we restore one in the sign bit: 1111 1011. Total -5 10 in reverse complement code is written as 1111 1011.

Rules for performing arithmetic operations in the binary system

Addition. The addition operation is performed in the same way as in the decimal system. An overflow of a bit results in the appearance of a one in the next bit:

0+0=0, 0+1=1, 1+1=10;

+ 111011

Subtraction. Since most modern computers have only one hardware adder, which is used to implement all arithmetic operations, subtraction is reduced to addition with a negative number:

Rules for subtraction in the binary system. Algorithm for the subtraction operation by adding complementary codes:

1) convert a negative number from signed form to two's complement;

2) perform the binary addition operation on all digits,
including signed, ignoring carry unit from highest
discharge;

3) when the sign digit of the sum is equal to one, which means
receiving a negative result in the form of an additional code,
it is necessary to convert the result into signed form (using an algorithm for converting to inverse form).

For example, let's perform the action 13-15=13+(-15)

1. Convert -15 into additional code form:

1000 1111 –> 000 1111 -> 111 0000 -> 111 0000 +1=111 0001 -> 1111 0001

2. Add 13 and -15:

+11110001

3. Convert to regular binary form:

1111 1110 -> 111 1110 ->000 0001 -> 000 0001+1=000 0010 -> 1000 0010 = -2 10

Thus, when performing addition and subtraction operations, the processor's arithmetic logic unit has to perform bitwise addition with carry, inversion, and sign checking of binary numbers.

In cases where it is necessary to perform arithmetic operations on numbers greater than 127, they are placed not in one, but in two or more bytes.

For example, let's perform the action: 15-13=15+(-13)

1. Translate -13 into additional code form:

1000 1101 –> 000 1101 -> 111 0010 -> 111 0010 +1=111 0011 -> 1111 0011

2. Add 15 and -13:

+11110011

3. The sign bit is 0, reverse translation is not required, i.e. the result is 0000 0010 = 2 10

Multiplication. If, along with the listed operations, shift operations are performed, then using the adder you can also perform multiplication, which is reduced to a series of repeated additions. If the digit in the zero position of the multiplier is 1, then the multiplicand is rewritten under the corresponding digits; multiplication by subsequent ones leads to a shift of the addend to the left by one position. If the digit of the multiplier is 0, then the next term is shifted two positions to the left.

For example, multiply 6 (0000 0110) by 5 (0000 0101):

*00000101

(multiply by 1) +00000110

(multiply by 0) 1

(multiply by 1) + 0000011011

Let's check: 0001 1110=0*2 0 +1*2 1 +1*2 2 +1*2 3 +1*2 4 =2+4+8=16=30

For example, multiply 15 (0000 1111) by 13 (0000 1101):

*00001101

(multiply by 1) +00001111

(multiply by 0) 1

(multiply by 1) +0000111111

(multiply by 1) + 00001111111

Let's check: 1100 0011=1*2 7 +1*2 6 +0*2 5 +0*2 4 +0*2 3 +0*2 2 +1*2 1 +1*2 0 =1+2+64 +128=195

Division. When performing a division operation, a subtraction operation is performed several times. Therefore, you must first find an additional divisor code. Division is accomplished by repeated subtraction and shifting. For example, let's divide the number 195 (1100 0011) by 15 (0000 1111). Additional code of the number 0000 1111 -> 11110001. Since according to the division rules, each intermediate dividend must be greater than the divisor, we choose the number 11000 as the first dividend, i.e. the first five digits and add three zeros to the left, completing the dividend to 8 digits. Then we add it with the additional code of the dividend and enter one into the result. If the next dividend after removing the next digit is less than the divisor, then zero is entered into the result and another digit from the original dividend is added to the dividend.