hex string arithmetic in c++

Question

I want to do basic arithmetic (addition, subtraction and comparison) with 64 digit hex numbers represented as strings. for example

"ffffa"+"2" == "ffffc"

Since binary representation of such a number requires 256 bits, I cannot convert the string to basic integer types. one solution is to use gmp or boost/xint but they are too big for this simple functionality.

Is there a lightweight solution that can help me?

Answer 1

Just write a library which will handle the strings with conversion between hex to int and will add one char at a time, taking care of overflow. It took minutes to implement such an algorithm:

#include <cstdio>
#include <sstream>
#include <iostream>

using namespace std;

namespace hexstr {
    char int_to_hexchar(int v) {
        if (0 <= v && v <= 9) {
            return v + '0';
        } else {
            return v - 10 + 'a';
        }
    }
    int hexchar_to_int(char c) {
        if ('0' <= c && c <= '9') {
            return c - '0';
        } else {
            return c - 'a' + 10;
        }
    }
    int add_digit(char a, char b) {
        return hexchar_to_int(a) + hexchar_to_int(b);
    }
    void reverseStr(string& str) { 
        int n = str.length(); 
        for (int i = 0; i < n / 2; i++) 
            swap(str[i], str[n - i - 1]); 
    }
    void _add_val_to_string(string& s, int& val) {
        s.push_back(int_to_hexchar(val % 16));
        val /= 16;
    }
    string add(string a, string b)
    {
        auto ita = a.end();
        auto itb = b.end();
        int tmp = 0;
        string ret;

        while (ita != a.begin() && itb != b.begin()) {
            tmp += add_digit(*--ita, *--itb);
            _add_val_to_string(ret, tmp);
        }
        while (ita != a.begin()) {
            tmp += hexchar_to_int(*--ita);
            _add_val_to_string(ret, tmp);
        }
        while (itb != b.begin()) {
            tmp += hexchar_to_int(*--itb);
            _add_val_to_string(ret, tmp);
        }
        while (tmp) {
            _add_val_to_string(ret, tmp);
        }

        reverseStr(ret);

        return ret;
    }
}

int main()
{
    std::cout 
        << "1bd5adead01230ffffc" << endl
        << hexstr::add(
                std::string() + "dead0000" + "00000" + "ffffa", 
                std::string() + "deaddead" + "01230" + "00002"
        ) << endl;
    return 0;
}

This can be optimized, the reversing string maybe can be omitted and some cpu cycles and memory allocations spared. Also error handling is lacking. It will work only on implementations that use ASCII table as the character set and so on... But it's as simple as that. I guess this small lib can handle any hex strings way over 64 digits, depending only on the host memory.