An arbitrary natural number can be represented in the only way as a sum of powers of two, for example 23 = 16+4+2+1. By denoting the powers of two included in this sum by ones, and those not included in its powers by zeros, we can briefly denote this sum by a Boolean set (in other terminology, a vector) (10111) 2. Index 2 reminds you that the number is written in binary system. A one in the least significant (leftmost) digit means the term 1, a one in the second digit from the left means 2, a one in the third digit means 4, a zero in the fourth digit means the absence of term 8, a one in the fourth (most significant) digit means the presence term 16 (in most cases it is reasonable to consider only those records of numbers in the binary system in which the most significant digit is one).
The main advantage of the binary system (besides the naturalness of its use in electronic digital technology) is the exceptional simplicity of the algorithms for arithmetic operations in it. The multiplication table in the binary system does not require memorization at all: any number multiplied by zero gives zero, and multiplied by one is equal to itself. The division rule is reduced to two equalities 0/1 = 0, 1/1 =1, due to which division by a column in the binary system is simpler than in the decimal system, and essentially reduces to repeated subtraction. The addition table in the binary system is a little more complicated than the multiplication table (unlike the decimal system), since 1+1 = (10) 2 and a carry occurs to the next digit.
The rule for adding two bits in a binary system is given by the formulas x+y = 2v+u, v = x&y, u = xÅy. Due to symmetry, to check them it is enough to consider not four, but three cases: 0+0 = (00) 2, 1+0=0+1= (01) 2, 1+1 = (10) 2. The circuit that performs this addition is called a half adder (in English literature: half adder) and is usually designated HA or FA2. This circuit (in the basis (AND, XOR)) is shown in the figure.
Circuits for arithmetic operations on multi-bit binary numbers. The addition of two n-bit binary numbers (x n,....,x 1) 2 and (y n,....,y 1) 2, as in the decimal system, leads to the appearance of carries to the next digit, which must be taken into account in the calculation. These carries are also equal to zero or one (if the carry is zero, then in a manual calculation it is not actually performed, but the logic circuit must work correctly in this case, because it “does not know” which carry came from the previous digit). Let us denote the transfer from the (i-1)th digit to the next i-th rank through w i (w 1 =0, because in this case there is simply no previous digit). Then to calculate z i (i-th bit of the result), you need to add the bits x i and y i and the carry bit w i . We perform this addition using the formulas
x i + y i +w i = 2v i +u i , v i =m(x i ,y i ,w i), u i =l(x i ,y i ,w i)
using the FA3 circuit. Then z i =u i =l(x i,y i,w i), and the next carry bit w i +1 = v i =m(x i,y i,w i). When adding n-bit numbers, generally speaking, an n+1-bit number is obtained. Its most significant bit z n +1 = w n +1 is equal to the last carry.
The diagram for adding three-digit numbers is shown in the following figure. The scheme for adding n-bit numbers looks similar.
The complexity of the specified n-bit adder is 5n-3. N.P. Redkin proved that adders for n-bit numbers of less complexity in the basis (AND,OR,XOR,NOT) do not exist. The constructed adder is therefore a minimal circuit. But this scheme has a significant drawback - it has great depth. The depth of a circuit is the maximum number of its elements that form a circuit connecting any of the circuit’s inputs to one of its outputs. For example, the depth of the above FA3 circuit is 3.
Circuit depth - not less important characteristic circuit than its complexity. The complexity of the logic circuit largely determines the area of the corresponding actual circuit located on the silicon chip. The depth of the logic circuit largely determines the delay of the real circuit, i.e. the time during which the signal travels from the inputs of the circuit to its outputs, in other words, the time that must pass after stabilization of any values at the inputs of the circuit until the moment when certain logical values are also stabilized at all outputs of the circuit. Circuit complexity is often not a significant issue since modern technology allows very large circuits to be placed on a chip. And minimizing the circuit delay is very important, since the delay of the combinational part of the multi-cycle circuit determines it clock frequency- the lower the delay, the higher the frequency.
Theoretically, calculating the latency of a real circuit is very difficult. There are usually quite a few circuits of circuit elements connecting its inputs to outputs (these circuits are also called paths), and the delay of the circuit is determined by the delay along the worst path in a certain sense, which is called critical. For example, in diagram FA3, the critical path probably connects inputs X or Y to output m. The delay along any path is determined not only by the sum of the delays of all elements lying on this path (in the example given it is equal to 3, if we consider the delay of each element to be single). The delay of the wires connecting these elements should also be taken into account. The delay of an element depends on which of its inputs and which of its outputs it is measured, as well as on electrical characteristics the element itself and the elements directly connected to it in the circuit under consideration, it depends on the temperature of the circuit and even on what logical values are supplied at the moment in question to the inputs of this element and whether (and in what direction) the value at its output changes. However, although not very precisely, the delay of a path can be estimated as the sum of the delays of its elements. If the delays of all elements are equal, then this value is determined by the depth of the circuit. Of course, the concept of circuit depth can be expanded by admitting that elements of the basis can have arbitrary non-negative delays.
The depth of the above n-bit adder circuit at first glance is 3n-2. But a careful analysis of possible critical paths shows that it is actually equal to 2n-1. All the same, this is a lot and a real circuit constructed in this way will have long delay. In practice, circuits are used that have both low complexity, not exceeding Cn (where C is a small constant) and low depth, approximately equal to 2log 2 n. V.M. Khrapchenko in 1970 constructed a scheme of low complexity and depth, asymptotically equal to log 2 n (i.e. equal to (1+ e(n)) log 2 n, where e(n) tends to zero as n increases). He recently proved that the depth of the adder cannot be less than log 2 n + log 2 n (log 2 (log 2 n))). Therefore, the scheme he constructed has an asymptotically minimal depth. However, Khrapchenko's scheme outperforms conventional schemes only for n of the order of a thousand. Nevertheless, there is some modification of his scheme with a depth approximately equal to log j n, where j = (Ö5+1)/2, and this scheme has a depth less than standard schemes, already starting from n = 8. In 2008, M. I. Grinchuk constructed a circuit of depth no greater than log 2 n+log 2 (log 2 n)+6, which even for small n has a smaller depth than all known circuits.
The problem of constructing optimal circuits for multiplying n-bit numbers turned out to be even more difficult than the problem of constructing optimal adders. It is easy to build a circuit for multiplying n-bit numbers in the basis (OR,AND,XOR,NOT) of complexity approximately equal to 6n 2. To do this, you can use the above circuit for the adder. However, its depth will be great. In the early 60s, several researchers (in the USSR Stolyarov and Ofman, in the USA Avicenis and Wallace) independently constructed a scheme for multiplying complexity of order n 2 and depth of order log 2 n. In terms of depth, these circuits are optimal in order, but the problem of constructing a circuit for multiplying an asymptotically minimal depth still remains unsolved. In terms of complexity, these schemes turned out to be far from optimal. A. A. Karatsuba built in 1962 a circuit for multiplication with an order complexity no greater than n 1.6, then A. L. Toom built a circuit with complexity n 1+ e(n), where e(n) tends to zero with increasing n. In a certain sense, this result is final, however, it was refined at the turn of the 70s by the German mathematicians A. Schönhage and F. Strassen, who obtained for multiplication circuits an upper bound for the complexity of an order not exceeding n log 2 n log 2 (log 2 n), and in 2008 this estimate was improved by the American mathematician M. Fuhrer, who replaced the double logarithm with an extremely slowly growing function. There is an assumption that the complexity of the multiplication circuit in order is not less than n log 2 n, but this has not been proven.
The American mathematician S. Cook proved that it is possible to construct a circuit for dividing a 2n-bit number by an n-bit number, whose order complexity does not exceed the complexity of multiplying n-bit numbers. It is also known that the lower bound for the complexity of the circuit for order division is not less than the lower bound for the complexity of multiplication. Therefore, in terms of complexity estimates, division is nothing new compared to multiplication. However, for a long time the best estimate of the depth of division by order was (log 2 n) 2 .
Subsequently, circuits for division with a depth of order equal to log 2 n were found, but their complexity turned out to be great. The Americans Reif and Tate built schemes for dividing depth in order not exceeding log 2 n log 2 (log 2 n) and at the same time complexity in order not exceeding n log 2 n log 2 log 2 n, however, these schemes, like the Schönhage schemes, Strassen and Fuhrer have not yet found practical applications, since in reality they begin to outperform the schemes used in practice only for huge values of n.
Recommended reading
- ABOUT. Lupanov “Asymptotic estimates of the complexity of control systems” ed. Moscow State University, 1984.
- ABOUT. Lupanov “Lecture notes on mathematical logic” ed. Moscow State University, 2009.
- J. Savage “Computational Complexity” M. ed. Factorial, 1998.
- D. Knuth “The Art of Computer Programming”, vol. 2, ed. Williams, 2000.
- S.B. Gashkov “Number systems and their applications”, M. ed. MCNMO, 2004.
- S.B. Gashkov, V.N. Chubarikov “Arithmetic. Algorithms. Computational Complexity,” ed. Bustard, 2005.
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.
A 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 to do this.) 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 when dividing a NUMBER 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-digits 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.
- Digit number = 1
- If 2 -K > A
Then we add zero to the binary number
- add 1 to the binary number
- A = A - 2 -K
- K = K + 1
- 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 is a number in additional code It’s extremely simple, we take a number, replace zeros with ones, replace 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. 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. Let us 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 in such a way that the mass of these 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 a general method for 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); (1, 0, 0); (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 do not appear very often in the series of natural numbers. 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, using not even a very large number 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:
- It is easy to see that the final binary number includes all remainders and last step and remainder and quotient.
- The quotient is written before the remainder.
- 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 points included in it are separated by a dot. intermediate results.
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 |
||
Arithmetic operations on binary numbers are performed using an algorithm called column addition. The rules for performing arithmetic operations on binary numbers are given by tables of binary addition, subtraction and multiplication (Table 1.31).
Table 1.31. Arithmetic operations on binary numbers
Example 1.60. Add the numbers 55.25 and 19.5 in decimal and binary number systems.
First term 55, 25 1 1 0 1 1 1.0 1
Second term 19, 50 1 0 0 1 1.1 0
The resulting extra bit is called carry bit.
Example 1.61. Add the numbers 65 and 42 in the binary number system.
- 65 10 = 01000001 2 .
- 42 10 = 00101010 2 .
Let's add these numbers:
01000001 First term
00101010 Second term 01101011 Result
You can verify that (01101011) 2 = (107) 10:
0 2 7 + 1 2 6 + 1 2 5 + 0 2 4 + 1 -2 3 + 0-2 2 + 1 -2" + 1 -2° = = 64 + 32 + 8 + 2+ 1 = 107.
Example 1.62. Perform binary addition X And U. a) X= 1101; Y= 101.
|
X+Y = |
Result. 1101 + 101 = 10010. b)X= 1101; Y= 101; 7= 111.
x+y+g= 110 0 1
Note. Subtracting numbers in the binary number system is performed in the same way as in the decimal number system. If necessary, a unit from the next highest digit is occupied, and the occupied unit is equal to two units of this digit. A unit is borrowed each time a digit is in the subtracted digit. more numbers in the same category of the minuend. To perform a subtraction operation, it is replaced by addition, and the inverted (opposite) number is taken as the second addend. For example, suppose you need to perform a subtraction: 65 - 42. Let's replace it with addition: 65 + (-42).
And so, we already know what the binary number system is. The binary system is the same full-fledged number system as the decimal system, which is familiar to all of us. In the binary system, as in any other number system, all arithmetic operations that we are accustomed to in the decimal system are possible. That is, addition, subtraction, multiplication, division. Let's look at each of the arithmetic operations using specific examples.
Addition
Let's say we need to find the sum of two binary numbers: 10011001110 + 11000101110. How to do this. The rules for adding binary numbers are the same as for decimal numbers. The only difference is that each digit of the sum can take only two values - zero or one. In the same way as in the decimal system, to add numbers it is convenient to write them in a column:
| + | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | ||
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | |
Numbers must be added bit by bit, starting with the least significant digit. In this case, the following rule applies: Zero plus zero will result, naturally zero. One plus zero and zero plus one result in one. When adding two ones, we get a zero in the current digit and a unit carried to the most significant digit. When adding three units (taking into account the carryover unit from the previous digit), we obtain a unit in the current digit and a carryover unit. These rules are combined in the so-called addition table:
Using the addition table, check the addition example above. Try adding some numbers yourself.
Multiplication
Multiplying binary numbers is also similar to multiplying decimal numbers. Now we will also show this process with an example. Remember how you multiply two decimal numbers side by side. Here is an example of multiplying binary numbers by a column:
| X | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | |||
| 1 | 0 | 1 | 1 | |||||||||||
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | ||||
| + | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | |||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | ||||
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | |
In the same way as when multiplying binary numbers, we multiply the first number by each digit of the second and write the results obtained under the first line, one under the other with a shift. Then we add the obtained intermediate results taking into account the shift. However, in the case of binary numbers there is one significant difference. Since any digit of a binary number is either zero or one, intermediate multiplication is greatly facilitated. In fact, any number multiplied by one is equal to itself. Any number multiplied by zero is equal to zero! Therefore, there is no need to calculate anything here. This is why multiplying two binary numbers is reduced to the operations of shift and addition. This is very important for building computers. Now it is clear that we do not need any “multipliers”. To implement addition and multiplication operations, we only need adders and shift registers. You can get acquainted with their device on our website.
Subtraction
In order to simplify the subtraction operation, the so-called “additional code” was invented. We can say that negative numbers are written using this code. In order to write a binary number in two's complement code, you need to invert all its digits and then add one. Inverting a bit of a binary number means replacing its contents with the opposite. (Zero is one, and one is zero). The table below shows examples of converting various numbers into additional code. In each row of the table you see the same number written first in the decimal system, then in the binary system in direct code, then inverted direct code, and then in complementary code.
Read the rules for converting numbers from decimal to binary in the “Number Systems” section.
The rule for subtracting two binary numbers is:
in order to subtract one number from the second, you need:
- Convert the subtrahend into complementary code.
- Add these two numbers (minuend and subtrahend in two's complement).
- When adding, do not take into account the carry from the most significant digit.
- The result obtained is the difference.
Let's explain this with an example. Let's say we need to find the difference between the numbers 13 and 5 in binary. Let's first convert the required numbers into the binary system:
We take the number 13 in direct binary code (00001101).
The number 5 is converted to complementary binary code 5 (11111011).
Now we do the addition:
| + | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | ||
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
We discard the transfer from the highest digit we use. The result is 1000.
To check, let's convert the result to decimal form. 1000 in binary is 8 in decimal. I advise you to carefully check the example given in accordance with the addition table (see above).
Multiplying and dividing by 2
Multiplying by 2 (by 10 in binary) is a special case of multiplication. But it should be considered separately. The fact is that just as when multiplying by 10 in the decimal system you just need to add one zero to the end of the number, so when multiplying by two in the binary system, to get the result you need to shift the multiplicand one place to the left and add one zero to the low order.| Binary | Decimal |
Division by 2 occurs in the same way. Only in reverse. In order to divide a binary number by 2 (binary 10), you simply need to discard the zero in the least significant digit of the number and shift all other digits one digit to the right. If the least significant digit of the desired number is not zero, but one, then this means that the number is not divisible by two. In this case, division with a remainder is possible.
Note: You can practice multiplying by two with other numbers yourself. For information about converting numbers from decimal to binary, see here.
Division by an arbitrary number
Let's remember how we divide one number by another in the decimal system. I mean division by column or angle. Division occurs in the same way in the binary system. Here is an example of dividing two binary numbers:
First we write down the dividend. In this case, the number is 1000001 (65 in decimal). Then, to the right of it, draw a corner. Write the divisor at the top of the corner. In our case it is 101 (decimal 5). Then we begin to find the quotient by bit value. In the decimal system, in this case we select which number from 1 to 9 the divisor should be multiplied by, so that the result would still be less than the first three digits of the dividend. If such a number is not found, then take the first four digits of the dividend. In the binary system, any digit can take only two values - zero or one. Therefore, we have much less choice. The divisor can only be multiplied by 1 or zero. Moreover, in the first case it will remain unchanged, and in the second it will be equal to zero. We will only have to check whether the divisor is greater than the number that makes up the first three digits of the dividend. As you can see, the first three digits make up the number 100, which is less than 101. Therefore, we take the first four digits of the dividend. The number that makes up the first four digits of the dividend (1000) is naturally greater than the divisor. Therefore, we write the divisor under the first four digits of the dividend and subtract these two numbers. We get the difference 11. We write 1 in the first digit of the quotient.
We find the next category of the quotient. To do this, we remove the next digit of the dividend (in the same way as is done when dividing in the decimal system). We check whether it is now possible to subtract 101 from it. The number 110 is greater than 101. Therefore, we write one in the next digit of the quotient and subtract these two numbers. The difference is 1.
Next, we look for the third rank of the quotient. We remove another zero from the next digit of the dividend. But it is impossible to subtract 101 from the number 10. 10 is less than 101. Therefore, we write zero in the next digit of the quotient and remove the last digit of the dividend. Subtraction is now possible. Moreover, the result of subtraction is zero. This means, firstly, that the last digit of the quotient is equal to one, and secondly, that the number 1000001 is divided by 101 without a remainder. The result of division is 1101 (decimal 13).
Conclusion
You may be wondering what practical value there is in knowing the rules of binary arithmetic. It is much more convenient to count in decimal form. Yes, for humans it is more convenient in decimal. But it was these very rules that made it possible to create electronic circuits, capable of performing calculations automatically. If you look closely at the rules for dividing numbers, you can see that all these actions come down to shifting the digits of a number and subtraction. Subtraction, as we have seen earlier, comes down to adding numbers, one of which is represented in two's complement code. The adder is easily built based on the simplest logic elements. The shift is performed using a shift register. On the pages of this site you will find a description of all these elements of computing systems.
, Competition "Presentation for the lesson"
Presentation for the lesson
Back Forward
Attention! Slide previews are for informational purposes only and may not represent all of the presentation's features. If you are interested this work, please download the full version.
Lesson objectives: (slide 2)
- Introduce students to the binary number system.
- Develop skills in performing arithmetic operations with binary numbers
Lesson progress
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:
- 110010+11,01
- 1111001-1101
- 10101,1*11
- 10101110:101
