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

额外减小

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

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

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

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

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

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

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <typeinfo>
   
4. #include <bitset>
   
5. #include <string>
   
6. #include <utility>
   
7. #include <algorithm>
   
8. using namespace std;
   
9. 
   
10. const int _bits=512;
    
11. 
    
12. // 准备写一个高精度类。用 std::bitset
    
13. 
    
14. inline int to_int(bitset<_bits> x)
    
15. {
    
16.         int maxn=min(32,_bits),ans=0;
    
17.         for(int i=0,j=1;i<maxn;i++,j*=2)
    
18.         {
    
19.                 if(x[i])
    
20.                 ans+=j;
    
21.         }
    
22.         return ans;
    
23. }
    
24. 
    
25. inline int highest_true(bitset<_bits> x)
    
26. {
    
27.         for(int i=_bits-1;i>=0;i--)
    
28.         {
    
29.                 if(x[i])return i;
    
30.         }
    
31.         return -1;
    
32. }
    
33. 
    
34. inline bool operator>(bitset<_bits> x,bitset<_bits> y)
    
35. {
    
36.         for(int i=_bits-1;i>=0;i--)
    
37.         {
    
38.                 if(x[i]&&!y[i])
    
39.                 return true;
    
40.                 if(!x[i]&&y[i])
    
41.                 return false;
    
42.         }
    
43.         return false;
    
44. }
    
45. 
    
46. inline bool operator<(bitset<_bits> x,bitset<_bits> y)
    
47. {
    
48.         for(int i=_bits-1;i>=0;i--)
    
49.         {
    
50.                 if(x[i]&&!y[i])
    
51.                 return false;
    
52.                 if(!x[i]&&y[i])
    
53.                 return true;
    
54.         }
    
55.         return false;
    
56. }
    
57. 
    
58. inline bool operator>=(bitset<_bits> x,bitset<_bits> y)
    
59. {
    
60.         return !(x<y);
    
61. }
    
62. 
    
63. inline bool operator<=(bitset<_bits> x,bitset<_bits> y)
    
64. {
    
65.         return !(x>y);
    
66. }
    
67. 
    
68. inline bitset<_bits> operator+(bitset<_bits> x,bitset<_bits> y)
    
69. {
    
70.         bool c;
    
71.         bitset<_bits> ans;
    
72.         ans[0]=x[0]^y[0];
    
73.         c=x[0]&&y[0];
    
74.         for(int i=1;i<_bits;i++)
    
75.         {
    
76.                 ans[i]=(x[i]&&y[i]&&c)||(x[i]&&!y[i]&&!c)||(!x[i]&&y[i]&&!c)||(!x[i]&&!y[i]&&c);
    
77.                 c=(x[i]&&y[i]&&c)||(x[i]&&y[i]&&!c)||(!x[i]&&y[i]&&c)||(x[i]&&!y[i]&&c);
    
78.         }
    
79.         return ans;
    
80. }
    
81. 
    
82. inline bitset<_bits> operator-(bitset<_bits> x,bitset<_bits> y)
    
83. {
    
84.         return x+~y+(bitset<_bits>)1;
    
85. }
    
86. 
    
87. inline bitset<_bits> operator*(bitset<_bits> x,bitset<_bits> y)
    
88. {
    
89.         bitset<_bits> tmpx=x,tmpy=y,ans;
    
90.         while(tmpx.any())
    
91.         {
    
92.                 if(tmpx[0])
    
93.                 {
    
94.                         ans=ans+tmpy;
    
95.                 }
    
96.                 tmpx>>=1;
    
97.                 tmpy<<=1;
    
98.         }
    
99.         return ans;
    
100. }
     
101. 
     
102. inline pair< bitset<_bits> , bitset<_bits> > divmod(bitset<_bits> x,bitset<_bits> y)
     
