论坛 › C\C++交流 › 效率极低的高精度算法（二进制操作，bitset）

额外减小 发表于 2023-10-14 00:48:41

效率极低的高精度算法（二进制操作，bitset）

本帖最后由 额外减小 于 2023-10-14 00:57 编辑

rt。
框架已经写好了。接下来就是一些内置函数了。

代码中实现了高精度加减乘除膜，还有快读快输。可以自行添加其他功能。

代码中是512位二进制存储，到十进制能存155位，相当多了。

你们可以自己扩展到1024bit(309十进制位),65536bit(19729十进制位)。多大的高精度都能用。

这就是传说中的用时间换空间。

二进制计算是完全没有空间浪费的。你不管是普通高精（int存10种数字）或者压位高精都是有很大的内存浪费的。
所以我们在不是算法竞赛的时候一定要用时间换空间啊！（bushi



#include <iostream>
#include <cstdio>
#include <typeinfo>
#include <bitset>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;

const int _bits=512;

// 准备写一个高精度类。用 std::bitset

inline int to_int(bitset<_bits> x)
{
        int maxn=min(32,_bits),ans=0;
        for(int i=0,j=1;i<maxn;i++,j*=2)
        {
                if(x)
                ans+=j;
        }
        return ans;
}

inline int highest_true(bitset<_bits> x)
{
        for(int i=_bits-1;i>=0;i--)
        {
                if(x)return i;
        }
        return -1;
}

inline bool operator>(bitset<_bits> x,bitset<_bits> y)
{
        for(int i=_bits-1;i>=0;i--)
        {
                if(x&&!y)
                return true;
                if(!x&&y)
                return false;
        }
        return false;
}

inline bool operator<(bitset<_bits> x,bitset<_bits> y)
{
        for(int i=_bits-1;i>=0;i--)
        {
                if(x&&!y)
                return false;
                if(!x&&y)
                return true;
        }
        return false;
}

inline bool operator>=(bitset<_bits> x,bitset<_bits> y)
{
        return !(x<y);
}

inline bool operator<=(bitset<_bits> x,bitset<_bits> y)
{
        return !(x>y);
}

inline bitset<_bits> operator+(bitset<_bits> x,bitset<_bits> y)
{
        bool c;
        bitset<_bits> ans;
        ans=x^y;
        c=x&&y;
        for(int i=1;i<_bits;i++)
        {
                ans=(x&&y&&c)||(x&&!y&&!c)||(!x&&y&&!c)||(!x&&!y&&c);
                c=(x&&y&&c)||(x&&y&&!c)||(!x&&y&&c)||(x&&!y&&c);
        }
        return ans;
}

inline bitset<_bits> operator-(bitset<_bits> x,bitset<_bits> y)
{
        return x+~y+(bitset<_bits>)1;
}

inline bitset<_bits> operator*(bitset<_bits> x,bitset<_bits> y)
{
        bitset<_bits> tmpx=x,tmpy=y,ans;
        while(tmpx.any())
        {
                if(tmpx)
                {
                        ans=ans+tmpy;
                }
                tmpx>>=1;
                tmpy<<=1;
        }
        return ans;
}

inline pair< bitset<_bits> , bitset<_bits> > divmod(bitset<_bits> x,bitset<_bits> y)
{
        int ht1=highest_true(x),ht2=highest_true(y);
        pair< bitset<_bits>,bitset<_bits> > ans_pair;
        if(ht1<ht2)
        {
                ans_pair.first=0;
                ans_pair.second=x;
                return ans_pair;
        }
        bitset<_bits> tmpx=x,tmpy=y<<(ht1-ht2),div;
        while(1)
        {
                //cout<<tmpx<<endl<<tmpy<<endl<<div<<endl<<endl;
               
                div=(tmpx>=tmpy);
               
               
                if(div)
                tmpx=tmpx-tmpy;
                if(tmpx<y)
                break;
                div<<=1;
                tmpy>>=1;
        }
        div<<=(highest_true(tmpy)-ht2);
        //cout<<highest_true(tmpy)<<' '<<ht2<<endl;
        ans_pair.first=div;
        ans_pair.second=tmpx;
        //cout<<endl<<"div: "<<div<<" "<<(highest_true(tmpy)-ht2)<<endl;
        return ans_pair;
}

inline bitset<_bits> operator/(bitset<_bits> x,bitset<_bits> y)
{
        return divmod(x,y).first;
}

inline bitset<_bits> operator%(bitset<_bits> x,bitset<_bits> y)
{
        return divmod(x,y).second;
}

inline bitset<_bits>& operator+=(bitset<_bits> & x,const bitset<_bits> y)
{
        return x=x+y;
}

inline bitset<_bits>& operator-=(bitset<_bits> & x,const bitset<_bits> y)
{
        return x=x-y;
}

bitset<_bits>& operator*=(bitset<_bits> & x,const bitset<_bits> y)
{
        return x=x*y;
}

bitset<_bits>& operator/=(bitset<_bits> & x,const bitset<_bits> y)
{
        return x=x/y;
}

bitset<_bits>& operator%=(bitset<_bits> & x,const bitset<_bits> y)
{
        return x=x%y;
}

inline void fast_read(bitset<_bits> &x)
{
        x.reset();
        bool isneg=false;
        char ch=getchar();
        while(!isdigit(ch))
        {
                if(ch=='-')isneg=true;
                ch=getchar();
        }
        while(isdigit(ch))
        {
                x=(x<<3)+(x<<1)+(ch^48);
                ch=getchar();
        }
        if(isneg)x=~x+1;
}

inline void fast_print(const bitset<_bits> &x)
{
        if(x>9)
        fast_print(x/10);
        putchar(to_int(x%10)+48);
}

inline void in_int(bitset<_bits> &x)
{
        int a;
        cin>>a;
        x=a;
}

inline void out_int(bitset<_bits> &x)
{
        string str=x.to_string();
       
        int ans=0,l=str.length();
        for(int i=l-1,j=1;i>=0;i--,j*=2)
        {
                if(str=='1')ans+=j;
        }
        cout<<"output : "<<ans<<endl;
}

int main()
{
        bitset<_bits> a1;
        while(1)
        {
                fast_read(a1);
                fast_print(a1);
                putchar('\n');
        }
}

Mike_python小 发表于 2023-10-14 10:41:18

{:10_254:}

额外减小 发表于 2023-10-14 18:58:04

Mike_python小 发表于 2023-10-14 10:41


{:10_254:}

查看完整版本: 效率极低的高精度算法（二进制操作，bitset）