int128的实现（基本完成）
虽然有一个声明叫_int128但是这并不是C++标准：
long long 不够用？详解 __int128 - FReQuenter - 博客园 (cnblogs.com)
网络上去找int128的另类实现方法，发现几乎都是在介绍_int128的
然后我就自己想了个办法，当时还没学C++，用C草草写了下了事，也没有验证行不行
在这周一（2024/2/19）看了C++的类以及运算符重载之后，我打算拿int128来练练手
重载倒是很快练好了，但是代码有大问题：
可以看看我之前的愚蠢的代码
主要是完全没注意到数爆出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天去改，虽然不是每一刻都在想，但是也挺搞事的）
原文地址：https://blog.csdn.net/Fool256353/article/details/136242468
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！