Alternative __int128 without 64-bit compiler (Alpha version)
Difference between en2 and en3, changed 3,016 character(s)
As you know, in [this](https://mirror.codeforces.com/blog/entry/126654) 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 (not completed yet):↵
↵
<spoiler summary="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>max(x,y)<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 Custom_Unsigned_int128bool↵
        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 Custom_Unsigned_int128bool↵
        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 Custom_Unsigned_int128bool↵
        operator<(const _Tp& x,const Custom_Unsigned_int128& ele){↵
            return ele<x↵
            (↵
                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 Custom_Unsigned_int128bool↵
        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 Custom_Unsigned_int128bool↵
        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 Custom_Unsigned_int128bool↵
        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↵
            });↵
        }↵
↵
        template<typename _Tp>↵
        friend Custom_Unsigned_int128↵
        operator-(const _Tp& x,const Custom_Unsigned_int128& ele){↵
            return Custom_Unsigned_int128↵
            {↵
                -ele.higherInt+↵
                detect_overflow_minus(x,ele.lowerInt),↵
                x-ele.lowerInt↵
            };↵
        }↵
↵
        Custom_Unsigned_int128↵
        operator-(const Custom_Unsigned_int128& x)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↵
            {(↵
                higherInt0ull,↵
                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+=pr<<=1;↵
            }↵
            return ret;↵
        }↵
↵
        template<typename _Tp>↵
        Custom_Unsigned_int128↵
        friend operator*(const _Tp& x,const Custom_Unsigned_int128& ele){↵
            return ele*x;↵
        }↵
↵
        template<typename _Tp>↵
        Custom_Unsigned_int128&↵
        operator*=(const _Tp& x){↵
            return *this=*this*x;↵
        }↵
↵
    };↵
↵
}↵
↵
void test(){↵
    RedshiftShine::Custom_Unsigned_int128 ci(1,1Custom_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);↵
    aputo [a,b]=ci.base_access();↵
    std::printf("%llu %llu\n",a,b);char(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();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Hope it helps.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English shiny_shine 2024-03-22 15:45:49 21 Revision 3 / Alpha version
en3 English shiny_shine 2024-03-15 09:14:17 3016 Revision 2 / Alpha version
en2 English shiny_shine 2024-03-14 09:11:41 10726 Revision 1
en1 English shiny_shine 2024-03-13 12:59:06 4429 Initial revision (published)