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

This article introduces the relevant knowledge of "what is the addition, subtraction, multiplication and division of large numbers". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Large number addition

Large number addition is the simplest, simple simulation can be done. First of all, let's think about the process of adding two numbers: from right to left to calculate the sum, carry, and all the way to the end.

The process of bit-by-bit addition from right to left is also simulated in programming languages, but some details need to be paid attention to in the implementation.

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

2, calculate from right to left, you can put the results into an array to form a string, or you can use StringBuider splicing, and finally reverse the order when stitching.

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

4. At the end of the calculation, we have to see whether the remainder is 1, if it is 1, we need to add it to the result, for example, "991" + "11" calculates that the three positions are 002, but there is a remainder that needs to be added, so it should be 1002.

An addition process

Of course, there are many ways to implement it, you can first reverse the string and then calculate it from the back. Of course, what I implement here is that the string is calculated from the back to the front of each bit, and then the result order is added to the StringBuilder.

In this question, you can test your own code by adding two numbers to [415]. The implementation code is as follows:

Public String addStrings (String num1, String num2) {/ / official account: bigsai welcomes your interest int len1=num1.length ()-1 Magneto Len2num2.length ()-1; char ch2 [] = num1.toCharArray (); char ch3 [] = num2.toCharArray (); StringBuilder sb=new StringBuilder (); int remainder = 0tramp / calculated remainder while (len1 > = 0 | len2 > = 0) {int n1=len1 > = 0? (ch2 [len1--] -'0'): 0 Int n2=len2 > = 0? (ch3 [len2--] -'0'): 0; whether the corresponding numeric remainder=num/10;// of int num=n1+n2+remainder;// sum carries sb.append (num); / / whether it is added to the result string} if (remainder > 0) / / whether carry {sb.append (remainder) is still required } / / reverse loading is the result return sb.reverse (). ToString ();} large number subtraction

Addition corresponds to subtraction. With the above idea of large number addition, I think you should also have some ideas in large number subtraction, but the difference between subtraction and addition is that subtraction has a position. Addition needs carry and subtraction needs to be borrowed. And large integer positive subtraction may not produce positive or negative.

Two positive numbers, if the large number minus the decimal, then everything is normal, the result is a positive number; but if the decimal minus the large number, then the result will be a negative number, and the result is more troublesome to deal with. So here all turn to big-small processing (big-small does not exist can not borrow the situation).

Subtraction turns to big-small

1. Compare the size of num1 and num2 before performing the calculation. If num1 > num2, then simulate the process of num1-num2. If num1

2, when comparing the size of two numbers, because it is in character form, first compare the length of the two strings, the longer one is larger and the shorter one is smaller, if the two strings are of the same size, then you can compare them in lexicographical order (Java can directly use the compareTo method).

3. Unlike addition, there may be several prefixes of zeros before subtraction, which you need to remove. For example, if the result calculated by "1100"-"1000" is "0100", you have to remove the previous zero and return to "0100".

4. The specific implementation is similar to addition. If you use StringBuilder storage, you need to reverse the order. If it is a negative number, add'- 'before it.

5, each position carries on the subtraction operation normally, if the value is less than 0, then needs to borrow upward (+ 10), then processing the last bit to carry on the subtraction also needs to deal with the borrowing.

An approximate process of subtraction

There is no original title in this question, but you can verify the correctness of your code on Xiaomi OJ [large subtraction]. The specific code is as follows:

Public static boolean compare (String num1,String num2) {if (num1.length () num2.length ()) return true; else return num1.compareTo (num2) > 0;} 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 item0) Return sBuilder.toString 0) {sBuilder.append (value [index -]);} index ();} large number division

Large number addition, subtraction and multiplication are done through simulation, but large number division is also achieved through simulation?

No, for the large number a _ b, the most general requirement is to get its integer solution or remainder, that is, a/b=c. D, that is, there are c b in a, and d is left. The core is to find out what c is first. For programs, you can change division into subtraction by enumerating, and keep subtracting d from a until it can't be subtracted.

Conversion from division to subtraction

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

Then it is necessary to speed up the search and reduce the number of subtraction. One of the best ways to reduce the number of subtraction is to expand the divisor b. If b is followed by a '0partial, then the result is multiplied by 10, and the number of subtractions becomes 1/10. According to this idea, we can always find the maximum multiple of 10 of b (less than a), calculate the number of subtractions and convert them into the total number of words minus b, keep the result as a string, and then iterate until the end. Although this is a division problem, it also contains subtraction and addition (the number of times is added to the result).

Computing thought

Of course, it is also possible for some people to use dichotomy to compress the number of times that can be reduced (addition can iterate numbers to achieve dichotomous multiples). But the amount of code may be more, so the general interview written test will not let you write on the spot, so you can master the previous subtraction, subtraction, multiplication code.

I will also briefly give you this part of the code (other functions will not be repeated if they have been pasted on it):

/ / suppose num1 > num2 public static String divideString (String num1,String num2) {String value= "0"; / / result while (compare (num1,num2)) {StringBuilder sbTeam=new StringBuilder (num2); / / use this to add zeros and num to subtract StringBuilder sbCount=new StringBuilder ("1"); / / the number of times may be very large int subLen=num1.length ()-num2.length () / / A few zeros should be added to the statistics (int item0 / for 3) + (5-> 6-> 4)

Output: 7-> 8-> 0-> 7

Unlike the above, the linked list is not inverted, but the addition operation actually needs to start from the last face, that is, in theory, it should start from the end of the linked list, but this is a single linked list, so the time complexity of the operation is too high. so we have to use space for time: stack to solve.

The nodes of the linked list are placed in two stacks in turn, and then the two stacks are counted at the same time. However, the list to be returned is a linked list, so you can insert it by header (if you don't insert it, you can reverse it at last). For more information, please see the figure below:

Logic

The implementation code is:

/ / A more concise way to write ublic ListNode addTwoNumbers (ListNode L1, ListNode L2) {ListNode node=new ListNode (0); ListNode team=node; int jin=0;// carry while (L1 carry null | | L2 carry null) {int num=jin; if (L1 empty null) {num+=l1.val;l1=l1.next;} if (L2 carry null) {num+=l2.val;l2=l2.next;} jin=num/10; num%=10; team.next=new ListNode (num) Team=team.next;} if (jinned numbers 0) team.next=new ListNode (jin); return node.next; "what is the addition, subtraction, multiplication and division of large numbers", thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.