int128的实现（基本完成）

虽然有一个声明叫_int128但是这并不是C++标准：

long long 不够用？详解 __int128 - FReQuenter - 博客园 (cnblogs.com)

网络上去找int128的另类实现方法，发现几乎都是在介绍_int128的

然后我就自己想了个办法，当时还没学C++，用C草草写了下了事，也没有验证行不行

在这周一（2024/2/19）看了C++的类以及运算符重载之后，我打算拿int128来练练手

重载倒是很快练好了，但是代码有大问题：

int128的实现（未完成）-CSDN博客

int128的实现_实现一个int128的数-CSDN博客

可以看看我之前的愚蠢的代码

主要是完全没注意到数爆出2^64的问题（主要体现在上面的第一篇博客，第二篇博客因为没专门写输入输出，所以没爆掉）

还有一个非常吃屎的东西：0xFFFFFFFF这个数，是2^32-1，不是2^32

顺便把输入吞掉一个字符的问题解决了（用了ungetc函数）

说说原理吧：

总所周知，我们这里的最高位的int的位数是64位（long long），最高表示的数是2^64-1（无符号），只有18,446,744,073,709,551,615大概10的20次方，有的时候是不够用的，用高精度数组的速度的效率又相对较慢，这时候就想到了int128了

但是只能你自己来实现（或者用上面的_int128啦，但是有的时候用不了），所以我就想了一种实现方法

用4个unsignedlonglongint值来记录4个数，分别代表x1 * 2^96, x2 * 2 ^ 64, x3 * 2^32, x4。这样加起来，就是一个int128的数了，而且不会爆掉（之前是用两个数记录高低位的，输入输出爆了，运算倒是没有）

然后按照数学的计算，就可以设计出加减乘除了

代码如下：

#ifndef CSTDIO_
#define CSTDIO_
#include<cstdio>
#endif#ifndef CCTYPE_
#define CCTYPE_
#include<cctype>
#endif#ifndef VECTOR_
#define VECTOR_
#include<vector>
#endif#ifndef INT128_H_
#define INT128_H_typedef unsigned long long LLU;//64位
typedef unsigned int U;//32位
const U MAX32 = 0xFFFFFFFF;
const LLU MAX64_U = 0xFFFFFFFF00000000;
const LLU _2POW32 = (LLU)MAX32 + 1;class INT128{LLU A, B, C, D;
public:INT128(LLU tmp = 0){A = B = 0, C = (tmp & MAX64_U) >> 32, D = tmp & MAX32;};void getnum(void);INT128 operator-(const U & tmp) const;INT128 operator+(const LLU & tmp) const;INT128 operator+(const INT128 & tmp) const;INT128 operator*(const U & tmp) const;INT128 operator/(const U & tmp) const;INT128 operator%(const U & tmp) const;void operator=(const LLU & tmp);void show(void);inline void function1(std::vector<int> & tmp, LLU & data);inline void function2(std::vector<int> & tmp, LLU & data);inline INT128 function3(INT128 & result, LLU & A1, LLU & A2, LLU & A3, LLU & A4);
};void INT128::getnum(void)
{A = B = C = D = 0;std::vector<int> tmp;char c;while(!isdigit(c = getchar()));//清空数字前面的东西do{tmp.insert(tmp.begin(), c - '0');}while(isdigit(c = getchar()));ungetc(c, stdin);//开始赋值function1(tmp, D), function1(tmp, C), function1(tmp, B);for(int i = tmp.size() - 1; i >= 0; i--)A = A * 10 + tmp[i];
}
INT128 INT128::operator-(const U & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = 0, A4 = (C << 32) + D - tmp;return function3(result, A1, A2, A3, A4);
}
INT128 INT128::operator+(const LLU & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = C, A4 = D + tmp;return function3(result, A1, A2, A3, A4);
}
INT128 INT128::operator*(const U & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = C, A4 = D;A1 *= tmp, A2 *= tmp, A3 *= tmp, A4 *= tmp;return function3(result, A1, A2, A3, A4);
}
INT128 INT128::operator/(const U & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = C, A4 = D;A2 += (A1 % tmp) << 32, A1 /= tmp;A3 += (A2 % tmp) << 32, A2 /= tmp;A4 += (A3 % tmp) << 32, A3 /= tmp;A4 /= tmp;return function3(result, A1, A2, A3, A4);
}
INT128 INT128::operator%(const U & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A, A2 = B, A3 = C, A4 = D;A2 += (A1 % tmp) << 32;A3 += (A2 % tmp) << 32;A4 += (A2 % tmp) << 32;result.D = A4 % tmp;return result;
}
INT128 INT128::operator+(const INT128 & tmp) const
{LLU A1, A2, A3, A4;INT128 result(0);A1 = A + tmp.A, A2 = B + tmp.B, A3 = C + tmp.C, A4 = D + tmp.D;return function3(result, A1, A2, A3, A4);
}
void INT128::operator=(const LLU & tmp)
{A = B = 0, C = (tmp & MAX64_U) >> 32, D = tmp & MAX32;
}
void INT128::show(void)
{std::vector<int> tmp;//A放进数组LLU n_tmp = A;int ext = 0;while(n_tmp){tmp.push_back(n_tmp % 10);n_tmp /= 10;}//B，C，D放进数组function2(tmp, B), function2(tmp, C), function2(tmp, D);//输出if(!tmp.size())  tmp.push_back(0);for(int i = tmp.size() - 1; i >= 0; i--)printf("%d", tmp[i]);
}
inline void INT128::function1(std::vector<int> & tmp, LLU & data)
{LLU ext = 0;bool jud = false;for(int i = tmp.size() - 1; i >= 0; i--){ext = ext * 10 + tmp[i];tmp[i] = ext / _2POW32;jud = (jud || tmp[i]) ? true : false;if(!jud)  tmp.pop_back();ext %= _2POW32;}data = ext;
}
inline void INT128::function2(std::vector<int> & tmp, LLU & data)
{LLU n_tmp = 0;int ext = 0;for(int i = 0; i < tmp.size(); i++)n_tmp += _2POW32 * (LLU)tmp[i], tmp[i] = n_tmp % 10, n_tmp /= 10;while(n_tmp){tmp.push_back(n_tmp % 10);n_tmp /= 10;}n_tmp = data, ext = 0;for(int i = 0; i < tmp.size(); i++){ext += n_tmp % 10 + tmp[i];tmp[i] = ext % 10, ext /= 10, n_tmp /= 10;}n_tmp += ext;while(n_tmp){tmp.push_back(n_tmp % 10);n_tmp /= 10;}
}
inline INT128 INT128::function3(INT128 & result, LLU & A1, LLU & A2, LLU & A3, LLU & A4)
{result.D = A4 & MAX32, A3 += (A4 & MAX64_U) >> 32;result.C = A3 & MAX32, A2 += (A3 & MAX64_U) >> 32;result.B = A2 & MAX32, A1 += (A2 & MAX64_U) >> 32;result.A = A1 & MAX32;return result;
}#endif

注：只有加法和赋值支持int128数，然后每种计算都支持常数，但是只有加法和赋值达到2^64-1，其他是2^32-1

至于为什么不让每种计算都支持int128嘛，因为懒得写了，还有乘法会爆int128、没必要，而且蓝桥杯要到了，我得加紧算法的学习了（这个东西花了我4天去改，虽然不是每一刻都在想，但是也挺搞事的）