大数情况下的字符串四则运算和进制转换问题

时间:2020-03-05 18:53:42   收藏:0   阅读:73

 

最近接触到了很多进制转换中可能存在溢出或者数位超限的问题;

 

如果采用大数利用结构体操作那一套会存在超时问题,这里专门看一下纯字符串操作;

 

进制运算本身就是多个大数运算的组合,所以只需要关注低精度、高精度下的大数运算即可;

 

字符串除法:

多用于取模的场景,例如十进制转二进制;

string divide(string str, int x) {
    int r = 0;
    for (int i = 0; i < str.size(); i++) {
        int temp = r * 10 + (str[i] - 0);
        str[i] = temp / x + 0;
        //商不信开辟空间直接计入原位数,和大数思想一样,还是商位数等于被除数位数;
        r = temp % x;
    }
    //去掉前导零;
    while (str.size() > 0 && str[0] == 0) {
        str.erase(0, 1);
    }
    return str;
}

从代码逻辑上来看,其实和大数问题的除法没有什么其他本质上的区别,无非就是取余数累计下一位,计算商;

所以进制转换操作无非就是一直取模相除;

 

这里还有一个骚操作,一直以来没有注意:

string str;
while (str.size() != 0) {
   int last = str[str.size() - 1] - 0;
   binary.push_back(last % 2);
   str = divide(str, 2);
}

取模运算可以直接取最后一位数字取模即可,这点自己没想到;

 

字符串乘法:

string multi(string str, int x) {
    int carry = 0;
    for (int i = str.size() - 1; i >= 0; i--) {
        int temp = (str[i] - 0)*x + carry;
        str[i] = temp % 10 + 0;
        carry = temp / 10;
    }
    if (carry != 0) {
        str = 1 + str;
    }
    return str;
}

其实和大数问题一毛一样;

这里还有一个比较聪明的地方:

最后如果还有进位的情况下,进位肯定为1,这个手算可以发现;

 

所以个人感觉,如果不用涉及进制转换,只涉及到大数高精度或者低精度计算,使用bign结构体方式即可;

如果采用进制问题下的大数存储运算,string更简洁更快一点,没有那么多开空间和结构体的运算;

原文:https://www.cnblogs.com/songlinxuan/p/12421683.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!