CODEWITHSUNDEEP
c++hexbignummultiprecision
gopy
gopy

Reputation: 328

hex string arithmetic in c++

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?

Upvotes: 1

Views: 1563

Answers (2)

KamilCuk
KamilCuk

Reputation: 140880

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.

Upvotes: 2

Acorn
Acorn

Reputation: 26066

Implementing addition, subtraction and comparison over fixed-base numeric strings yourself should be quite easy.

For instance, for addition and subtraction, simply do it as you would in paper: start on the right-hand end of both strings, parse the chars, compute the result, then carry over, etc. Comparison is even easier, and you go left-to-right.

Of course, all this is assuming you don't need performance (otherwise you should be using a proper library).

Upvotes: 2

Related Questions