1 //////////////////////////////////////////////////////////////////////////////
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are free to incorporate any part of ADLib and Prop into
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
25 #ifndef variable_precision_integer_h
26 #define variable_precision_integer_h
28 //////////////////////////////////////////////////////////////////////
29 // Class BigInt is a variable precision integer type.
30 //////////////////////////////////////////////////////////////////////
34 #include <AD/generic/generic.h> // Generic definitions
39 //////////////////////////////////////////////////////////////////////
40 // BigInt is represented in a sign/magnitude format.
41 // For stupid reasons, we'll have to export this definition to
43 //////////////////////////////////////////////////////////////////////
46 typedef unsigned short Digit
; // 16 bits per digit
47 typedef unsigned long Unit
; // 32 bits for computation
49 int sign
; // sign of the number: 0, +1, or -1.
50 int len
; // number of digits currently used
51 int capacity
; // number of digits available in array
52 Digit digits
[1]; // array of digits; the least significant is at index 0
54 //////////////////////////////////////////////////////////////////////
55 // Internal memory manager
56 //////////////////////////////////////////////////////////////////////
57 void * operator new (size_t, int);
58 void operator delete (void *);
60 //////////////////////////////////////////////////////////////////////
61 // These procedures work on the internal representation and
62 // are the ones actually doing the dirty work.
63 //////////////////////////////////////////////////////////////////////
64 friend a_BigInt
* copy(a_BigInt
*, const a_BigInt
*);
65 friend a_BigInt
* copy(a_BigInt
*, long, int = 1);
66 friend a_BigInt
* neg(a_BigInt
*, const a_BigInt
*);
67 friend a_BigInt
* addsub(a_BigInt
*, const a_BigInt
*, const a_BigInt
*, Bool
);
68 friend a_BigInt
* addsub(a_BigInt
*, const a_BigInt
*, long, Bool
);
69 friend a_BigInt
* addsub(a_BigInt
*, long, const a_BigInt
*, Bool
);
70 friend a_BigInt
* mul(a_BigInt
*, const a_BigInt
*, const a_BigInt
*);
71 friend a_BigInt
* mul(a_BigInt
*, const a_BigInt
*, long);
72 friend a_BigInt
* div(a_BigInt
*, const a_BigInt
*, const a_BigInt
*);
73 friend a_BigInt
* div(a_BigInt
*, const a_BigInt
*, long);
74 friend a_BigInt
* div(a_BigInt
*, long, const a_BigInt
*);
75 friend a_BigInt
* mod(a_BigInt
*, const a_BigInt
*, const a_BigInt
*);
76 friend a_BigInt
* mod(a_BigInt
*, const a_BigInt
*, long);
77 friend a_BigInt
* mod(a_BigInt
*, long, const a_BigInt
*);
78 friend a_BigInt
* andor(a_BigInt
*, const a_BigInt
*, const a_BigInt
*,char);
79 friend a_BigInt
* andor(a_BigInt
*, const a_BigInt
*, long, char);
80 friend a_BigInt
* bitnot(a_BigInt
*, const a_BigInt
*);
81 friend a_BigInt
* shift(a_BigInt
*, const a_BigInt
*, const a_BigInt
*, int);
82 friend a_BigInt
* shift(a_BigInt
*, const a_BigInt
*, long, int);
83 friend a_BigInt
* shift(a_BigInt
*, long, const a_BigInt
*, int);
84 friend int cmp(const a_BigInt
*, const a_BigInt
*);
85 friend int cmp(const a_BigInt
*, long);
90 //////////////////////////////////////////////////////////////////////
91 // A BigInt is just a pointer to its representation.
92 // Since zero is a common value and used for initialization
93 // a special zero value is provided. This is hidden for
95 //////////////////////////////////////////////////////////////////////
96 static a_BigInt
* zero
;
101 BigInt(a_BigInt
* d
) : D(d
) {} // for internal use only
103 ////////////////////////////////////////////////////////////////////////
105 ////////////////////////////////////////////////////////////////////////
106 static void (*error_handler
)(const char []);
108 ////////////////////////////////////////////////////////////////////////
109 // Constructors and destructors
110 ////////////////////////////////////////////////////////////////////////
112 inline BigInt() : D(zero
) { } // i.e. BigInt n;
113 inline BigInt(const BigInt
& n
) { D
= copy(0,n
); } // i.e. BigInt n = m;
114 inline BigInt(int n
) { D
= copy(0,n
); } // i.e. BigInt n = 1;
115 BigInt(const char *); // i.e. BigInt n = "12345";
116 inline ~BigInt() { delete D
; }
118 ////////////////////////////////////////////////////////////////////////
119 // Conversions: double() converts a BigInt to a double
120 // Conversions: long() converts a BigInt to a long with truncation
121 ////////////////////////////////////////////////////////////////////////
122 operator double () const;
124 ////////////////////////////////////////////////////////////////////////
126 ////////////////////////////////////////////////////////////////////////
127 inline BigInt
& operator = (const BigInt
& n
)
128 { D
= copy(D
,n
.D
); return *this; }
129 inline BigInt
& operator = (const int n
)
130 { D
= copy(D
,n
); return *this; }
131 BigInt
& operator = (const char *);
133 ////////////////////////////////////////////////////////////////////////
134 // Attributes of a BigInt
135 ////////////////////////////////////////////////////////////////////////
136 inline int sign () const { return D
->sign
; }
137 inline Bool
isEven () const { return (D
->digits
[0] & 1) == 0; }
138 inline Bool
isOdd () const { return D
->digits
[0] & 1; }
139 inline int operator [] (int i
) const { return D
->digits
[i
/16] & (1 << (i
& 15)); }
140 inline int radix () const { return 1 << (8 * sizeof(a_BigInt::Digit
)); }
141 inline int length () const;
143 ////////////////////////////////////////////////////////////////////////
144 // Arithmetic operators
145 ////////////////////////////////////////////////////////////////////////
146 friend BigInt
abs (const BigInt
&);
147 friend BigInt
operator - (const BigInt
&);
148 friend BigInt
operator + (const BigInt
&, const BigInt
&);
149 friend BigInt
operator + (int, const BigInt
&);
150 friend BigInt
operator + (const BigInt
&, int);
151 friend BigInt
operator - (const BigInt
&, const BigInt
&);
152 friend BigInt
operator - (int, const BigInt
&);
153 friend BigInt
operator - (const BigInt
&, int);
154 friend BigInt
operator * (const BigInt
&, const BigInt
&);
155 friend BigInt
operator * (int, const BigInt
&);
156 friend BigInt
operator * (const BigInt
&, int);
157 friend BigInt
operator / (const BigInt
&, const BigInt
&);
158 friend BigInt
operator / (int, const BigInt
&);
159 friend BigInt
operator / (const BigInt
&, int);
160 friend BigInt
operator % (const BigInt
&, const BigInt
&);
161 friend BigInt
operator % (int, const BigInt
&);
162 friend BigInt
operator % (const BigInt
&, int);
163 friend void div_mod (const BigInt
&, const BigInt
&, BigInt
&, BigInt
&);
164 friend BigInt
operator << (const BigInt
&, const BigInt
&);
165 friend BigInt
operator << (int, const BigInt
&);
166 friend BigInt
operator << (const BigInt
&, int);
167 friend BigInt
operator >> (const BigInt
&, const BigInt
&);
168 friend BigInt
operator >> (int, const BigInt
&);
169 friend BigInt
operator >> (const BigInt
&, int);
170 friend BigInt
operator | (const BigInt
&, const BigInt
&);
171 friend BigInt
operator | (int, const BigInt
&);
172 friend BigInt
operator | (const BigInt
&, int);
173 friend BigInt
operator & (const BigInt
&, const BigInt
&);
174 friend BigInt
operator & (int, const BigInt
&);
175 friend BigInt
operator & (const BigInt
&, int);
176 friend BigInt
operator ^ (const BigInt
&, const BigInt
&);
177 friend BigInt
operator ^ (int, const BigInt
&);
178 friend BigInt
operator ^ (const BigInt
&, int);
179 friend BigInt
not (const BigInt
&);
180 friend unsigned int hash (const BigInt
&);
182 ///////////////////////////////////////////////////////////
183 // Single bit operations
184 ///////////////////////////////////////////////////////////
185 inline int nthBit(int nth
) const { return D
->digits
[nth
/16] & (1 << (nth
& 15)); }
186 inline void setBit(int nth
) { D
->digits
[nth
/16] |= (1 << (nth
& 15)); }
187 inline void clearBit(int nth
) { D
->digits
[nth
/16] &= ~(1 << (nth
& 15)); }
189 ///////////////////////////////////////////////////////////
190 // In place operations are inlined for efficiency
191 ///////////////////////////////////////////////////////////
192 inline void operator ++ (int) { D
= addsub(D
,D
,1,false); }
193 inline void operator -- (int) { D
= addsub(D
,D
,1,true); }
194 inline void operator ++ () { D
= addsub(D
,D
,1,false); }
195 inline void operator -- () { D
= addsub(D
,D
,1,true); }
197 inline void abs () { if (D
->sign
== -1) D
= neg(D
,D
); }
198 inline void negate () { D
= neg(D
,D
); }
199 inline void not() { D
= bitnot(D
,D
); }
200 inline void operator += (const BigInt
& n
) { D
= addsub(D
,D
,n
.D
,false); }
201 inline void operator -= (const BigInt
& n
) { D
= addsub(D
,D
,n
.D
,true); }
202 inline void operator *= (const BigInt
& n
) { D
= mul(D
,D
,n
.D
); }
203 inline void operator /= (const BigInt
& n
) { D
= div(D
,D
,n
.D
); }
204 inline void operator %= (const BigInt
& n
) { D
= mod(D
,D
,n
.D
); }
205 inline void operator <<=(const BigInt
& n
) { D
= shift(D
,D
,n
.D
,1); }
206 inline void operator >>=(const BigInt
& n
) { D
= shift(D
,D
,n
.D
,-1); }
207 inline void operator |= (const BigInt
& n
) { D
= andor(D
,D
,n
.D
,'|'); }
208 inline void operator &= (const BigInt
& n
) { D
= andor(D
,D
,n
.D
,'&'); }
209 inline void operator ^= (const BigInt
& n
) { D
= andor(D
,D
,n
.D
,'^'); }
210 inline void operator += (int n
) { D
= addsub(D
,D
,n
,false); }
211 inline void operator -= (int n
) { D
= addsub(D
,D
,n
,true); }
212 inline void operator *= (int n
) { D
= mul(D
,D
,n
); }
213 inline void operator /= (int n
) { D
= div(D
,D
,n
); }
214 inline void operator %= (int n
) { D
= mod(D
,D
,n
); }
215 inline void operator <<=(int n
) { D
= shift(D
,D
,n
,1); }
216 inline void operator >>=(int n
) { D
= shift(D
,D
,n
,-1); }
217 inline void operator |= (int n
) { D
= andor(D
,D
,n
,'|'); }
218 inline void operator &= (int n
) { D
= andor(D
,D
,n
,'&'); }
219 inline void operator ^= (int n
) { D
= andor(D
,D
,n
,'^'); }
221 ///////////////////////////////////////////////////////////
222 // Comparisons are inlined for efficiency
223 ///////////////////////////////////////////////////////////
224 inline friend Bool
operator == (const BigInt
& a
, const BigInt
& b
) { return cmp(a
.D
,b
.D
) == 0; }
225 inline friend Bool
operator == (const BigInt
& a
, int b
) { return cmp(a
.D
,b
) == 0; }
226 inline friend Bool
operator == (int a
, const BigInt
& b
) { return cmp(b
.D
,a
) == 0; }
227 inline friend Bool
operator != (const BigInt
& a
, const BigInt
& b
) { return cmp(a
.D
,b
.D
) != 0; }
228 inline friend Bool
operator != (const BigInt
& a
, int b
) { return cmp(a
.D
,b
) != 0; }
229 inline friend Bool
operator != (int a
, const BigInt
& b
) { return cmp(b
.D
,a
) != 0; }
230 inline friend Bool
operator > (const BigInt
& a
, const BigInt
& b
) { return cmp(a
.D
,b
.D
) > 0; }
231 inline friend Bool
operator > (const BigInt
& a
, int b
) { return cmp(a
.D
,b
) > 0; }
232 inline friend Bool
operator > (int a
, const BigInt
& b
) { return cmp(b
.D
,a
) <= 0; }
233 inline friend Bool
operator < (const BigInt
& a
, const BigInt
& b
) { return cmp(a
.D
,b
.D
) < 0; }
234 inline friend Bool
operator < (const BigInt
& a
, int b
) { return cmp(a
.D
,b
) < 0; }
235 inline friend Bool
operator < (int a
, const BigInt
& b
) { return cmp(b
.D
,a
) >= 0; }
236 inline friend Bool
operator >= (const BigInt
& a
, const BigInt
& b
) { return cmp(a
.D
,b
.D
) >= 0; }
237 inline friend Bool
operator >= (const BigInt
& a
, int b
) { return cmp(a
.D
,b
) >= 0; }
238 inline friend Bool
operator >= (int a
, const BigInt
& b
) { return cmp(b
.D
,a
) < 0; }
239 inline friend Bool
operator <= (const BigInt
& a
, const BigInt
& b
) { return cmp(a
.D
,b
.D
) <= 0; }
240 inline friend Bool
operator <= (const BigInt
& a
, int b
) { return cmp(a
.D
,b
) <= 0; }
241 inline friend Bool
operator <= (int a
, const BigInt
& b
) { return cmp(b
.D
,a
) > 0; }
243 ///////////////////////////////////////////////////////////
244 // Miscellaneous arithmetic
245 ///////////////////////////////////////////////////////////
246 friend BigInt
gcd (BigInt
, BigInt
);
247 friend BigInt
sqrt (const BigInt
&);
248 friend BigInt
pow (const BigInt
&, const BigInt
&);
249 friend BigInt
pow_mod (const BigInt
&, const BigInt
&, const BigInt
&);
250 friend BigInt
make_random (const BigInt
& limit
);
252 ///////////////////////////////////////////////////////////
253 // I/O and string conversion
254 ///////////////////////////////////////////////////////////
255 char * makeString (char [], size_t length
= 1024,
256 unsigned int base
= 10) const;
257 int parseString (const char *, unsigned int base
= 10);
258 friend ostream
& operator << (ostream
&, const BigInt
&);
259 friend istream
& operator >> (istream
&, BigInt
&);
262 ///////////////////////////////////////////////////////////////////////////
263 // Binary and unary operators are inlined for efficiency.
264 // G++ has a non-standard syntax for faster returning of inline values
265 // that eliminate unnecessary copying. We'll provided a version with this
266 // special optimization and one without for non G++ compilers.
267 ///////////////////////////////////////////////////////////////////////////
268 // #if defined(__GNUG__) && ! defined(NO_NRV)
270 inline BigInt
abs (const BigInt
& a
) return r
271 { r
.D
= a
.D
->sign
== -1 ? neg(r
.D
,a
.D
) : copy(r
.D
,a
.D
); }
272 inline BigInt
operator - (const BigInt
& a
) return r
273 { r
.D
= neg(r
.D
,a
.D
); }
274 inline BigInt
operator + (const BigInt
& a
, const BigInt
& b
) return r
275 { r
.D
= addsub(r
.D
,a
.D
,b
.D
,false); }
276 inline BigInt
operator + (long a
, const BigInt
& b
) return r
277 { r
.D
= addsub(r
.D
,b
.D
,a
,false); }
278 inline BigInt
operator + (const BigInt
& a
, long b
) return r
279 { r
.D
= addsub(r
.D
,a
.D
,b
,false); }
280 inline BigInt
operator - (const BigInt
& a
, const BigInt
& b
) return r
281 { r
.D
= addsub(r
.D
,a
.D
,b
.D
,true); }
282 inline BigInt
operator - (long a
, const BigInt
& b
) return r
283 { r
.D
= addsub(r
.D
,a
,b
.D
,true); }
284 inline BigInt
operator - (const BigInt
& a
, long b
) return r
285 { r
.D
= addsub(r
.D
,a
.D
,b
,true); }
286 inline BigInt
operator * (const BigInt
& a
, const BigInt
& b
) return r
287 { r
.D
= mul(r
.D
,a
.D
,b
.D
); }
288 inline BigInt
operator * (long a
, const BigInt
& b
) return r
289 { r
.D
= mul(r
.D
,b
.D
,a
); }
290 inline BigInt
operator * (const BigInt
& a
, long b
) return r
291 { r
.D
= mul(r
.D
,a
.D
,b
); }
292 inline BigInt
operator / (const BigInt
& a
, const BigInt
& b
) return r
293 { r
.D
= div(r
.D
,a
.D
,b
.D
); }
294 inline BigInt
operator / (long a
, const BigInt
& b
) return r
295 { r
.D
= div(r
.D
,a
,b
.D
); }
296 inline BigInt
operator / (const BigInt
& a
, long b
) return r
297 { r
.D
= div(r
.D
,a
.D
,b
); }
298 inline BigInt
operator % (const BigInt
& a
, const BigInt
& b
) return r
299 { r
.D
= mod(r
.D
,a
.D
,b
.D
); }
300 inline BigInt
operator % (long a
, const BigInt
& b
) return r
301 { r
.D
= mod(r
.D
,a
,b
.D
); }
302 inline BigInt
operator % (const BigInt
& a
, long b
) return r
303 { r
.D
= mod(r
.D
,a
.D
,b
); }
304 inline BigInt
operator << (const BigInt
& a
, const BigInt
& b
) return r
305 { r
.D
= shift(r
.D
,a
.D
,b
.D
,1); }
306 inline BigInt
operator << (long a
, const BigInt
& b
) return r
307 { r
.D
= shift(r
.D
,a
,b
.D
,1); }
308 inline BigInt
operator << (const BigInt
& a
, long b
) return r
309 { r
.D
= shift(r
.D
,a
.D
,b
,1); }
310 inline BigInt
operator >> (const BigInt
& a
, const BigInt
& b
) return r
311 { r
.D
= shift(r
.D
,a
.D
,b
.D
,-1); }
312 inline BigInt
operator >> (long a
, const BigInt
& b
) return r
313 { r
.D
= shift(r
.D
,a
,b
.D
,-1); }
314 inline BigInt
operator >> (const BigInt
& a
, long b
) return r
315 { r
.D
= shift(r
.D
,a
.D
,b
,-1); }
316 inline BigInt
operator | (const BigInt
& a
, const BigInt
& b
) return r
317 { r
.D
= andor(r
.D
,a
.D
,b
.D
,'|'); }
318 inline BigInt
operator | (long a
, const BigInt
& b
) return r
319 { r
.D
= andor(r
.D
,b
.D
,a
,'|'); }
320 inline BigInt
operator | (const BigInt
& a
, long b
) return r
321 { r
.D
= andor(r
.D
,a
.D
,b
,'|'); }
322 inline BigInt
operator & (const BigInt
& a
, const BigInt
& b
) return r
323 { r
.D
= andor(r
.D
,a
.D
,b
.D
,'&'); }
324 inline BigInt
operator & (long a
, const BigInt
& b
) return r
325 { r
.D
= andor(r
.D
,b
.D
,a
,'&'); }
326 inline BigInt
operator & (const BigInt
& a
, long b
) return r
327 { r
.D
= andor(r
.D
,a
.D
,b
,'&'); }
328 inline BigInt
operator ^ (const BigInt
& a
, const BigInt
& b
) return r
329 { r
.D
= andor(r
.D
,a
.D
,b
.D
,'^'); }
330 inline BigInt
operator ^ (long a
, const BigInt
& b
) return r
331 { r
.D
= andor(r
.D
,b
.D
,a
,'^'); }
332 inline BigInt
operator ^ (const BigInt
& a
, long b
) return r
333 { r
.D
= andor(r
.D
,a
.D
,b
,'^'); }
334 inline BigInt
not (const BigInt
& a
) return r
335 { r
.D
= bitnot(r
.D
,a
.D
); }
337 inline BigInt
abs (const BigInt
& a
)
338 { return BigInt(a
.D
->sign
== -1 ? neg(0,a
.D
) : copy(0,a
.D
)); }
339 inline BigInt
operator - (const BigInt
& a
)
340 { return BigInt(neg(0,a
.D
)); }
341 inline BigInt
operator + (const BigInt
& a
, const BigInt
& b
) { return BigInt(addsub(0,a
.D
,b
.D
,false)); }
342 inline BigInt
operator + (long a
, const BigInt
& b
) { return BigInt(addsub(0,b
.D
,a
,false)); }
343 inline BigInt
operator + (const BigInt
& a
, long b
) { return BigInt(addsub(0,a
.D
,b
,false)); }
344 inline BigInt
operator - (const BigInt
& a
, const BigInt
& b
) { return BigInt(addsub(0,a
.D
,b
.D
,true)); }
345 inline BigInt
operator - (int a
, const BigInt
& b
) { return BigInt(addsub(0,a
,b
.D
,true)); }
346 inline BigInt
operator - (const BigInt
& a
, int b
) { return BigInt(addsub(0,a
.D
,b
,true)); }
347 inline BigInt
operator * (const BigInt
& a
, const BigInt
& b
) { return BigInt(mul(0,a
.D
,b
.D
)); }
348 inline BigInt
operator * (long a
, const BigInt
& b
) { return BigInt(mul(0,b
.D
,a
)); }
349 inline BigInt
operator * (const BigInt
& a
, int b
) { return BigInt(mul(0,a
.D
,b
)); }
350 inline BigInt
operator / (const BigInt
& a
, const BigInt
& b
) { return BigInt(div(0,a
.D
,b
.D
)); }
351 inline BigInt
operator / (int a
, const BigInt
& b
) { return BigInt(div(0,a
,b
.D
)); }
352 inline BigInt
operator / (const BigInt
& a
, long b
) { return BigInt(div(0,a
.D
,b
)); }
353 inline BigInt
operator % (const BigInt
& a
, const BigInt
& b
) { return BigInt(mod(0,a
.D
,b
.D
)); }
354 inline BigInt
operator % (int a
, const BigInt
& b
) { return BigInt(mod(0,a
,b
.D
)); }
355 inline BigInt
operator % (const BigInt
& a
, int b
) { return BigInt(mod(0,a
.D
,b
)); }
356 inline BigInt
operator << (const BigInt
& a
, const BigInt
& b
) { return BigInt(shift(0,a
.D
,b
.D
,1)); }
357 inline BigInt
operator << (int a
, const BigInt
& b
) { return BigInt(shift(0,a
,b
.D
,1)); }
358 inline BigInt
operator << (const BigInt
& a
, int b
) { return BigInt(shift(0,a
.D
,b
,1)); }
359 inline BigInt
operator >> (const BigInt
& a
, const BigInt
& b
) { return BigInt(shift(0,a
.D
,b
.D
,-1)); }
360 inline BigInt
operator >> (int a
, const BigInt
& b
) { return BigInt(shift(0,a
,b
.D
,-1)); }
361 inline BigInt
operator >> (const BigInt
& a
, int b
) { return BigInt(shift(0,a
.D
,b
,-1)); }
362 inline BigInt
operator | (const BigInt
& a
, const BigInt
& b
) { return BigInt(andor(0,a
.D
,b
.D
,'|')); }
363 inline BigInt
operator | (long a
, const BigInt
& b
) { return BigInt(andor(0,b
.D
,a
,'|')); }
364 inline BigInt
operator | (const BigInt
& a
, long b
) { return BigInt(andor(0,a
.D
,b
,'|')); }
365 inline BigInt
operator & (const BigInt
& a
, const BigInt
& b
) { return BigInt(andor(0,a
.D
,b
.D
,'&')); }
366 inline BigInt
operator & (long a
, const BigInt
& b
) { return BigInt(andor(0,b
.D
,a
,'&')); }
367 inline BigInt
operator & (const BigInt
& a
, long b
) { return BigInt(andor(0,a
.D
,b
,'&')); }
368 inline BigInt
operator ^ (const BigInt
& a
, const BigInt
& b
) { return BigInt(andor(0,a
.D
,b
.D
,'^')); }
369 inline BigInt
operator ^ (long a
, const BigInt
& b
) { return BigInt(andor(0,b
.D
,a
,'^')); }
370 inline BigInt
operator ^ (const BigInt
& a
, long b
) { return BigInt(andor(0,a
.D
,b
,'^')); }
371 inline BigInt
not (const BigInt
& a
) { return BigInt(bitnot(0,a
.D
)); }
