Add two number in any length, of any base from 0 to 36

mrnutty 0 703 Views

This code below add two positive numbers in any base from binary
to base 36 with any length allowed by memory. The snippet comes
with examples. There might be some bugs, because I haven't tested
extensively, so forgive me if you find bugs. Hope people find it useful
somehow. Thanks for reading.
--------------------------------------------------------------------------------------
Oh. Found a bug, after positing this post, of course,

For the isValidNum function the if statement inside the for loop should be this :

if( unsigned(toBaseInt(num[pos])) >= base ) return false;

the comparison needed to be >= instead of >. Sorry for the bug.

#include <iostream>
#include <string>
#include <sstream>
#include <cctype>
#include <list>

using namespace std;

/* adds two positive numbers of a positive base under 36*/
/* return "NULL" if either input is bad */
string add(const string& num1,const string& num2,const size_t& base);

/* check is a number is valid input in a given base */
bool isValidNum(const string& num,const size_t& base);

/* returns a copy of num, with no leading zeros */
string killLeadingZeros(const string& num);

/* appends zeros to front */
string addZerosToFront(const string& num, size_t howMany);

/* returns numerical value of char in base */
/* ex { '0' = 0 ... '9' = 9 } , {'A' = 10 ... 'Z' = 36 } */
int toBaseInt(const char c);

/* returns the char value of int in base */
/* ex{ 0 = '0'... 9 = '9'} , { 10 = 'A' ... 36 = 'Z'} */
char toBaseChar(const int i);
int main()
{
	string hex1 = "FFFF";
	string hex2 = "FFFF";
	string hexResult = add(hex1,hex2,16);

	string bin1 = "111";
	string bin2 = "101";
	string binResult = add(bin1,bin2,2);

	string dec1 = "1234567891017181920";
	string dec2 = "98765432123456789";
	string decResult = add(dec1,dec2,10);

	cout << hex1 << " + " << hex2 << " = " << hexResult << endl;
	cout << bin1 << " + " << bin2 << " = " << binResult << endl;
	cout << dec1 << " + " << dec2 << " = " << decResult << endl;


	return 0;
}

int toBaseInt(const char c){
	const string num = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";	
	return num.find(c);
}
char toBaseChar(const int i){
	const string num = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";	
	return num[i % num.size()];
}
bool isValidNum(const string& num,const size_t& base)
{
	const string bases = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";		
	// check if valid digit
	for(size_t pos = 0; pos != num.size(); ++pos){		
		if( unsigned(toBaseInt(num[pos])) > base ) return false;
	}
	return true;
}
string addZerosToFront(const string& num, size_t howMany){
	string str = string(num.size() + howMany,'0');
	for(int pos = howMany; pos != num.size()+ howMany; ++pos) 
		str[pos] = num[pos-howMany];
	return str;
}
string killLeadingZeros(const string& num){
	string str;
	/* quick check */
	if(num[0] != '0') return string(num);
	size_t pos = 1;
	while(num[pos] == '0') ++pos; 
	std::copy(num.begin()+pos,num.end(),std::back_insert_iterator<string>(str));
	return str;
}
string add(const string& num1,const string& num2, const size_t& base){
	if(!isValidNum(num1,base) || !isValidNum(num2,base) || base <= 0 || base > 36) 
		return "NULL";
	
	string topNum = killLeadingZeros(num1);
	string bottomNum = killLeadingZeros(num2);
	
	int sizeDiff = topNum.size() - bottomNum.size();
	
	if(sizeDiff > 0) 
		bottomNum = addZerosToFront(bottomNum,sizeDiff);
	else if(sizeDiff < 0)
		topNum = addZerosToFront(topNum,abs(sizeDiff));
	else /* size are the same */;
	
	
	list<char> result = list<char>();

	bool hasCarry = false;

	/* add digit by digit */
	for(size_t pos = topNum.size()-1; pos != -1; --pos)
	{
		/* add the last digit */
		size_t digitAdded = toBaseInt(topNum[pos]) + toBaseInt(bottomNum[pos]);
		/* add 1 if their is a carry from last addition */
		if(hasCarry){ ++digitAdded; hasCarry ^=1; }
		/* save the last digit of the result */
		result.push_back(toBaseChar(digitAdded % base));

		if(digitAdded >= base) hasCarry ^= true;
	}
	/* check if the left-most digit had a carry */
	if(hasCarry){ result.push_back('1'); }
	
	string strNum;
	/* copy data */
	while(!result.empty()){
		strNum.push_back(result.back());
		result.pop_back();
	}

	return strNum;
}

Dani AI

Generated

A few concrete improvements and hardening notes to make the snippet safe, correct and faster while keeping the same string-based approach. ’s example is a good starting point and ’s comment on integer size is on the right track — the list below focuses on correctness edge-cases, input robustness and simple performance wins.

The most critical correctness bug is iterating with an unsigned index and testing pos != -1 — that underflows and never terminates. Use a signed index or a controlled reverse loop. Example safe pattern:

for (int pos = int(topNum.size()) - 1; pos >= 0; --pos) {
    // use topNum[pos], bottomNum[pos]
}

Or iterate forward and compute the mirrored index: size_t pos = n - 1 - i; — both avoid unsigned wrap.

Leading-zero trimming and empty input need bounds checks. Calling num[0] or walking past the end when the string is all zeros is undefined behavior. A safe replacement is:

size_t p = num.find_first_not_of('0');
if (p == string::npos) return "0";
return num.substr(p);

Digit parsing and validation should handle lowercase input and an explicit “not found” result. Use std::toupper(static_cast<unsigned char>(c)) before lookup, and make toBaseInt return -1 for invalid digits so validation can fail cleanly instead of relying on unsigned casts.

Performance: avoid std::list<char> for the result — prefer std::string or std::vector<char> with reserve(n+1), push digits and then std::reverse once. Use an int carry = 0; (not a toggled bool) and compute sum = a + b + carry; carry = sum / base; — clearer and less error-prone.

API and testing notes: return an error via std::optional<string> or exceptions instead of a magic "NULL" string; add unit tests for empty input, all-zero input, lowercase letters, invalid digits, different lengths, and very large lengths. These changes fix subtle UB, make the routine resilient, and improve runtime for long inputs.

Member Avatar for Tumlee
Tumlee 42 Junior Poster in Training

Impressive, but:

1) Bases zero and one cannot possibly exist, nor could it produce any sort of sensical output nor input.
2) Using "int" will more than likely limit you. That's only four bytes in most environments, or eight hex characters. You should probably use the int64_t type.

Member Avatar for mrnutty
mrnutty 761 Senior Poster

Man its been a while since this snippet. As to a response to your comments,

1) The title was misleading and incorrect. As you can see in line 84

if(!isValidNum(num1,base) || !isValidNum(num2,base) || base <= 0 || base > 36)  
  return "NULL";

that it rejects invalid bases and data.

2) Sure you can use int64_t but that still has the same fundamental issue as you said with int. If I wanted this to be general I could have use std::string. But this snippet was not to be used for production to handle every case. Its just a snippet to handle more cases.

Thanks for the input tho.

Member Avatar for Tumlee
Tumlee 42 Junior Poster in Training

Yeah, int64_t has the same problem, but you will be less likely to run into that limitation if you use a larger int size.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview