高精度加法 - 不够通用 - 见力扣67题
vector<int> add(vector<int> &A, vector<int> &B)
{
vector<int> C;
if (A.size() < B.size()) return add(B, A);
int t = 0; //保存进位
for (int i = 0;i < A.size(); i++)
{
t += A[i]; // t=0 || t变成进位以后就是1
if (i < B.size())
t += B[i]; // 这个时候t = A[i]+B[i]
C.push_back(t % 10); //把相加以后的尾数入栈
t /= 10; //t取最高位，即变成了进位1或者0
}
if (t) C.push_back(1);
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1;i >= 0; i--) A.push_back(a[i] - '0');
for (int i = b.size() - 1;i >= 0; i--) B.push_back(b[i] - '0');
auto C = add(A, B);
for (int i = C.size() - 1;i >= 0; i--) cout << C[i];
return 0;
}
高精度减法
// 先比较A和B的大小 （默认A和B为正数）
bool cmp(vector<int> &A, vector<int> &B)
{
if (A.size() != B.size()) // 先用位数比较大小
return A.size() > B.size();
for (int i = A.size() - 1;i >= 0; i--)
{
if (A[i] != B[i])
return A[i] > B[i]; // 从高位往地位比较数字的大小
}
return true;
}
vector<int> sub(vector<int> &A, vector<int> &B) //默认A比B大
{
vector<int> C;
for (int i = 0, t = 0;i < A.size(); i++) // 初始化t=0，用于表示i位置上相减的结果
{
// i位置上如果借位了，就要减去借位t的值，没有借位则t=0
t = A[i] - t;
if (i < B.size())
t -= B[i]; // t= A[i]-t-B[i]
// 如果t是个负数，则借10，最后设置t=1，
// 下一轮位置相减时t=A[i]-t
C.push_back((t + 10) % 10);
// 设置t的值
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1;i >= 0; i--) A.push_back(a[i] - '0');
for (int i = b.size() - 1;i >= 0; i--) B.push_back(b[i] - '0');
if (cmp(A, B))
{
auto C = sub(A, B);
for (int i = C.size() - 1;i >= 0; i--) cout << C[i];
}
else
{
auto C = sub(B, A);
printf("-");
for (int i = C.size() - 1;i >= 0; i--) cout << C[i];
}
return 0;
}
高精度乘法
#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0;i < A.size() || t; i++)
{
if(i < A.size())
t += A[i] * b; // t用来暂存位数相乘的结果
C.push_back(t % 10); // 保留最后一位
t /= 10; // 暂存进位
}
while (C.size() > 1 && C.back() == 0)
C.pop_back();// 可能是乘 0
return C;
}
int main()
{
string a;
int b;
cin >> a >> b;
vector<int> A;
for (int i = a.size() - 1;i >= 0; i--) A.push_back(a[i] - '0');
auto C = mul(A, b);
for (int i = C.size() - 1;i >= 0; i--) cout << C[i];
return 0;
}
高精度除法
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> dvi(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0; //上一位的余数
for (int i = A.size() - 1;i >= 0; i--)
{
r = r * 10 + A[i]; //上一位的余数*10,
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin >> a >> b;
vector<int> A;
for (int i = a.size() - 1;i >= 0; i--) A.push_back(a[i] - '0');
int r;
auto C = dvi(A, b, r);
for (int i = C.size() - 1;i >= 0; i--) cout << C[i];
cout << endl << r << endl;
return 0;
}
LeetCode 67. 二进制求和
class Solution {
public:
string addBinary(string a, string b) {
string s;
s.reserve(a.size() + b.size());
int c = 0, i = a.size() - 1, j = b.size() - 1;
while(i >= 0 || j >= 0 || c == 1)
{
c += i >= 0 ? a[i--] - '0' : 0;
c += j >= 0 ? b[j--] - '0' : 0;
s.push_back((c & 1) + '0');
c >>= 1;//通过右移，获得该位向前的进位
}
reverse(s.begin(), s.end());
return s;
}
};
菜鸡的理解（错了请指正……）：
从a、b的最后一位开始（因为至少有一位所以这样就是对齐的），三目运算符判断是否已经向前遍历完了当前a或b字符串，如果遍历完了（i或j为0）那么为空，给0，不然给本位字符与0的ASCII值相减的结果也就是0或1的数值。
每循环一次就把a和b给的值加到c中去，用位与操作c&1取c的二进制最后一位（0或1）加0的ASCII值变回字符，然后这个字符就是结果字符串的当前位。然后c右移1位完成二进制的进位操作（值相当于十进制下除以2，也就是让c=进位后的下一位），保存当前的下一位结果，然后进行下一次的针对下一位的运算。
此时如果前面的运算进位了，c就会是1，如果前面的运算没进位，那么c就会是0。【有点绕好像】
PS：循环判断里判断c是否为1的条件就是因此而生的，操作到最后如果最后第二次循环有进位，那么i=0,j=0,c=1，此时要再循环一遍这样才能把1放进结果字符串里的最后一位，也就是翻转后的最高位。（所以从这个逻辑上讲，一开始的reserve空间开大了……应该是只要a、b两者中的最长者的长度加1即可，毕竟两个N进制数之和的位数最多是原有最大位数加1）
模板
class Solution {
public:
string addBinary(string a, string b) {
int i=a.length()-1,j=b.length()-1,add=0;
string ans="";
while(i>=0||j>=0||add!=0){
int x=i>=0?a[i]-'0':0;
int y=j>=0?b[j]-'0':0;
int sum=x+y+add;
ans.push_back('0' + sum%2); // %x 对应进制
add=sum/2; // /x 对应进制
i--;
j--;
}
reverse(ans.begin(),ans.end());
return ans;
}
};
class Solution {
public:
string addBinary(string a, string b) {
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int t=0;
string ans; //存储答案
for(int i=0;i<a.size() || i<b.size() || t;i++)
{
if(i<a.size())t+=a[i]-'0'; //每个位置上都相加
if(i<b.size())t+=b[i]-'0';
ans+=to_string(t%2); //转换为二进制存入ans
t/=2;
}
reverse(ans.begin(),ans.end());//反转
return ans;
}
};
LeetCode 2. 两数相加
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode();
ListNode* curr = dummy;
int carry = 0;
while (l1 || l2) { //l2和l2还没到末尾
// 当前节点有值，就把当前节点的值给x或者y
int x = l1 ? l1->val : 0; // int x = (l1 ！== null) ? l1->val : 0;
int y = l2 ? l2->val : 0;
int total = x + y + carry;
curr->next = new ListNode(total % 10);
curr = curr->next;
carry = total / 10;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
if (carry != 0) curr->next = new ListNode(carry);
return dummy->next;
}
};
leetcode 989 号算法题：数组形式的整数加法
leetcode 66 号算法题：加 1
leetcode 415 号算法题：字符串相加
leetcode 67 号算法题：二进制求和