As you know, in this reason, 64-bit C++ compilers are temporarily disabled.
In order to keep using __int128 (at least partially) in 32-bit compilers, I'm trying writing a template of the unsigned version of __int128.
On 2024/3/15, I completed writing the alpha version of it.
If you find bugs in my code, please leave a comment below. Thanks!
UPD:
2024/3/14: added (maybe) all operators that an __int128 has except for operator/ / fixed infinite-recursion bug in several operators
2024/3/15: added operator/ / fixed many bugs in almost all arithmetic operators / completed first (buggy) version of this handmade __int128
Here's it:
integer_128_impl.cpp
#include<tuple>
#include<iostream>
#include<climits>
namespace RedshiftShine{
using ll=unsigned long long;
const ll ulmx=ULLONG_MAX;
const ll shift=64;
ll min(ll x,ll y){
return x<y?x:y;
}
ll max(ll x,ll y){
return x>y?x:y;
}
bool detect_overflow_add(ll x,ll y){
return x+y<min(x,y);
}
bool detect_overflow_minus(ll x,ll y){
return x<y;
}
class Custom_Unsigned_int128{
private:
ll higherInt,lowerInt;
public:
Custom_Unsigned_int128(){}
template<typename _Tp>
Custom_Unsigned_int128(_Tp x):
higherInt(0),
lowerInt(x){}
template<typename _Tp>
Custom_Unsigned_int128(_Tp x,_Tp y):
higherInt(x),
lowerInt(y){}
Custom_Unsigned_int128
(const Custom_Unsigned_int128& ele):
higherInt(ele.higherInt),
lowerInt(ele.lowerInt){}
std::pair<ll,ll>
base_access(){
return std::pair<ll,ll>{
higherInt,
lowerInt
};
}
Custom_Unsigned_int128&
operator=(const Custom_Unsigned_int128& x){
higherInt=x.higherInt,
lowerInt=x.lowerInt;
return *this;
}
template<typename _Tp>
Custom_Unsigned_int128&
operator=(const _Tp& x){
*this=Custom_Unsigned_int128
(
0,x
);
return *this;
}
template<typename _Tp>
Custom_Unsigned_int128
operator+(const _Tp& x){
return Custom_Unsigned_int128
(
higherInt+
detect_overflow_add(lowerInt,x),
lowerInt+x
);
}
template<typename _Tp>
friend Custom_Unsigned_int128
operator+(const _Tp& x,const Custom_Unsigned_int128& ele){
return Custom_Unsigned_int128
(
ele.higherInt+
detect_overflow_add(ele.lowerInt,x),
ele.lowerInt+x
);
}
Custom_Unsigned_int128
operator+(const Custom_Unsigned_int128& x){
return Custom_Unsigned_int128
(
higherInt+x.higherInt+
detect_overflow_add(lowerInt,x.lowerInt),
lowerInt+x.lowerInt
);
}
template<typename _Tp>
bool
operator==(const _Tp& x)const{
return
(
!higherInt and
lowerInt==x
);
}
template<typename _Tp>
friend bool
operator==(const _Tp& x,const Custom_Unsigned_int128& ele){
return ele==x;
}
bool
operator==(const Custom_Unsigned_int128& x)const{
return
(
higherInt==x.higherInt and
lowerInt==x.lowerInt
);
}
template<typename _Tp>
bool
operator!=(const _Tp& x)const{
return !(*this==x);
}
template<typename _Tp>
friend bool
operator!=(const _Tp& x,const Custom_Unsigned_int128& ele){
return !(ele==x);
}
template<typename _Tp>
bool
operator<(const _Tp& x)const{
return
(
!higherInt and
lowerInt<x
);
}
template<typename _Tp>
friend bool
operator<(const _Tp& x,const Custom_Unsigned_int128& ele){
return
(
ele.higherInt or
ele.lowerInt>x
);
}
bool
operator<(const Custom_Unsigned_int128& x)const{
return
(
higherInt<x.higherInt or
(
higherInt==x.higherInt and
lowerInt<x.lowerInt
)
);
}
template<typename _Tp>
bool
operator<=(const _Tp& x)const{
return
(
*this<x or
*this==x
);
}
template<typename _Tp>
friend bool
operator<=(const _Tp& x,const Custom_Unsigned_int128& ele){
return ele<=x;
}
bool
operator<=(const Custom_Unsigned_int128& x)const{
return
(
*this<x or
*this==x
);
}
template<typename _Tp>
bool
operator>(const _Tp& x)const{
return
!(
*this<=x
);
}
template<typename _Tp>
friend bool
operator>(const _Tp& x,const Custom_Unsigned_int128& ele){
return !(ele<=x);
}
bool
operator>(const Custom_Unsigned_int128& x)const{
return
!(
*this<=x
);
}
template<typename _Tp>
bool
operator>=(const _Tp& x)const{
return
!(
*this<x
);
}
template<typename _Tp>
friend bool
operator>=(const _Tp& x,const Custom_Unsigned_int128& ele){
return !(ele<x);
}
bool
operator>=(const Custom_Unsigned_int128& x)const{
return
!(
*this<x
);
}
template<typename _Tp>
Custom_Unsigned_int128&
operator+=(const _Tp& x){
return *this=*this+x;
}
template<typename _Tp>
Custom_Unsigned_int128
operator-(const _Tp& x)const{
return Custom_Unsigned_int128
(
higherInt-
detect_overflow_minus(lowerInt,x),
lowerInt-x
);
}
Custom_Unsigned_int128
operator-(const Custom_Unsigned_int128& x)const{
return Custom_Unsigned_int128
(
higherInt-x.higherInt-
detect_overflow_minus(lowerInt,x.lowerInt),
lowerInt-x.lowerInt
);
}
template<typename _Tp>
Custom_Unsigned_int128&
operator-=(const _Tp& x){
return *this=*this-x;
}
template<typename _Tp>
Custom_Unsigned_int128
operator&(const _Tp& x){
return Custom_Unsigned_int128
(
0ull,
lowerInt&x
);
}
template<typename _Tp>
Custom_Unsigned_int128
friend operator&(const _Tp& x,const Custom_Unsigned_int128& ele){
return Custom_Unsigned_int128
(
ele.higherInt,
ele.lowerInt&x
);
}
Custom_Unsigned_int128
operator&(const Custom_Unsigned_int128& x){
return Custom_Unsigned_int128
(
higherInt&x.higherInt,
lowerInt&x.lowerInt
);
}
template<typename _Tp>
Custom_Unsigned_int128&
operator&=(const _Tp& x){
return *this=*this&x;
}
template<typename _Tp>
Custom_Unsigned_int128
operator|(const _Tp& x){
return Custom_Unsigned_int128
(
higherInt,
lowerInt|x
);
}
template<typename _Tp>
Custom_Unsigned_int128
friend operator|(const _Tp& x,const Custom_Unsigned_int128& ele){
return Custom_Unsigned_int128
(
ele.higherInt,
ele.lowerInt|x
);
}
Custom_Unsigned_int128
operator|(const Custom_Unsigned_int128& x){
return Custom_Unsigned_int128
(
higherInt|x.higherInt,
lowerInt|x.lowerInt
);
}
template<typename _Tp>
Custom_Unsigned_int128&
operator|=(const _Tp& x){
return *this=*this|x;
}
template<typename _Tp>
Custom_Unsigned_int128
operator^(const _Tp& x){
return Custom_Unsigned_int128
(
higherInt,
lowerInt^x
);
}
template<typename _Tp>
Custom_Unsigned_int128
friend operator^(const _Tp& x,const Custom_Unsigned_int128& ele){
return Custom_Unsigned_int128
(
ele.higherInt,
ele.lowerInt^x
);
}
Custom_Unsigned_int128
operator^(const Custom_Unsigned_int128& x){
return Custom_Unsigned_int128
(
higherInt^x.higherInt,
lowerInt^x.lowerInt
);
}
template<typename _Tp>
Custom_Unsigned_int128&
operator^=(const _Tp& x){
return *this=*this^x;
}
Custom_Unsigned_int128
operator~(){
return Custom_Unsigned_int128(
~higherInt,
~lowerInt
);
}
template<typename _Tp>
Custom_Unsigned_int128
operator<<(const _Tp& x){
return x<shift?
Custom_Unsigned_int128(
higherInt<<x|(lowerInt>>(shift-x)),
lowerInt<<x
):
Custom_Unsigned_int128(
lowerInt<<(x-shift),
0ull
);
}
template<typename _Tp>
Custom_Unsigned_int128&
operator<<=(const _Tp& x){
return *this=*this<<x;
}
template<typename _Tp>
Custom_Unsigned_int128
operator>>(const _Tp& x){
return x<shift?
Custom_Unsigned_int128(
higherInt>>x,
lowerInt>>x|(higherInt<<(shift-x))
):
Custom_Unsigned_int128(
0ull,
higherInt>>(x-shift)
);
}
template<typename _Tp>
Custom_Unsigned_int128&
operator>>=(const _Tp& x){
return *this=*this>>x;
}
template<typename _Tp>
Custom_Unsigned_int128
operator*(const _Tp& x)const{
Custom_Unsigned_int128 ret(0),pr(*this);
_Tp tm(x);
for(;tm;tm>>=1){
if(tm&1)ret+=pr;
pr<<=1;
}
return ret;
}
template<typename _Tp>
Custom_Unsigned_int128
friend operator*(const _Tp& x,const Custom_Unsigned_int128& ele){
Custom_Unsigned_int128 ret(0),pr(ele);
_Tp tm(x);
for(;tm!=0;tm>>=1){
if((tm&1)!=0)ret+=pr;
pr+=pr;
}
return ret;
}
template<typename _Tp>
Custom_Unsigned_int128&
operator*=(const _Tp& x){
return *this=*this*x;
}
template<typename _Tp>
Custom_Unsigned_int128
operator/(const _Tp& x)const{
Custom_Unsigned_int128 ret(0),pr(x),trm(1),ts(*this);
while((!(pr.higherInt>>(shift-1))) and pr<=ts){
pr<<=1,trm<<=1;
}
pr>>=1,trm>>=1;
for(;;pr>>=1,trm>>=1){
// if(ts<pr)continue;
while(ts>=pr){
ts-=pr,ret+=trm;
}
if((pr&1)!=0)break;
}
return ret;
}
template<typename _Tp>
Custom_Unsigned_int128&
operator/=(const _Tp& x){
return *this=*this/x;
}
template<typename _Tp>
_Tp
operator%(const _Tp& x)const{
return (*this-*this/x*x).lowerInt;
}
Custom_Unsigned_int128
operator%(const Custom_Unsigned_int128& x)const{
return *this-*this/x*x;
}
template<typename _Tp>
Custom_Unsigned_int128&
operator%=(const _Tp& x){
return *this=*this%x;
}
};
}
void print(RedshiftShine::Custom_Unsigned_int128 v){
if(v==0)return;
print(v/10);
putchar(v%10+'0');
}
void test(){
RedshiftShine::Custom_Unsigned_int128 ci(0,1),cz(0,1);
print(ci),putchar(' ');
for(int i=128;i;i--){
std::swap(ci,cz);
cz+=ci;
print(cz),putchar(' ');
}
}
int main(){
test();
}
