大数情况下的字符串四则运算和进制转换问题
时间: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)