Binary arithmetic

Parameter name	Meaning
Article topic:	Binary arithmetic
Rubric (thematic category)	Computer science

Binary number system

Number systems used when working with computers

Base P = 2. The alphabet includes two binary digits: 0, 1. Any number C = C n C n-1 ...C 1 C 0 C -1 C -m is the sum of powers of the number P = 2,

C = C n × 2 n +C n-1 × 2 n-1 +…+C 1 × 2 1 +C 0 × 2 0 +C -1 × 2 -1 +…+C -m × 2 -m

Example 3.6.

101011.11 2 =1×2 5 + 0×2 4 + 1×2 3 + 0×2 2 +1×2 1 + 1×2 0 +1×2 -1 + 1×2 -2 = 32+8 +2+1+0.5+0.25=43.75 10.

The weights of the digits in the binary number system are 1, 4, 8.16,... to the left of the decimal point and 0.5; 0.25; 0.125; 0.625;... to the right of the decimal point.

Sometimes used in programming hexadecimal notation. To represent numbers greater than 9 in the hexadecimal number system, the Latin letters A, B, C, D, E, F are used. Images of the first sixteen numbers in the decimal, binary and hexadecimal number systems are given in Table. 2.

Code table in various systems dead reckoning

table 2

Decimal system	Binary system	Hexadecimal system	Decimal system	Binary system	Hexadecimal system
					A
					B
					C
					D
					E
					F

Binary Decimal The number system has become widespread in modern computers due to the ease of conversion to the decimal system and vice versa. It is used where the main attention is paid not to the simplicity of the technical construction of the machine, but to the convenience of the user. In this number system, all decimal digits are separately encoded by four binary digits.

Example 3.7.

The decimal number 9703 in BCD looks like this: 1001 0111 0000 0011.

The advantage of the binary number system over the decimal number system from the point of view of a digital computer is the following:

• elements with two stable states are required;
• arithmetic operations are significantly simplified;
• 1.5 times less equipment is required;
• allows you to use the apparatus of mathematical logic for the analysis and synthesis of circuits.

The disadvantages of the binary number system are as follows:

• large number recording length;
• When entering and outputting information, conversion to the decimal number system is required.

Let's look at how basic operations are performed in binary arithmetic.

The rules of arithmetic in all positional number systems are the same, ᴛ.ᴇ. addition, multiplication and subtraction begin from the lowest digits, division - from the highest ones.

When adding, the carry unit is added to the digits of the adjacent most significant digit. When subtracted, a unit of borrowing in the highest digit gives two units in the lowest adjacent digit.

Example 3.8

Multiplying binary numbers is similar to multiplying decimal numbers, but... If we multiply only by 0 and 1, then multiplication is reduced to the operation of shift and addition.

Example 3.9

Binary arithmetic - concept and types. Classification and features of the category "Binary Arithmetic" 2017, 2018.

- Binary arithmetic

Because information processes V digital systems take values ​​only 0 and 1, then data representation is carried out using binary numbers. Addition and subtraction of binary numbers, as well as all other arithmetic operations, are performed according to the same rules as... .

- Binary number system and binary arithmetic

In the binary number system, you can perform the same operations with numbers as in the decimal number system. Addition is performed on the same principle as in the decimal number system: only if a given digit produces an amount that does not fit in it, then...

, Competition "Presentation for the lesson"

Presentation for the lesson

Back forward

Attention! Preview The slides are for informational purposes only and may not represent all the features of the presentation. If you are interested this work, please download the full version.

Lesson objectives: (slide 2)

1. Introduce students to the binary number system.
2. Develop skills in performing arithmetic operations with binary numbers

During the classes

I. Start of the lesson

Teacher: In order to better master the binary number system, you need to master performing arithmetic operations on binary numbers.

All positional number systems are “the same”, namely, in all of them arithmetic operations are performed according to the same rules:

• the same laws of arithmetic are valid: commutative, associative, distributive;
• the rules of addition, subtraction, multiplication and division are valid;
• The rules for performing arithmetic operations are based on addition and multiplication tables.

Let's look at the rules for performing arithmetic operations

II. Learning new material

When dividing by a column, you have to perform multiplication and subtraction as intermediate results. But in the binary number system, intermediate multiplications are reduced to multiplying the divisor by either 0 or 1, so the most difficult operation remains subtraction, which you must learn to do accurately.

III. Consolidation of what has been learned. (slide 12)

