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();
}
This works similar to how people would hack higher precision real numbers into older system that does not provide support a long time ago. Pretty cool!
I RUS
The code is pretty neat.
Meanwhile, I found something similar to your implementation: the
std::_Signed128
andstd::_Unsigned128
in MSC++2019, which may be a firm reference for implementingsigned __int128
.Auto comment: topic has been updated by shiny_shine (previous revision, new revision, compare).
Very nice code! There is also an alternative one adapted from abseil, with some modification. Unfortunately, it is tediously long.
Seriously?
In fact it doesn't matter if you remove them
but I think this impl has a better performance
Auto comment: topic has been updated by shiny_shine (previous revision, new revision, compare).
Auto comment: topic has been updated by shiny_shine (previous revision, new revision, compare).