Problem
I wrote this method that adds two integers in the form of strings together. This way I can add large integers without overflowing.
How efficient is the code that I wrote? I am by no means a great coder, but I would consider myself somewhat decent. Is there anyway that would make it better?
I am a self taught coder and have only been doing it for about a year, so please be easy on me.
static string addString(string num1, string num2) {
string retVal = null, cNum1 = null, cNum2 = null;
int bf1 = 0, bf2 = 0;
if (num1.Length > num2.Length) {
for (int i = 0; i < (num1.Length - num2.Length); i++) {
cNum2 += "0";
}
} else if (num1.Length < num2.Length) {
for (int i = 0; i < (num2.Length - num1.Length); i++) {
cNum1 += "0";
}
}
cNum1 += num1;
cNum2 += num2;
char[] cAN1 = cNum1.ToCharArray();
Array.Reverse(cAN1);
cNum1 = new string(cAN1);
char[] cAN2 = cNum2.ToCharArray();
Array.Reverse(cAN2);
cNum2 = new string(cAN2);
for (int i = 0; i < cNum1.Length; i++) {
bf2 = bf1 + int.Parse(cNum1.Substring(i, 1)) + int.Parse(cNum2.Substring(i, 1));
if (bf2 > 9) {
retVal += bf2.ToString().Substring(bf2.ToString().Length - 1, 1);
bf1 = int.Parse(bf2.ToString().Substring(0, bf2.ToString().Length - 1));
} else {
retVal += bf2.ToString();
bf1 = 0;
}
}
if (bf1 != 0) {
retVal += bf1.ToString();
}
char[] ret1 = retVal.ToCharArray();
Array.Reverse(ret1);
retVal = new string(ret1);
return retVal;
}
Solution
Some style comments
- Add vertical spaces to group code which logically belongs together.
- Don’t declare multiple variables on the same line.
- Name your variables as meaningfully as possible. Names like
bf1won’t tell Bob the maintainer what it is about, making it harder to maintain the code. - methods should be named using
PascalCasecasing. See: C# naming guidelines - Usually a C# developer would expect one to use the Allman indention style; i.e. place the opening brace on the next line.
- Always add a scope specifier (access modifier) to methods and variables.
This method is violating the Single responsibility principle. It is just doing too much like normalizing the given input, adding the numeric values of the chars and constructing the result.
Let us take a look at what you are doing to normalize the string
string cNum1 = null;
string cNum2 = null;
if (num1.Length > num2.Length) {
for (int i = 0; i < (num1.Length - num2.Length); i++) {
cNum2 += "0";
}
} else if (num1.Length < num2.Length) {
for (int i = 0; i < (num2.Length - num1.Length); i++) {
cNum1 += "0";
}
}
cNum1 += num1;
cNum2 += num2;
Each time you call cNum1 += "0" or cNum2 += "0" you are creating a new string. By using the PadLeft() method together with Math.Max() and extracting the the normalization to a separate method your code will look cleaner.
private static string NormalizeValue(string value, int maxLength)
{
return value.PadLeft(maxLength, '0');
}
This has also the advantage that you won’t need cNum1 and cNum2 anymore.
static string addString(string num1, string num2) {
int maxLength = Math.Max(num1.Length, num2.Length);
num1 = NormalizeValue(num1, maxLength);
num2 = NormalizeValue(num2, maxLength);
.....
}
If you start the for loop at maxLength - 1 and decrement the index you won’t need the reversing of the char arrays anymore.
Using a StringBuilder to add the results of the single additions will result in fewer created strings.
If you are sure that the passed in strings only contain digits you can use a neat little trick. You can subtract a char ‘0’ from the current char like e.g
Assume first = '2' and second = '4' are the chars currently be processed.
int result = first - '0' + second - '0';
this boils down to
int result = '2' - '0' + '4' - '0' ;
and is subtracting the ASCII values of the chars
int result = 50 - 48 - 52 - 48;
so there is no need to call int.Parse() anymore. By extracting the two uses of ‘0’ to a const this will be beautified.
const int doubleZeroValue = 96;
int result = first + second - doubleZeroValue;
This will lead to
private static string NormalizeValue(string value, int maxLength)
{
return value.PadLeft(maxLength, '0');
}
private static string AddString(string firstNumber, string secondNumber)
{
const int doubleZeroValue = 96;
int maxLength = Math.Max(firstNumber.Length, secondNumber.Length);
firstNumber = NormalizeValue(firstNumber, maxLength);
secondNumber = NormalizeValue(secondNumber, maxLength);
StringBuilder sb = new StringBuilder(maxLength + 1);
int result = 0;
for (int i = maxLength - 1; i >= 0; i--)
{
result += firstNumber[i] + secondNumber[i] - doubleZeroValue;
if (result < 10)
{
sb.Append(result);
result = 0;
continue;
}
sb.Append(result - 10);
result /= 10;
}
if (result > 0)
{
sb.Append(result);
}
char[] resultDigits = sb.ToString().ToCharArray();
Array.Reverse(resultDigits);
return new string(resultDigits);
}
It still has some magic numbers in it like
sb.Append(result - 10);
result /= 10;
which could/should be extracted to meaningful constants but I couldn’t come up with the names lacking enough english.
What about simply using the built in BigInteger?
using System.Numerics;
using System;
public class Program
{
public static void Main()
{
BigInteger num1 = BigInteger.Parse("112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123");
BigInteger num2 = BigInteger.Parse("321112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123");
BigInteger sum = num1 + num2;
Console.WriteLine(sum);
}
}
Well i think you solution is not that good because you are working very hard with string and working with string is very slow (compared to calculations with integer).
So and what’s about the code maintainability? It is not that good too, because you can read that code only very hard (which also is because of that decent code readability @Heslacher spoke about in his answer). But the main aspect is the fact that you work with strings. as a code reader without debugger you will have a very hard time reading and understanding your code.
What is a good Solution for this problem?
The first thing i would always do is to create a class! I called mine BigInt
class BigInt
{
public List<int> Integer { get; set; }
public BigInt(string number)
{
this.Integer = this.CalculateBigInteger(number);
}
public BigInt(List<int> list)
{
this.Integer = list;
}
private List<int> CalculateBigInteger(string number)
{
return number.Reverse()
.Select(chararcter =>int.Parse(chararcter.ToString()))
.ToList();
}
}
With this code i am able to read the string into an int with — yeah nearly — infinite length.
Now we implement the add function which is the hardest parts and wich took me 2 and a half try:
The problems:
- One Number may be longer than the other one
- you need to add from the back (this is covered in the code snipped above)
- you have carryover(when you have 8 + 4 you have 12 so your add-result is 2 and your carryover is 1)
The add method:
public static BigInt Add(BigInt int_1, BigInt int_2)
{
var result = new List<int>();
int carryOver = 0;
IEnumerator<int> enumerator_1 = int_1.Integer.GetEnumerator();
IEnumerator<int> enumerator_2 = int_2.Integer.GetEnumerator();
enumerator_1.MoveNext();
enumerator_2.MoveNext();
bool hasNext_1 = true;
bool hasNext_2 = true;
while (hasNext_1 || hasNext_2)
{
var value = NumberAdd(enumerator_1.Current, enumerator_2.Current, ref carryOver);
result.Add(value);
hasNext_1 = enumerator_1.MoveNext();
hasNext_2 = enumerator_2.MoveNext();
}
if (carryOver != 0)
{
result.Add(carryOver);
}
return new BigInt(result);
}
I iterate over my two integer lists with an enumerator. when the enumerator has no more elements enumerator.MoveNext() return false, but if you call enumerator.Current it will also return 0 which is pretty nice, because enumerator1.Current + enumerator2.Current is enumerator1.Current when enumerator2 has no more elements.
I also added these small helper method to make the code better readable:
private static int NumberAdd(int value_1, int value_2, ref int carryOver)
{
var addResult = value_1 + value_2 + carryOver;
carryOver = addResult / 10;
var addValue = addResult % 10;
return addValue;
}
the ref word means that this variable is referenced. that means when you change the value it is also changed in the calling scope. otherwise the change would be garbage collected because an integer is call by value and not call by reference. in other words: ref makes this integer call by reference.
Print the result:
This code is nearly 1:1 copied from SO:
public string ToString()
{
StringBuilder sb = new StringBuilder();
foreach (var number in this.Integer)
{
sb.Append(number.ToString());
}
var reverseString = sb.ToString().ToCharArray();
Array.Reverse(reverseString);
return new string(reverseString);
}
Usage:
static void Main(string[] args)
{
var bigInt_1 = new BigInt("1346876136548");
var bigInt_2 = new BigInt("984651484651484654");
var result = BigInt.Add(bigInt_1, bigInt_2);
Console.WriteLine(result.ToString());
Console.ReadKey();
}
i create 2 objects of BigInt with the Constructor passing the big values as a string. The Result is:
984652831527621202
Advices:
- Try to get clear about the problem
- Find good data structures to solve your problem — this is most of the time one or even more new classes and in my case the data structure list (a dynamic data structure)
-
Try to program as clear as possible — always think about someone other is reading your code and ask yourself the question: is he able to understand your code without a book of comments? if no, try to code it again and better. i also coded this example 3 times because i was not happy about my code even if the code worked
Very interesting topic. i asked me this a bunch of time what is a good solution to work with bigger values than an
integer/longcan hold. But please see that this solution has very very bad memory handle. For one number from 0-9 you allocate memory of the with of one integer. if you have problems with memory you should use byte or need another even much better solution!
If you have questions or other things you want to talk about, i’d would be happy to answer you