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

mrnutty 0 Tallied Votes 687 Views Share

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;
}
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.

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.

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.