A refinement of http://fuliang.iteye.com/blog/368928
.
#include <string>
#include <iostream>
using namespace std;
/*
* This implementation uses string to represent big integer. Arithmetic is
* performed on every digit. This is not a efficient way. Hacker's Delight
* provides a more efficient way. If I am not wrong, Java BigInteger performs
* arithmetic in that way.
*/
// ascii code for '0'
const int ZERO = 48;
inline int compare(string str1, string str2) {
int result = str1.size() - str2.size();
if (result != 0)
return result;
else
return str1.compare(str2);
}
inline int int_val(const char& ch) {
return ch - ZERO;
}
inline void swap_str(string& str1, string& str2) {
string temp = str1;
str1 = str2;
str2 = temp;
}
inline char ch_val(int integer) {
return char(integer + ZERO);
}
inline bool negative(string str) {
return str[0] == '-';
}
inline bool same_sign(string str1, string str2) {
return str1[0] == '-' && str2[0] == '-'
|| str1[0] != '-' && str2[0] != '-';
}
inline void format(int sign, string& integer) {
integer.erase(0, integer.find_first_not_of('0'));
if(integer.empty()) integer = "0";
if((sign == -1) && (integer[0] != '0'))
integer = "-" + integer;
}
string add_int(string, string);
string subtraction_int(string, string);
string add_natural(string, string);
string subtraction_natural(string, string);
/**
* add_int - add two integers.
*/
string add_int(string lterm, string rterm) {
int sign = 1;
string sum;
if (same_sign(lterm, rterm)) {
if (negative(lterm)) {
sign = -1;
lterm.erase(0, 1);
rterm.erase(0, 1);
}
sum = add_natural(lterm, rterm);
} else {
if (negative(lterm))
swap_str(lterm, rterm);
rterm.erase(0, 1);
int res = compare(lterm, rterm);
if (res == 0)
return "0";
else if (res < 0) {
sign = -1;
swap_str(lterm, rterm);
}
sum = subtraction_natural(lterm, rterm);
}
format(sign, sum);
return sum;
}
/**
* subtraction_int - subtract rterm from lterm.
*/
string subtraction_int(string lterm, string rterm) {
if (negative(rterm))
rterm.erase(0, 1);
else
rterm = "-" + rterm;
return add_int(lterm, rterm);
}
/**
* subtraction_natural - subtract rterm natural number from lterm natural number.
*
* rterm should be less than lterm.
*/
string subtraction_natural(string lterm, string rterm) {
string difference;
string::size_type offset = lterm.size() - rterm.size();
for (int i = rterm.size() - 1; i >= 0; i--) {
if (lterm[i + offset] < rterm[i]) {
difference = ch_val(lterm[i + offset] - rterm[i] + 10) + difference;
int j = i + offset - 1;
while (lterm[j] == ZERO) {
lterm[j--] = 9 + ZERO;
}
lterm[j] = char(int(lterm[j]) - 1);
} else {
difference = ch_val(lterm[i + offset] - rterm[i]) + difference;
}
}
for (int i = offset - 1; i >= 0; i--)
difference = lterm[i] + difference;
return difference;
}
/**
* add_natural - add the two natural number.
*/
string add_natural(string lterm, string rterm) {
int i;
string sum;
string::size_type ll, lr;
ll = lterm.size();
lr = rterm.size();
if (ll < lr) {
for (i = 1; i <= lr - ll; i++)
lterm = "0" + lterm;
} else {
for (i = 1; i <= ll - lr; i++)
rterm = "0" + rterm;
}
int digit = 0, carry = 0, temp;
for (i = lterm.size() - 1; i >= 0; i--) {
temp = int_val(lterm[i]) + int_val(rterm[i]) + carry;
digit = temp % 10;
carry = temp / 10;
sum = ch_val(digit) + sum;
}
if (carry != 0)
sum = ch_val(carry) + sum;
return sum;
}
/**
* multiply_int - multiply two integers.
*/
string multiply_int(string lfactor, string rfactor) {
// handle sign
int sign = 1;
if (lfactor[0] == '-') {
sign *= -1;
lfactor = lfactor.erase(0, 1);
}
if (rfactor[0] == '-') {
sign *= -1;
rfactor = rfactor.erase(0, 1);
}
string product;
int i, j;
string::size_type l1, l2;
l1 = lfactor.size();
l2 = rfactor.size();
for (i = l2 - 1; i >= 0; i--) {
string temp;
int digit = 0, carry = 0, product1, rdigit = int_val(rfactor[i]);
if (rdigit != 0) {
for (j = 1; j <= (int)(l2 - 1 - i); j++)
temp = temp + "0";
for (j = l1 - 1; j >= 0; j--) {
product1 = rdigit * int_val(lfactor[j]) + carry;
digit = product1 % 10;
carry = product1 / 10;
temp = ch_val(digit) + temp;
}
if (carry != 0)
temp = ch_val(carry) + temp;
product = add_int(product, temp);
}
}
format(sign, product);
return product;
}
/**
* divide_int - divide divident wiwht divisor.
* @flag: 1 to return quotient, 0 to return residue.
*/
string divide_int(string divident, string divisor, int flag) {
string quotient, residue;
int sign1 = 1, sign2 = 1;
// divided by zero
if (divisor == "0") {
quotient = "ERROR";
residue = "ERROR";
if (flag == 1)
return quotient;
else
return residue;
}
// divide zero
if (divident == "0") {
quotient = "0";
residue = "0";
}
if (divident[0] == '-') {
divident.erase(0, 1);
sign1 = -1;
sign2 = -1;
}
if (divisor[0] == '-') {
divisor.erase(0, 1);
sign1 *= -1;
}
int res = compare(divident, divisor);
if (res < 0) {
quotient = "0";
residue = divident;
} else if (res == 0) {
quotient = "1";
residue = "0";
} else {
string::size_type l1 = divident.size();
string::size_type l2 = divisor.size();
string temp;
string product;
temp.append(divident, 0, l2 - 1);
for (int i = l2 - 1; i < l1; i++) {
temp = temp + divident[i];
// try quotient
for (char ch = '9'; ch >= '0'; ch--) {
string str;
str = str + ch;
product = multiply_int(divisor, str);
if (compare(product, temp) <= 0) {
quotient = quotient + ch;
temp = subtraction_int(temp, product);
break;
}
}
}
residue = temp;
}
format(sign1, quotient);
format(sign2, residue);
return flag ? quotient : residue;
}
string divide_int(string divident, string divisor) {
return divide_int(divident, divisor, 1);
}
int main(int argc, const char *argv[]) {
char ch;
string lterm, rterm, res;
int shift;
while (cin >> ch) {
cin >> lterm >> rterm;
switch (ch) {
case '+':
res = add_int(lterm, rterm);
break;
case '-':
res = subtraction_int(lterm, rterm);
break;
case '*':
res = multiply_int(lterm, rterm);
break;
case '/':
res = divide_int(lterm, rterm);
break;
default:
break;
}
cout << res << endl;
}
return 0;
}
分享到:
相关推荐
In this book, we describe the optimized implementations of several arithmetic datapath, controlpath, and pseudorandom sequence generator circuits. We explore regular, modular, cascadable, and bit-...
H.2 Basic Techniques of Integer Arithmetic H-2 H.3 Floating Point H-13 H.4 Floating-Point Multiplication H-17 H.5 Floating-Point Addition H-21 H.6 Division and Remainder H-27 H.7 More on Floating-...
1 2/3维图像分割工具箱 2 PSORT粒子群优化工具箱 3 matlab计量工具箱Lesage 4 MatCont7p1 5 matlab模糊逻辑工具箱函数 6 医学图像处理工具箱 7 人工蜂群工具箱 8 MPT3安装包 9 drEEM toolbox 10 DOMFluor Toolbox v...
XNum是用C ++编写的整数算术库。 XNum与其他库(例如GMP)之间的区别前者试图模仿人类自己用来做算术的实用方法。 当前的
用于大整数算术的BASIC库,以及一些数论模块。
FPGA Placement Methodologies
The arithmetic of Computer Science . The contents cover senior and complicated logic mathematics.
Final Thoughts on Integer Arithmetic 98 2.4 Floating Point 99 2.4.1 Fractional Binary Numbers 100 2.4.2 IEEE Floating-Point Representation 103 2.4.3 Example Numbers 105 2.4.4 Rounding 110 2.4.5 ...
Arithmetic
arithmetic111.rararithmetic111.rararithmetic111.rararithmetic111.rararithmetic111.rararithmetic111.rar
arithmetic coder, algorithm, compressing.
Integer Arithmetic IP Cores User Guide Intel FPGA 数学整数运算IP 使用手册
Convolution arithmetic tutorialConvolution arithmetic tutorialConvolution arithmetic tutorial
Fixed-Point Arithmetic: An Introduction Randy Yates
主要介绍Prime field arithmetic, Binary field arithmetic, Optimal extension field arithmetic等几个域的一些基本算术问题
当 BigDecimal 值大于 Integer.MAX_VALUE 时,intValue() 方法将抛出 java.lang.ArithmeticException 异常。例如,在上面的示例代码中,若输入的 BigDecimal 值为 2147483648 时,intValue() 方法将抛出“Out of ...
影像處理程式的project。使用Arithmetic mean filter處理圖片
The role of arithmetic in datapath design in VLSI design has been increasing in importance over the last several years due to the demand for processors that are smaller, faster, and dissipate less ...
Computer Arithmetic Algorithms 专业书 英文版本
:elephant: ... integer . parse ( 16 , 100 , 'ff' ) ; // [ 2 , 55 ] integer . stringify ( 100 , 16 , [ 2 , 55 ] ) ; // 'ff' integer . translate ( 10 , 16 , '255' ) ; // 'ff' :scroll: 参考