Several people have asked how binary relates to base 10 in the LongLong example.
While this is only tangentially related to the material, it is worth understanding if you are curious. A few things to consider:
1)You definitely could use base 10 instead of base two. This will work for most cases. However, there will be a problem with really big numbers.
Suppose, to make the numbers smaller, that a long took up 7 bits. In other words, it had 7 binary digits. Let's also assume that the number is positive so we won't worry about negatives at all.
A 7 bit binary number has 2^7 -1 = 128 - 1 as it's maximal value. This is similar to have a 7 digit base 10 number would have value 10^7 - 1 = 9,999,999 as a maximal value. Remember, that because Java works in base 2 (binary) that the maximal value will *always* be 2^n - 1 for some n.
The problem with operating in base 10 will happen on the left most digit of each number. The problem is that *some* but not all, 3 digit base 10 numbers can fit into 7 bits. This means that when you set up you loop, you'll run into issues as you won't know whether to go for a total of 3 digits or 2 digits.
This will be a bit hard to demonstrate with a long, just because the numbers are bigger, but you can do the following. A long's maximum value is
9,223,372,036,854,775,807
This is 19 digits in base-10. This means that some 19 digit base 10 numbers fit into a long and other 19 digit base 10 numbers do not fit.
When you implement this code, you will probably have something like
for (int i=1; i <= 19; i++) OR for (int i=0; i <= 18; i++)
If you have done the first case, then you will have a "long overflow" problem when you put into secondPart a value this big for both LongLongs. The problem is at the step
total = total + (x+y)*10^(n-1) ---->with n = 19 here and x+y possibly bigger than 10, you can be too large.
If you have done the second case, then you'd be ignoring any values in the 19th (from the right) base 10 digit.
2)Why this avoids overflow error. This is a bit mathy btw......
In the program we overcome the integer overflow if it happens in the secondPart for the following reason:
At each step, all we do is take d1+d2+carry. We then take that result % 2 . What this does is ensure that when we write
total = total + (d1+d2+carry)%2 * 2^(n-1) --->at this step the value (d1 + d2 + carry) % 2 is always 0 or 1, so the resulting product is at most 2^(n-1) It turns out that because of this, the numbers will always be < 2^64. The reason is similar to what happens in base-10. The biggest possible n digit number in base 10 is having all 9's. It's value will be 10^(n+1) - 1. The biggest possible n-digit number in base 2 is having all 1s. It's value will be 2^(n+1) - 1
This means that total will be a result composed of:
1|0 * 2^(n-1) + 1|0 * 2^(n-1) + 1|0 * 2^(n-2) + ... 1|0 * 2^2 + 1|0 * 2 + 1|0 * 1
I have written 1|0 to mean it could either be 1 or 0. We know that the biggest this can be is if all the 1|0 are actually 1. This would leave us with
2^(n-1) + 2^(n-2) + 2^(n-3) + ...+4 + 2 + 1 . This actually sums up to be 2^n-1 which we know will fit into a long
If we *didn't* take the result %2, then this would be 2 or 3 in some cases. That could lead to cases where the sum is > 2^n-1
The advantage of using 2 numbers this way is that we can now take the carry bit from the addition of the secondParts and use it to help out in the firstPart addition. Again, this would be a bit complex in cases where you had a carry at the last stage if you were operating in base-10 instead of binary.