Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to realize the addition, subtraction, multiplication and division of large numbers". The explanation in this article is simple and clear, easy to learn and understand. Please follow the ideas of Xiaobian to study and learn "how to realize the addition, subtraction, multiplication and division of large numbers" together.

You have classified brush questions small partners, may see a lot of people classified string, greedy, dynamic programming, bfs, dfs, large numbers, number theory, etc., first listen to large numbers, you may be different: large numbers are what? Sounds like a tall order.

Large numbers, in fact, are very large numbers (may far exceed 32,64 bits, the basic type can not be expressed) addition and subtraction, in Java we can use a large number class (BigInteger, etc.) is easy to solve the various operations of large numbers, but if you meet the interviewer he will definitely let you handwritten.

This number is generally expressed and returned in the form of a string, linked list, etc. The core of large number operation is: simulation, simulation of our daily paper pen calculation of the number of addition, subtraction, multiplication and division process, and then according to the characteristics of the computer, programming language and other appropriate storage calculation can be, however, large number division operation is a little special, and we directly simulate the way of thinking is slightly different.

addition of large numbers

Addition of large numbers is the simplest, simple simulation can be done. First, let's consider the flow of adding two numbers: summing, carrying, and ending from right to left.

In the programming language is also simulated from right to left bit-by-bit addition process, but in the specific implementation needs to pay attention to some details.

1. Enumerate character strings and convert them to char[] to improve efficiency

2. Calculate from right to left. You can put the results into an array and finally form a string. You can also use StringBuider to splice. When splicing, you should reverse the order.

3. The remainder needs to be cleared every time it is superimposed. If the sum of two numbers is greater than or equal to 10, there is a remainder. The number added to the position in the result should also be the result of the number.

4, the final calculation to see if the remainder is 1, if 1 needs to be added to the result, for example,"991"+"11" count three positions for 002 but there is still a remainder to add, so it should be 1002.

Of course, there are many ways to implement it. You can first invert the string and then calculate it from front to back. Of course, what I implemented here is to calculate the corresponding bits of the string from the back to the front, and then add the result sequence to StringBuilder.

This question can be checked in the force button [415 two numbers add], the implementation code is:

public String addStrings(String num1, String num2) {//public number: bigsai Welcome your attention int len1=num1.length()-1,len2=num2.length()-1; char ch2[]=num1.toCharArray(); char ch3[]=num2.toCharArray(); StringBuilder sb=new StringBuilder(); int remainder =0;//calculate remainder while (len1>=0||len2>=0) { int n1=len1>=0? (ch2[len1--]-'0'):0; int n2=len2>=0? (ch3[len2--]-'0'):0; int num=n1+n2+remainder;//sum corresponding numbers mainder =num/10;//whether carry sb.append(num);//add to result string } if(mainder>0)//whether carry is needed { sb.append(remainder); } //reverse installation is the result return sb.reverse().toString();} Subtract large numbers

Addition corresponds to subtraction. With the above realization idea of large number addition, then I think you should have some ideas in large number subtraction, but subtraction and addition are different in that subtraction has a position difference. Addition requires carry and subtraction requires borrowing. And large integer subtraction may produce positive or negative.

Two positive numbers, if the large minus the decimal, then everything is normal, the result is a positive number; but if the decimal minus the large, then the result will be a negative number, and the result is more troublesome to process. Therefore, all of them are converted into large-small processing here (large-small does not exist in the case of non-borrowing).

1. Compare the size of subtrahend (num1) and minuend (num2) before performing calculation. If num1>num2, then simulate the process of num1-num2. If num10;}public static String subtractString(String num1,String num2) { char sign='+';//Sign //Let num1>num2 if num1=0|| len2>=0) { int n1=len1>=0? (ch2[len1--]-'0'):0; int n2=len2>=0? (ch3[len2--]-'0'):0; int num=n1-n2-borrow; borrow=0; if(num=0;j--) { int index=a.length-1-i+b.length-1-j; value[index]+=(a[i]-'0')*(b[j]-'0'); } } for(int i=0;i=0) { sBuilder.append(value[index--]); } return sBuilder.toString();} Division of large numbers

So, big numbers, addition, subtraction, multiplication, simulation, but big numbers, division, simulation?

For a large number a/b, it is generally required to find its integer solution or remainder at most, that is, a/b=c…d (a,b,c,d are all integers); that is, there are c b in a, and d remains. The core is to find out how much c is first. For the program, you can change division into subtraction by enumerating ah, and continuously subtract d from a until it cannot be subtracted.

But there is a problem, if the dividend a is very large, there may be many b, then the time complexity is too high, it is impossible to execute so many times, so how do you need to optimize this method?

That is to speed up the search times, reduce the number of subtraction times, subtraction times to reduce a best solution is to expand the divisor b. If a zero is added to b, the result is multiplied by 10, and the number of subtractions becomes one-tenth. According to this idea, we can always find the maximum multiple of 10 of b (less than a) and calculate the number of subtractions and then convert it to the total number of words subtracted from b. The result should be kept as a string, and the iteration will continue until the end. Although this is a division problem, it also contains subtraction and addition (the number of times is added to the result).

Of course, there are also some people who use dichotomy to compress the number of times that can be reduced (addition can be iterated to achieve binary multiples), the specific implementation is not very difficult, but the code volume may be relatively large, so the general interview written test will not let you write on the spot, so master the subtraction, subtraction, multiplication code in front of it.

Thank you for reading, the above is the content of "how to realize the addition, subtraction, multiplication and division of large numbers." After studying this article, I believe everyone has a deeper understanding of how to realize the addition, subtraction, multiplication and division of large numbers. The specific use situation still needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.