103. {
     
104.         int ht1=highest_true(x),ht2=highest_true(y);
     
105.         pair< bitset<_bits>,bitset<_bits> > ans_pair;
     
106.         if(ht1<ht2)
     
107.         {
     
108.                 ans_pair.first=0;
     
109.                 ans_pair.second=x;
     
110.                 return ans_pair;
     
111.         }
     
112.         bitset<_bits> tmpx=x,tmpy=y<<(ht1-ht2),div;
     
113.         while(1)
     
114.         {
     
115.                 //cout<<tmpx<<endl<<tmpy<<endl<<div<<endl<<endl;
     
116.                
     
117.                 div[0]=(tmpx>=tmpy);
     
118.                
     
119.                
     
120.                 if(div[0])
     
121.                 tmpx=tmpx-tmpy;
     
122.                 if(tmpx<y)
     
123.                 break;
     
124.                 div<<=1;
     
125.                 tmpy>>=1;
     
126.         }
     
127.         div<<=(highest_true(tmpy)-ht2);
     
128.         //cout<<highest_true(tmpy)<<' '<<ht2<<endl;
     
129.         ans_pair.first=div;
     
130.         ans_pair.second=tmpx;
     
131.         //cout<<endl<<"div: "<<div<<" "<<(highest_true(tmpy)-ht2)<<endl;
     
132.         return ans_pair;
     
133. }
     
134. 
     
135. inline bitset<_bits> operator/(bitset<_bits> x,bitset<_bits> y)
     
136. {
     
137.         return divmod(x,y).first;
     
138. }
     
139. 
     
140. inline bitset<_bits> operator%(bitset<_bits> x,bitset<_bits> y)
     
141. {
     
142.         return divmod(x,y).second;
     
143. }
     
144. 
     
145. inline bitset<_bits>& operator+=(bitset<_bits> & x,const bitset<_bits> y)
     
146. {
     
147.         return x=x+y;
     
148. }
     
149. 
     
150. inline bitset<_bits>& operator-=(bitset<_bits> & x,const bitset<_bits> y)
     
151. {
     
152.         return x=x-y;
     
153. }
     
154. 
     
155. bitset<_bits>& operator*=(bitset<_bits> & x,const bitset<_bits> y)
     
156. {
     
157.         return x=x*y;
     
158. }
     
159. 
     
160. bitset<_bits>& operator/=(bitset<_bits> & x,const bitset<_bits> y)
     
161. {
     
162.         return x=x/y;
     
163. }
     
164. 
     
165. bitset<_bits>& operator%=(bitset<_bits> & x,const bitset<_bits> y)
     
166. {
     
167.         return x=x%y;
     
168. }
     
169. 
     
170. inline void fast_read(bitset<_bits> &x)
     
171. {
     
172.         x.reset();
     
173.         bool isneg=false;
     
174.         char ch=getchar();
     
175.         while(!isdigit(ch))
     
176.         {
     
177.                 if(ch=='-')isneg=true;
     
178.                 ch=getchar();
     
179.         }
     
180.         while(isdigit(ch))
     
181.         {
     
182.                 x=(x<<3)+(x<<1)+(ch^48);
     
183.                 ch=getchar();
     
184.         }
     
185.         if(isneg)x=~x+1;
     
186. }
     
187. 
     
188. inline void fast_print(const bitset<_bits> &x)
     
189. {
     
190.         if(x>9)
     
191.         fast_print(x/10);
     
192.         putchar(to_int(x%10)+48);
     
193. }
     
194. 
     
195. inline void in_int(bitset<_bits> &x)
     
196. {
     
197.         int a;
     
198.         cin>>a;
     
199.         x=a;
     
200. }
     
201. 
     
202. inline void out_int(bitset<_bits> &x)
     
203. {
     
204.         string str=x.to_string();
     
205.        
     
206.         int ans=0,l=str.length();
     
207.         for(int i=l-1,j=1;i>=0;i--,j*=2)
     
208.         {
     
209.                 if(str[i]=='1')ans+=j;
     
210.         }
     
211.         cout<<"output : "<<ans<<endl;
     
212. }
     
213. 
     
214. int main()
     
215. {
     
216.         bitset<_bits> a1;
     
217.         while(1)
     
218.         {
     
219.                 fast_read(a1);
     
220.                 fast_print(a1);
     
221.                 putchar('\n');
     
222.         }
     
223. }

复制代码

Mike_python小

额外减小

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