The guys do the work on their own. Then open the slide with the answers.

Answers. (Slide 13)

IV. Homework (slide 14)

1. Learn the rules for performing arithmetic operations in the binary number system.

2. Follow these steps:

1. 110010+11,01
2. 1111001-1101
3. 10101,1*11
4. 10101110:101

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 equipment 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. Is it possible to represent a binary number as a decimal number and vice versa? decimal number represent it in binary form.

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 method, 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. An ordinary fraction, that is, a fraction of the form A/B, can be regular and improper. 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 the fractional part we have not just the task of translating one representation into another, but translating with a certain accuracy.

Rule of accuracy. Suppose you are given a decimal number that can be represented as a decimal fraction with an accuracy of 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 place, then it is done 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. The general rule is that, as with 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 highlighted 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 a very important mathematical problem. Large prime numbers are necessary for some encryption algorithms to securely encrypt messages. Moreover, not just large numbers are needed, but very large ones. 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 a not very large number as a key, the decipherer, with the help of not even a very large one, 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 very powerful computer and a huge amount of 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

Performing arithmetic operations in any positional number system is carried out according to the same rules that are used in the decimal number system.

Just as in the decimal number system, to perform arithmetic operations you need to know the addition (subtraction) and multiplication tables.

Addition, subtraction and multiplication table for the binary number system

Adding binary numbers

Addition in the binary number system follows the same rules as in the decimal number system. Two numbers are written in a column aligned with the separator of the integer and fractional parts and, if necessary, supplemented on the right with insignificant zeros. Addition starts from the rightmost digit. Two lower-order units are combined into a higher-order unit.

Example: 1011,1 2 + 1010,11 2

The situation is also interesting when more than two numbers are added. In this case, transfer through several digits is possible.
Example: 111,1 2 + 111 2 + 101,1 2

When adding in the ones place (bit 0), there are 4 ones, which, when combined, give 100 2 . Therefore, from the zero digit to the first digit it is transferred 0 , and in the second - 1 .
A similar situation arises in the second digit, where, taking into account the two transferred units, the number is obtained 5 = 101 2 . 1 remains in the second category, 0 transferred to the third and 1 transferred to the fourth.

Subtracting Binary Numbers

In cases where a unit of the senior category is engaged, it gives two units of the junior category. If a unit is studied after several categories, then it gives one unit in all intermediate zero categories and two units in the category for which it was studied.
Example: 10110,01 2 — 1001,1 2

Arithmetic operations in all positional number systems are performed according to the same rules that are well known to you.

Addition. Let's consider adding numbers in the binary number system. It is based on a table for adding single-digit binary numbers :

It is important to pay attention to the fact that when adding two ones, the digit overflows and is transferred to the most significant digit. A digit overflow occurs when the value of the number in it becomes equal to or greater than the base.

The addition of multi-bit binary numbers occurs in accordance with the above addition table, taking into account possible transfers from low-order to high-order digits.

As an example, let's add the binary numbers 110 2 and 11 2 into a column :

Let's check the correctness of the calculations by adding in the decimal number system. Let's convert binary numbers to the decimal number system and then add them:

110 2 =1*2 2 + 1*2 1 + 0*2 0 = 6 10 ;

11 2 = 1*2 1 + 1*2 0 = 3 10 ;

6 10 + 3 10 = 9 10 .

Now let's convert the result of binary addition to a decimal number:

1001 2 = 1*2 3 +0*2 2 + 0*2 1 + 1*2 0 = 9 10 /

Let's compare the results - the addition was performed correctly.

Subtraction. Let's look at subtracting binary numbers. It is based on a table for subtracting single-digit binary numbers. When subtracting a larger number (1) from a smaller number (0), a loan is made from the highest digit. In the table, the loan is designated 1 with a line:

Subtraction of multi-bit binary numbers occurs in accordance with the above subtraction table, taking into account possible borrowings from the most significant bits. As an example, let's subtract the binary numbers 110 2 and 11 2:

Multiplication. Multiplication is based on the multiplication table for single-digit binary numbers:

Multiplication of multi-digit binary numbers occurs in accordance with the above multiplication table according to the usual scheme used in the decimal number system with sequential multiplication of the multiplicand by the digits of the multiplier. As an example, let's multiply binary numbers and:

Division. The division operation is performed using an algorithm similar to the algorithm for performing the division operation in the decimal number system. As an example, let's divide the binary number 110 2 and 11 2: