代码之家 › 专栏 › 技术社区 › gopy

C++中的十六进制字符串运算

multiprecision bignum hex c++

gopy · 技术社区 · 6 年前

我想用64位十六进制数字表示字符串来做基本的算术(加法、减法和比较)。例如

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

因为这样一个数字的二进制表示需要256位,所以我无法将字符串转换为基本整数类型。一种解决方案是使用 gmp 或 boost/xint 但是对于这个简单的功能来说,它们太大了。

有轻量级的解决方案可以帮助我吗?

2 回复 | 直到 6 年前

KamilCuk 6 年前

只需编写一个库,它将处理十六进制到int之间的字符串转换,并一次添加一个字符,注意溢出。实现这种算法需要几分钟的时间:

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

这可以优化,可以省略反转字符串,并且可以节省一些CPU周期和内存分配。此外,还缺少错误处理。它只适用于使用ASCII表作为字符集的实现,等等…但就这么简单。我想这个小的lib可以处理64位以上的任何十六进制字符串,这只取决于主机内存。

Acorn 6 年前

在固定基数字字符串上自己实现加法、减法和比较应该很容易。

例如,对于加法和减法,只需像在纸上那样做:从两个字符串的右端开始,分析 char s,计算结果,然后结转,等等。比较更容易,从左到右。

当然,所有这些都假定您不需要性能(否则您应该使用适当的库)。