All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ttmathint.h
Go to the documentation of this file.
1 /*
2  * This file is a part of TTMath Bignum Library
3  * and is distributed under the (new) BSD licence.
4  * Author: Tomasz Sowa <t.sowa@ttmath.org>
5  */
6 
7 /*
8  * Copyright (c) 2006-2011, Tomasz Sowa
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions are met:
13  *
14  * * Redistributions of source code must retain the above copyright notice,
15  * this list of conditions and the following disclaimer.
16  *
17  * * Redistributions in binary form must reproduce the above copyright
18  * notice, this list of conditions and the following disclaimer in the
19  * documentation and/or other materials provided with the distribution.
20  *
21  * * Neither the name Tomasz Sowa nor the names of contributors to this
22  * project may be used to endorse or promote products derived
23  * from this software without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
29  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
35  * THE POSSIBILITY OF SUCH DAMAGE.
36  */
37 
38 
39 
40 #ifndef headerfilettmathint
41 #define headerfilettmathint
42 
48 #include "ttmathuint.h"
49 
50 namespace ttmath
51 {
52 
53 
62 template<uint value_size>
63 class Int : public UInt<value_size>
64 {
65 public:
66 
71  void SetMax()
72  {
75  }
76 
77 
82  void SetMin()
83  {
86  }
87 
88 
93  void SetSignOne()
94  {
96  }
97 
98 
106  {
107  /*
108  if the value is equal that one which has been returned from SetMin
109  (only the highest bit is set) that means we can't change sign
110  because the value is too big (bigger about one)
111 
112  e.g. when value_size = 1 and value is -2147483648 we can't change it to the
113  2147483648 because the max value which can be held is 2147483647
114 
115  we don't change the value and we're using this fact somewhere in some methods
116  (if we look on our value without the sign we get the correct value
117  eg. -2147483648 in Int<1> will be 2147483648 on the UInt<1> type)
118  */
120  return 1;
121 
122  UInt<value_size> temp(*this);
124  UInt<value_size>::Sub(temp);
125 
126  return 0;
127  }
128 
129 
130 
140  void SetSign()
141  {
142  if( IsSign() )
143  return;
144 
145  ChangeSign();
146  }
147 
148 
149 
155  bool IsSign() const
156  {
158  }
159 
160 
161 
168  {
169  if( !IsSign() )
170  return 0;
171 
172  return ChangeSign();
173  }
174 
175 
176 
177 
184 private:
185 
186  uint CorrectCarryAfterAdding(bool p1_is_sign, bool p2_is_sign)
187  {
188  if( !p1_is_sign && !p2_is_sign )
189  {
191  return 1;
192  }
193 
194  if( p1_is_sign && p2_is_sign )
195  {
196  if( ! UInt<value_size>::IsTheHighestBitSet() )
197  return 1;
198  }
199 
200  return 0;
201  }
202 
203 
204 public:
205 
219  uint Add(const Int<value_size> & ss2)
220  {
221  bool p1_is_sign = IsSign();
222  bool p2_is_sign = ss2.IsSign();
223 
224  UInt<value_size>::Add(ss2);
225 
226  return CorrectCarryAfterAdding(p1_is_sign, p2_is_sign);
227  }
228 
229 
236  uint AddInt(uint value, uint index = 0)
237  {
238  bool p1_is_sign = IsSign();
239 
241 
242  return CorrectCarryAfterAdding(p1_is_sign, false);
243  }
244 
245 
256  {
257  bool p1_is_sign = IsSign();
258 
259  UInt<value_size>::AddTwoInts(x2, x1, index);
260 
261  return CorrectCarryAfterAdding(p1_is_sign, false);
262  }
263 
264 private:
265 
266  uint CorrectCarryAfterSubtracting(bool p1_is_sign, bool p2_is_sign)
267  {
268  if( !p1_is_sign && p2_is_sign )
269  {
271  return 1;
272  }
273 
274  if( p1_is_sign && !p2_is_sign )
275  {
276  if( ! UInt<value_size>::IsTheHighestBitSet() )
277  return 1;
278  }
279 
280  return 0;
281  }
282 
283 public:
284 
298  uint Sub(const Int<value_size> & ss2)
299  {
300  bool p1_is_sign = IsSign();
301  bool p2_is_sign = ss2.IsSign();
302 
303  UInt<value_size>::Sub(ss2);
304 
305  return CorrectCarryAfterSubtracting(p1_is_sign, p2_is_sign);
306  }
307 
308 
313  uint SubInt(uint value, uint index = 0)
314  {
315  bool p1_is_sign = IsSign();
316 
318 
319  return CorrectCarryAfterSubtracting(p1_is_sign, false);
320  }
321 
322 
327  {
328  bool p1_is_sign = IsSign();
329 
331 
332  return CorrectCarryAfterAdding(p1_is_sign, false);
333  }
334 
335 
340  {
341  bool p1_is_sign = IsSign();
342 
344 
345  return CorrectCarryAfterSubtracting(p1_is_sign, false);
346  }
347 
348 
349 private:
350 
351 
352  uint CheckMinCarry(bool ss1_is_sign, bool ss2_is_sign)
353  {
354  /*
355  we have to examine the sign of the result now
356  but if the result is with the sign then:
357  1. if the signs were the same that means the result is too big
358  (the result must be without a sign)
359  2. if the signs were different that means if the result
360  is different from that one which has been returned from SetMin()
361  that is carry (result too big) but if the result is equal SetMin()
362  there'll be ok (and the next SetSign will has no effect because
363  the value is actually negative -- look at description of that case
364  in ChangeSign())
365  */
366  if( IsSign() )
367  {
368  if( ss1_is_sign != ss2_is_sign )
369  {
370  /*
371  there can be one case where signs are different and
372  the result will be equal the value from SetMin() (only the highest bit is set)
373  (this situation is ok)
374  */
376  return 1;
377  }
378  else
379  {
380  // signs were the same
381  return 1;
382  }
383  }
384 
385  return 0;
386  }
387 
388 
389 public:
390 
391 
398  {
399  bool ss1_is_sign, ss2_is_sign;
400  uint c;
401 
402  ss1_is_sign = IsSign();
403 
404  /*
405  we don't have to check the carry from Abs (values will be correct
406  because next we're using the method MulInt from the base class UInt
407  which is without a sign)
408  */
409  Abs();
410 
411  if( ss2 < 0 )
412  {
413  ss2 = -ss2;
414  ss2_is_sign = true;
415  }
416  else
417  {
418  ss2_is_sign = false;
419  }
420 
421  c = UInt<value_size>::MulInt((uint)ss2);
422  c += CheckMinCarry(ss1_is_sign, ss2_is_sign);
423 
424  if( ss1_is_sign != ss2_is_sign )
425  SetSign();
426 
427  return c;
428  }
429 
430 
431 
440  {
441  bool ss1_is_sign, ss2_is_sign;
442  uint c;
443 
444  ss1_is_sign = IsSign();
445  ss2_is_sign = ss2.IsSign();
446 
447  /*
448  we don't have to check the carry from Abs (values will be correct
449  because next we're using the method Mul from the base class UInt
450  which is without a sign)
451  */
452  Abs();
453  ss2.Abs();
454 
455  c = UInt<value_size>::Mul(ss2);
456  c += CheckMinCarry(ss1_is_sign, ss2_is_sign);
457 
458  if( ss1_is_sign != ss2_is_sign )
459  SetSign();
460 
461  return c;
462  }
463 
464 
479  uint Div(Int<value_size> ss2, Int<value_size> * remainder = 0)
480  {
481  bool ss1_is_sign, ss2_is_sign;
482 
483  ss1_is_sign = IsSign();
484  ss2_is_sign = ss2.IsSign();
485 
486  /*
487  we don't have to test the carry from Abs as well as in Mul
488  */
489  Abs();
490  ss2.Abs();
491 
492  uint c = UInt<value_size>::Div(ss2, remainder);
493 
494  if( ss1_is_sign != ss2_is_sign )
495  SetSign();
496 
497  if( ss1_is_sign && remainder )
498  remainder->SetSign();
499 
500  return c;
501  }
502 
503  uint Div(const Int<value_size> & ss2, Int<value_size> & remainder)
504  {
505  return Div(ss2, &remainder);
506  }
507 
508 
523  uint DivInt(sint ss2, sint * remainder = 0)
524  {
525  bool ss1_is_sign, ss2_is_sign;
526 
527  ss1_is_sign = IsSign();
528 
529  /*
530  we don't have to test the carry from Abs as well as in Mul
531  */
532  Abs();
533 
534  if( ss2 < 0 )
535  {
536  ss2 = -ss2;
537  ss2_is_sign = true;
538  }
539  else
540  {
541  ss2_is_sign = false;
542  }
543 
544  uint rem;
545  uint c = UInt<value_size>::DivInt((uint)ss2, &rem);
546 
547  if( ss1_is_sign != ss2_is_sign )
548  SetSign();
549 
550  if( remainder )
551  {
552  if( ss1_is_sign )
553  *remainder = -sint(rem);
554  else
555  *remainder = sint(rem);
556  }
557 
558  return c;
559  }
560 
561 
562  uint DivInt(sint ss2, sint & remainder)
563  {
564  return DivInt(ss2, &remainder);
565  }
566 
567 
568 private:
569 
570 
576  uint Pow2(const Int<value_size> & pow)
577  {
578  bool was_sign = IsSign();
579  uint c = 0;
580 
581  if( was_sign )
582  c += Abs();
583 
584  uint c_temp = UInt<value_size>::Pow(pow);
585  if( c_temp > 0 )
586  return c_temp; // c_temp can be: 0, 1 or 2
587 
588  if( was_sign && (pow.table[0] & 1) == 1 )
589  // negative value to the power of odd number is negative
590  c += ChangeSign();
591 
592  return (c==0)? 0 : 1;
593  }
594 
595 
596 public:
597 
598 
608  {
609  if( !pow.IsSign() )
610  return Pow2(pow);
611 
613  // if 'pow' is negative then
614  // 'this' must be different from zero
615  return 2;
616 
617  if( pow.ChangeSign() )
618  return 1;
619 
620  Int<value_size> t(*this);
621  uint c_temp = t.Pow2(pow);
622  if( c_temp > 0 )
623  return c_temp;
624 
626  if( Div(t) )
627  return 1;
628 
629  return 0;
630  }
631 
632 
633 
639 private:
640 
641 
645  template<uint argument_size>
646  uint FromUIntOrInt(const UInt<argument_size> & p, bool UInt_type)
647  {
648  uint min_size = (value_size < argument_size)? value_size : argument_size;
649  uint i;
650 
651  for(i=0 ; i<min_size ; ++i)
652  UInt<value_size>::table[i] = p.table[i];
653 
654 
655  if( value_size > argument_size )
656  {
657  uint fill;
658 
659  if( UInt_type )
660  fill = 0;
661  else
662  fill = (p.table[argument_size-1] & TTMATH_UINT_HIGHEST_BIT)?
664 
665  // 'this' is longer than 'p'
666  for( ; i<value_size ; ++i)
667  UInt<value_size>::table[i] = fill;
668  }
669  else
670  {
671  uint test = (UInt<value_size>::table[value_size-1] & TTMATH_UINT_HIGHEST_BIT)?
673 
674  if( UInt_type && test!=0 )
675  return 1;
676 
677  for( ; i<argument_size ; ++i)
678  if( p.table[i] != test )
679  return 1;
680  }
681 
682  return 0;
683  }
684 
685 public:
686 
695  template<uint argument_size>
697  {
698  return FromUIntOrInt(p, false);
699  }
700 
701 
706  {
707  uint fill = ( value<0 ) ? TTMATH_UINT_MAX_VALUE : 0;
708 
709  for(uint i=1 ; i<value_size ; ++i)
710  UInt<value_size>::table[i] = fill;
711 
712  UInt<value_size>::table[0] = uint(value);
713 
714  // there'll never be a carry here
715  return 0;
716  }
717 
718 
722  template<uint argument_size>
724  {
725  return FromUIntOrInt(p, true);
726  }
727 
728 
732  template<uint argument_size>
734  {
735  return FromUIntOrInt(p, true);
736  }
737 
738 
743  {
744  for(uint i=1 ; i<value_size ; ++i)
746 
747  UInt<value_size>::table[0] = value;
748 
749  // there can be a carry here when the size of this value is equal one word
750  // and the 'value' has the highest bit set
751  if( value_size==1 && (value & TTMATH_UINT_HIGHEST_BIT)!=0 )
752  return 1;
753 
754  return 0;
755  }
756 
757 
762  {
763  return FromUInt(value);
764  }
765 
766 
771  {
772  FromInt(p);
773 
774  return *this;
775  }
776 
777 
783  template<uint argument_size>
785  {
786  FromInt(p);
787 
788  return *this;
789  }
790 
791 
796  {
797  FromInt(i);
798 
799  return *this;
800  }
801 
802 
807  {
808  FromInt(i);
809  }
810 
811 
815  Int(const Int<value_size> & u)
816  {
817  FromInt(u);
818  }
819 
820 
824  template<uint argument_size>
826  {
827  // look that 'size' we still set as 'value_size' and not as u.value_size
828  FromInt(u);
829  }
830 
831 
832 
838  template<uint argument_size>
840  {
841  FromUInt(p);
842 
843  return *this;
844  }
845 
846 
851  {
852  FromUInt(i);
853 
854  return *this;
855  }
856 
857 
862  {
863  FromUInt(i);
864  }
865 
866 
870  template<uint argument_size>
872  {
873  // look that 'size' we still set as 'value_size' and not as u.value_size
874  FromUInt(u);
875  }
876 
877 
878 
879 #ifdef TTMATH_PLATFORM32
880 
881 
887  {
889 
890  if( c )
891  return 1;
892 
893  if( value_size == 1 )
894  return ((UInt<value_size>::table[0] & TTMATH_UINT_HIGHEST_BIT) == 0) ? 0 : 1;
895 
896  if( value_size == 2 )
897  return ((UInt<value_size>::table[1] & TTMATH_UINT_HIGHEST_BIT) == 0) ? 0 : 1;
898 
899  return 0;
900  }
901 
902 
908  {
909  return FromUInt(n);
910  }
911 
912 
918  {
919  uint mask = (n < 0) ? TTMATH_UINT_MAX_VALUE : 0;
920 
922 
923  if( value_size == 1 )
924  {
925  if( uint(ulint(n) >> 32) != mask )
926  return 1;
927 
928  return ((UInt<value_size>::table[0] & TTMATH_UINT_HIGHEST_BIT) == (mask & TTMATH_UINT_HIGHEST_BIT)) ? 0 : 1;
929  }
930 
931  UInt<value_size>::table[1] = (uint)(ulint(n) >> 32);
932 
933  for(uint i=2 ; i<value_size ; ++i)
934  UInt<value_size>::table[i] = mask;
935 
936  return 0;
937  }
938 
939 
945  {
946  FromUInt(n);
947 
948  return *this;
949  }
950 
951 
957  {
958  FromUInt(n);
959  }
960 
961 
967  {
968  FromInt(n);
969 
970  return *this;
971  }
972 
973 
979  {
980  FromInt(n);
981  }
982 
983 #endif
984 
985 
986 
987 
988 #ifdef TTMATH_PLATFORM64
989 
994  uint FromUInt(unsigned int i)
995  {
996  return FromUInt(uint(i));
997  }
998 
999 
1004  uint FromInt(unsigned int i)
1005  {
1006  return FromUInt(i);
1007  }
1008 
1009 
1014  uint FromInt(signed int i)
1015  {
1016  return FromInt(sint(i));
1017  }
1018 
1019 
1024  Int<value_size> & operator=(unsigned int i)
1025  {
1026  FromUInt(i);
1027 
1028  return *this;
1029  }
1030 
1031 
1036  Int(unsigned int i)
1037  {
1038  FromUInt(i);
1039  }
1040 
1041 
1046  Int<value_size> & operator=(signed int i)
1047  {
1048  FromInt(i);
1049 
1050  return *this;
1051  }
1052 
1053 
1058  Int(signed int i)
1059  {
1060  FromInt(i);
1061  }
1062 
1063 #endif
1064 
1065 
1066 
1070  Int(const char * s)
1071  {
1072  FromString(s);
1073  }
1074 
1075 
1079  Int(const std::string & s)
1080  {
1081  FromString( s.c_str() );
1082  }
1083 
1084 
1085 #ifndef TTMATH_DONT_USE_WCHAR
1086 
1090  Int(const wchar_t * s)
1091  {
1092  FromString(s);
1093  }
1094 
1095 
1099  Int(const std::wstring & s)
1100  {
1101  FromString( s.c_str() );
1102  }
1103 
1104 #endif
1105 
1106 
1113  {
1114  }
1115 
1116 
1121  {
1122  }
1123 
1124 
1131  sint ToInt() const
1132  {
1133  return sint( UInt<value_size>::table[0] );
1134  }
1135 
1136 
1141  uint ToUInt(uint & result) const
1142  {
1143  uint c = UInt<value_size>::ToUInt(result);
1144 
1145  if( value_size == 1 )
1146  return (result & TTMATH_UINT_HIGHEST_BIT) == 0 ? 0 : 1;
1147 
1148  return c;
1149  }
1150 
1151 
1156  uint ToInt(uint & result) const
1157  {
1158  return ToUInt(result);
1159  }
1160 
1161 
1166  uint ToInt(sint & result) const
1167  {
1168  result = sint( UInt<value_size>::table[0] );
1169  uint mask = IsSign() ? TTMATH_UINT_MAX_VALUE : 0;
1170 
1171  if( (result & TTMATH_UINT_HIGHEST_BIT) != (mask & TTMATH_UINT_HIGHEST_BIT) )
1172  return 1;
1173 
1174  for(uint i=1 ; i<value_size ; ++i)
1175  if( UInt<value_size>::table[i] != mask )
1176  return 1;
1177 
1178  return 0;
1179  }
1180 
1181 
1182 #ifdef TTMATH_PLATFORM32
1183 
1189  uint ToUInt(ulint & result) const
1190  {
1191  uint c = UInt<value_size>::ToUInt(result);
1192 
1193  if( value_size == 1 )
1194  return (UInt<value_size>::table[0] & TTMATH_UINT_HIGHEST_BIT) == 0 ? 0 : 1;
1195 
1196  if( value_size == 2 )
1197  return (UInt<value_size>::table[1] & TTMATH_UINT_HIGHEST_BIT) == 0 ? 0 : 1;
1198 
1199  return c;
1200  }
1201 
1202 
1208  uint ToInt(ulint & result) const
1209  {
1210  return ToUInt(result);
1211  }
1212 
1213 
1219  uint ToInt(slint & result) const
1220  {
1221  if( value_size == 1 )
1222  {
1223  result = slint(sint(UInt<value_size>::table[0]));
1224  }
1225  else
1226  {
1227  uint low = UInt<value_size>::table[0];
1228  uint high = UInt<value_size>::table[1];
1229 
1230  result = low;
1231  result |= (ulint(high) << TTMATH_BITS_PER_UINT);
1232 
1233  uint mask = IsSign() ? TTMATH_UINT_MAX_VALUE : 0;
1234 
1235  if( (high & TTMATH_UINT_HIGHEST_BIT) != (mask & TTMATH_UINT_HIGHEST_BIT) )
1236  return 1;
1237 
1238  for(uint i=2 ; i<value_size ; ++i)
1239  if( UInt<value_size>::table[i] != mask )
1240  return 1;
1241  }
1242 
1243  return 0;
1244  }
1245 
1246 #endif
1247 
1248 
1249 
1250 #ifdef TTMATH_PLATFORM64
1251 
1257  uint ToUInt(unsigned int & result) const
1258  {
1259  uint c = UInt<value_size>::ToUInt(result);
1260 
1261  if( c || IsSign() )
1262  return 1;
1263 
1264  return 0;
1265  }
1266 
1267 
1273  uint ToInt(unsigned int & result) const
1274  {
1275  return ToUInt(result);
1276  }
1277 
1278 
1284  uint ToInt(int & result) const
1285  {
1286  uint first = UInt<value_size>::table[0];
1287 
1288  result = int(first);
1289  uint mask = IsSign() ? TTMATH_UINT_MAX_VALUE : 0;
1290 
1291  if( (first >> 31) != (mask >> 31) )
1292  return 1;
1293 
1294  for(uint i=1 ; i<value_size ; ++i)
1295  if( UInt<value_size>::table[i] != mask )
1296  return 1;
1297 
1298  return 0;
1299  }
1300 
1301 #endif
1302 
1303 
1304 
1305 
1306 private:
1307 
1311  template<class string_type>
1312  void ToStringBase(string_type & result, uint b = 10) const
1313  {
1314  if( IsSign() )
1315  {
1316  Int<value_size> temp(*this);
1317  temp.Abs();
1318  temp.UInt<value_size>::ToStringBase(result, b, true);
1319  }
1320  else
1321  {
1322  UInt<value_size>::ToStringBase(result, b, false);
1323  }
1324  }
1325 
1326 public:
1327 
1331  void ToString(std::string & result, uint b = 10) const
1332  {
1333  return ToStringBase(result, b);
1334  }
1335 
1336 
1340  std::string ToString(uint b = 10) const
1341  {
1342  std::string result;
1343  ToStringBase(result, b);
1344 
1345  return result;
1346  }
1347 
1348 
1349 #ifndef TTMATH_DONT_USE_WCHAR
1350 
1354  void ToString(std::wstring & result, uint b = 10) const
1355  {
1356  return ToStringBase(result, b);
1357  }
1358 
1359 
1363  std::wstring ToWString(uint b = 10) const
1364  {
1365  std::wstring result;
1366  ToStringBase(result, b);
1367 
1368  return result;
1369  }
1370 
1371 #endif
1372 
1373 
1374 
1375 private:
1376 
1380  template<class char_type>
1381  uint FromStringBase(const char_type * s, uint b = 10, const char_type ** after_source = 0, bool * value_read = 0)
1382  {
1383  bool is_sign = false;
1384 
1386 
1387  if( *s == '-' )
1388  {
1389  is_sign = true;
1391  }
1392  else
1393  if( *s == '+' )
1394  {
1396  }
1397 
1398  if( UInt<value_size>::FromString(s,b,after_source,value_read) )
1399  return 1;
1400 
1401  if( is_sign )
1402  {
1403  Int<value_size> mmin;
1404 
1405  mmin.SetMin();
1406 
1407  /*
1408  the reference to mmin will be automatically converted to the reference
1409  to UInt type
1410  (this value can be equal mmin -- look at a description in ChangeSign())
1411  */
1412  if( UInt<value_size>::operator>( mmin ) )
1413  return 1;
1414 
1415  /*
1416  if the value is equal mmin the method ChangeSign() does nothing (only returns 1 but we ignore it)
1417  */
1418  ChangeSign();
1419  }
1420  else
1421  {
1422  Int<value_size> mmax;
1423 
1424  mmax.SetMax();
1425 
1426  if( UInt<value_size>::operator>( mmax ) )
1427  return 1;
1428  }
1429 
1430  return 0;
1431  }
1432 
1433 
1434 public:
1435 
1452  uint FromString(const char * s, uint b = 10, const char ** after_source = 0, bool * value_read = 0)
1453  {
1454  return FromStringBase(s, b, after_source, value_read);
1455  }
1456 
1457 
1461  uint FromString(const wchar_t * s, uint b = 10, const wchar_t ** after_source = 0, bool * value_read = 0)
1462  {
1463  return FromStringBase(s, b, after_source, value_read);
1464  }
1465 
1466 
1471  uint FromString(const std::string & s, uint b = 10)
1472  {
1473  return FromString( s.c_str(), b );
1474  }
1475 
1476 
1480  Int<value_size> & operator=(const char * s)
1481  {
1482  FromString(s);
1483 
1484  return *this;
1485  }
1486 
1487 
1488 #ifndef TTMATH_DONT_USE_WCHAR
1489 
1490 
1495  uint FromString(const std::wstring & s, uint b = 10)
1496  {
1497  return FromString( s.c_str(), b );
1498  }
1499 
1500 
1504  Int<value_size> & operator=(const wchar_t * s)
1505  {
1506  FromString(s);
1507 
1508  return *this;
1509  }
1510 
1511 
1515  Int<value_size> & operator=(const std::wstring & s)
1516  {
1517  FromString( s.c_str() );
1518 
1519  return *this;
1520  }
1521 
1522 #endif
1523 
1524 
1528  Int<value_size> & operator=(const std::string & s)
1529  {
1530  FromString( s.c_str() );
1531 
1532  return *this;
1533  }
1534 
1535 
1536 
1544  bool operator==(const Int<value_size> & l) const
1545  {
1546  return UInt<value_size>::operator==(l);
1547  }
1548 
1549  bool operator!=(const Int<value_size> & l) const
1550  {
1551  return UInt<value_size>::operator!=(l);
1552  }
1553 
1554  bool operator<(const Int<value_size> & l) const
1555  {
1556  sint i=value_size-1;
1557 
1559  sint a2 = sint(l.table[i]);
1560 
1561  if( a1 != a2 )
1562  return a1 < a2;
1563 
1564 
1565  for(--i ; i>=0 ; --i)
1566  {
1567  if( UInt<value_size>::table[i] != l.table[i] )
1568  // comparison as unsigned int
1569  return UInt<value_size>::table[i] < l.table[i];
1570  }
1571 
1572  // they're equal
1573  return false;
1574  }
1575 
1576 
1577  bool operator>(const Int<value_size> & l) const
1578  {
1579  sint i=value_size-1;
1580 
1582  sint a2 = sint(l.table[i]);
1583 
1584  if( a1 != a2 )
1585  return a1 > a2;
1586 
1587 
1588  for(--i ; i>=0 ; --i)
1589  {
1590  if( UInt<value_size>::table[i] != l.table[i] )
1591  // comparison as unsigned int
1592  return UInt<value_size>::table[i] > l.table[i];
1593  }
1594 
1595  // they're equal
1596  return false;
1597  }
1598 
1599 
1600  bool operator<=(const Int<value_size> & l) const
1601  {
1602  sint i=value_size-1;
1603 
1605  sint a2 = sint(l.table[i]);
1606 
1607  if( a1 != a2 )
1608  return a1 < a2;
1609 
1610 
1611  for(--i ; i>=0 ; --i)
1612  {
1613  if( UInt<value_size>::table[i] != l.table[i] )
1614  // comparison as unsigned int
1615  return UInt<value_size>::table[i] < l.table[i];
1616  }
1617 
1618  // they're equal
1619  return true;
1620  }
1621 
1622 
1623  bool operator>=(const Int<value_size> & l) const
1624  {
1625  sint i=value_size-1;
1626 
1628  sint a2 = sint(l.table[i]);
1629 
1630  if( a1 != a2 )
1631  return a1 > a2;
1632 
1633 
1634  for(--i ; i>=0 ; --i)
1635  {
1636  if( UInt<value_size>::table[i] != l.table[i] )
1637  // comparison as unsigned int
1638  return UInt<value_size>::table[i] > l.table[i];
1639  }
1640 
1641  // they're equal
1642  return true;
1643  }
1644 
1645 
1646 
1660  {
1661  Int<value_size> temp(*this);
1662 
1663  temp.ChangeSign();
1664 
1665  return temp;
1666  }
1667 
1668 
1670  {
1671  Int<value_size> temp(*this);
1672 
1673  temp.Sub(p2);
1674 
1675  return temp;
1676  }
1677 
1678 
1680  {
1681  Sub(p2);
1682 
1683  return *this;
1684  }
1685 
1686 
1688  {
1689  Int<value_size> temp(*this);
1690 
1691  temp.Add(p2);
1692 
1693  return temp;
1694  }
1695 
1696 
1698  {
1699  Add(p2);
1700 
1701  return *this;
1702  }
1703 
1704 
1706  {
1707  Int<value_size> temp(*this);
1708 
1709  temp.Mul(p2);
1710 
1711  return temp;
1712  }
1713 
1714 
1716  {
1717  Mul(p2);
1718 
1719  return *this;
1720  }
1721 
1722 
1724  {
1725  Int<value_size> temp(*this);
1726 
1727  temp.Div(p2);
1728 
1729  return temp;
1730  }
1731 
1732 
1734  {
1735  Div(p2);
1736 
1737  return *this;
1738  }
1739 
1740 
1742  {
1743  Int<value_size> temp(*this);
1744  Int<value_size> remainder;
1745 
1746  temp.Div(p2, remainder);
1747 
1748  return remainder;
1749  }
1750 
1751 
1753  {
1754  Int<value_size> remainder;
1755 
1756  Div(p2, remainder);
1757  operator=(remainder);
1758 
1759  return *this;
1760  }
1761 
1762 
1767  {
1768  AddOne();
1769 
1770  return *this;
1771  }
1772 
1773 
1778  {
1779  UInt<value_size> temp( *this );
1780 
1781  AddOne();
1782 
1783  return temp;
1784  }
1785 
1786 
1788  {
1789  SubOne();
1790 
1791  return *this;
1792  }
1793 
1794 
1796  {
1797  UInt<value_size> temp( *this );
1798 
1799  SubOne();
1800 
1801  return temp;
1802  }
1803 
1804 
1805 
1812 private:
1813 
1817  template<class ostream_type, class string_type>
1818  static ostream_type & OutputToStream(ostream_type & s, const Int<value_size> & l)
1819  {
1820  string_type ss;
1821 
1822  l.ToString(ss);
1823  s << ss;
1824 
1825  return s;
1826  }
1827 
1828 
1829 
1830 public:
1831 
1832 
1836  friend std::ostream & operator<<(std::ostream & s, const Int<value_size> & l)
1837  {
1838  return OutputToStream<std::ostream, std::string>(s, l);
1839  }
1840 
1841 
1842 #ifndef TTMATH_DONT_USE_WCHAR
1843 
1847  friend std::wostream & operator<<(std::wostream & s, const Int<value_size> & l)
1848  {
1849  return OutputToStream<std::wostream, std::wstring>(s, l);
1850  }
1851 
1852 #endif
1853 
1854 
1855 
1856 private:
1857 
1861  template<class istream_type, class string_type, class char_type>
1862  static istream_type & InputFromStream(istream_type & s, Int<value_size> & l)
1863  {
1864  string_type ss;
1865 
1866  // char or wchar_t for operator>>
1867  char_type z;
1868 
1869  // operator>> omits white characters if they're set for ommiting
1870  s >> z;
1871 
1872  if( z=='-' || z=='+' )
1873  {
1874  ss += z;
1875  s >> z; // we're reading a next character (white characters can be ommited)
1876  }
1877 
1878  // we're reading only digits (base=10)
1879  while( s.good() && Misc::CharToDigit(z, 10)>=0 )
1880  {
1881  ss += z;
1882  z = static_cast<char_type>(s.get());
1883  }
1884 
1885  // we're leaving the last readed character
1886  // (it's not belonging to the value)
1887  s.unget();
1888 
1889  l.FromString(ss);
1890 
1891  return s;
1892  }
1893 
1894 
1895 public:
1896 
1900  friend std::istream & operator>>(std::istream & s, Int<value_size> & l)
1901  {
1902  return InputFromStream<std::istream, std::string, char>(s, l);
1903  }
1904 
1905 
1906 #ifndef TTMATH_DONT_USE_WCHAR
1907 
1911  friend std::wistream & operator>>(std::wistream & s, Int<value_size> & l)
1912  {
1913  return InputFromStream<std::wistream, std::wstring, wchar_t>(s, l);
1914  }
1915 #endif
1916 
1917 
1918 };
1919 
1920 } // namespace
1921 
1922 #endif
bool operator>=(const Int< value_size > &l) const
Definition: ttmathint.h:1623
Int< value_size > & operator=(const Int< argument_size > &p)
Definition: ttmathint.h:784
Int implements a big integer value with a sign.
Definition: ttmathint.h:63
Int< value_size > operator-() const
Definition: ttmathint.h:1659
Int< value_size > & operator=(const std::string &s)
Definition: ttmathint.h:1528
std::wstring ToWString(uint b=10) const
Definition: ttmathint.h:1363
uint SubInt(uint value, uint index=0)
Int< value_size > & operator=(const Int< value_size > &p)
Definition: ttmathint.h:770
static void SkipWhiteCharacters(const char_type *&c)
Definition: ttmathmisc.h:160
friend std::istream & operator>>(std::istream &s, Int< value_size > &l)
Definition: ttmathint.h:1900
static uint CharToDigit(uint c)
Definition: ttmathmisc.h:181
uint Div(const Int< value_size > &ss2, Int< value_size > &remainder)
Definition: ttmathint.h:503
uint FromUInt(const UInt< argument_size > &p)
Definition: ttmathuint.h:2633
NetworKit::index index
Definition: BloomFilter.h:16
uint AddInt(uint value, uint index=0)
sint ToInt() const
Definition: ttmathint.h:1131
Int< value_size > & operator*=(const Int< value_size > &p2)
Definition: ttmathint.h:1715
uint table[value_size]
Definition: ttmathuint.h:81
uint Pow(Int< value_size > pow)
Definition: ttmathint.h:607
Int< value_size > & operator/=(const Int< value_size > &p2)
Definition: ttmathint.h:1733
uint FromString(const wchar_t *s, uint b=10, const wchar_t **after_source=0, bool *value_read=0)
Definition: ttmathint.h:1461
Int(slint n)
Definition: ttmathint.h:978
Int(const char *s)
Definition: ttmathint.h:1070
template class UInt<uint>
uint DivInt(sint ss2, sint &remainder)
Definition: ttmathint.h:562
void SetSign()
Definition: ttmathint.h:140
uint FromInt(const Int< argument_size > &p)
Definition: ttmathint.h:696
Int(const Int< value_size > &u)
Definition: ttmathint.h:815
int64_t slint
Definition: ttmathtypes.h:178
Int(sint i)
Definition: ttmathint.h:806
uint Sub(const UInt< value_size > &ss2, uint c=0)
uint Add(const UInt< value_size > &ss2, uint c=0)
void ToStringBase(string_type &result, uint b=10, bool negative=false) const
Definition: ttmathuint.h:3292
Int(const std::wstring &s)
Definition: ttmathint.h:1099
uint ToUInt(uint &result) const
Definition: ttmathint.h:1141
uint Abs()
Definition: ttmathint.h:167
friend std::wistream & operator>>(std::wistream &s, Int< value_size > &l)
Definition: ttmathint.h:1911
uint ToInt(sint &result) const
Definition: ttmathint.h:1166
Int(const wchar_t *s)
Definition: ttmathint.h:1090
uint FromUInt(uint value)
Definition: ttmathint.h:742
uint FromString(const std::wstring &s, uint b=10)
Definition: ttmathint.h:1495
void ToString(std::wstring &result, uint b=10) const
Definition: ttmathint.h:1354
uint FromInt(const UInt< argument_size > &p)
Definition: ttmathint.h:733
void SetMax()
Definition: ttmathuint.h:215
Int< value_size > operator*(const Int< value_size > &p2) const
Definition: ttmathint.h:1705
bool operator!=(const UInt< value_size > &l) const
Definition: ttmathuint.h:3708
uint FromInt(slint n)
Definition: ttmathint.h:917
uint AddOne()
Definition: ttmathint.h:326
uint FromUInt(const UInt< argument_size > &p)
Definition: ttmathint.h:723
#define TTMATH_UINT_HIGHEST_BIT
Definition: ttmathtypes.h:189
Int< value_size > operator%(const Int< value_size > &p2) const
Definition: ttmathint.h:1741
uint MulInt(uint ss2)
Definition: ttmathuint.h:835
Int(ulint n)
Definition: ttmathint.h:956
void SetMax()
Definition: ttmathint.h:71
uint FromInt(uint value)
Definition: ttmathint.h:761
signed int sint
Definition: ttmathtypes.h:164
void SetZero()
Definition: ttmathuint.h:188
uint FromInt(sint value)
Definition: ttmathint.h:705
UInt< value_size > operator--(int)
Definition: ttmathint.h:1795
Int< value_size > & operator-=(const Int< value_size > &p2)
Definition: ttmathint.h:1679
uint ToUInt() const
Definition: ttmathuint.h:3079
bool operator>(const Int< value_size > &l) const
Definition: ttmathint.h:1577
std::string ToString(uint b=10) const
Definition: ttmathint.h:1340
uint Div(const UInt< value_size > &divisor, UInt< value_size > *remainder=0, uint algorithm=3)
Definition: ttmathuint.h:1603
uint ToUInt(ulint &result) const
Definition: ttmathint.h:1189
#define TTMATH_UINT_MAX_VALUE
Definition: ttmathtypes.h:195
bool operator!=(const Int< value_size > &l) const
Definition: ttmathint.h:1549
Int(const std::string &s)
Definition: ttmathint.h:1079
uint Pow(UInt< value_size > pow)
Definition: ttmathuint.h:2402
UInt< value_size > & operator++()
Definition: ttmathint.h:1766
uint AddTwoInts(uint x2, uint x1, uint index)
uint Mul(Int< value_size > ss2)
Definition: ttmathint.h:439
uint ToInt(slint &result) const
Definition: ttmathint.h:1219
Int()
Definition: ttmathint.h:1112
uint SubOne()
Definition: ttmathint.h:339
void SetSignOne()
Definition: ttmathint.h:93
Int< value_size > & operator%=(const Int< value_size > &p2)
Definition: ttmathint.h:1752
uint FromUInt(ulint n)
Definition: ttmathint.h:886
Int(uint i)
Definition: ttmathint.h:861
uint ToInt(uint &result) const
Definition: ttmathint.h:1156
Int< value_size > & operator=(uint i)
Definition: ttmathint.h:850
uint Add(const Int< value_size > &ss2)
Definition: ttmathint.h:219
uint AddInt(uint value, uint index=0)
Definition: ttmathint.h:236
uint FromString(const std::string &s, uint b=10)
Definition: ttmathint.h:1471
bool operator==(const Int< value_size > &l) const
Definition: ttmathint.h:1544
#define TTMATH_BITS_PER_UINT
Definition: ttmathtypes.h:184
void ToString(std::string &result, uint b=10) const
Definition: ttmathint.h:1331
uint ChangeSign()
Definition: ttmathint.h:105
UInt implements a big integer value without a sign.
Definition: ttmathuint.h:73
bool IsSign() const
Definition: ttmathint.h:155
UInt< value_size > & operator--()
Definition: ttmathint.h:1787
uint AddTwoInts(uint x2, uint x1, uint index)
Definition: ttmathint.h:255
void SetMin()
Definition: ttmathint.h:82
uint FromString(const char *s, uint b=10, const char **after_source=0, bool *value_read=0)
Definition: ttmathint.h:1452
UInt< value_size > operator++(int)
Definition: ttmathint.h:1777
Int< value_size > & operator=(const wchar_t *s)
Definition: ttmathint.h:1504
Int< value_size > & operator=(const UInt< argument_size > &p)
Definition: ttmathint.h:839
uint FromInt(ulint n)
Definition: ttmathint.h:907
uint64_t ulint
Definition: ttmathtypes.h:177
uint ToInt(ulint &result) const
Definition: ttmathint.h:1208
Int< value_size > & operator=(const char *s)
Definition: ttmathint.h:1480
Int< value_size > operator+(const Int< value_size > &p2) const
Definition: ttmathint.h:1687
uint DivInt(sint ss2, sint *remainder=0)
Definition: ttmathint.h:523
uint Div(Int< value_size > ss2, Int< value_size > *remainder=0)
Definition: ttmathint.h:479
uint Mul(const UInt< value_size > &ss2, uint algorithm=100)
Definition: ttmathuint.h:923
Int< value_size > & operator=(slint n)
Definition: ttmathint.h:966
Int< value_size > operator/(const Int< value_size > &p2) const
Definition: ttmathint.h:1723
~Int()
Definition: ttmathint.h:1120
unsigned int uint
Definition: ttmathtypes.h:163
uint AddOne()
Definition: ttmathuint.h:386
void SetOne()
Definition: ttmathuint.h:202
Int(const UInt< argument_size > &u)
Definition: ttmathint.h:871
Int< value_size > operator-(const Int< value_size > &p2) const
Definition: ttmathint.h:1669
Int< value_size > & operator=(sint i)
Definition: ttmathint.h:795
uint MulInt(sint ss2)
Definition: ttmathint.h:397
bool IsTheHighestBitSet() const
Definition: ttmathuint.h:2523
uint DivInt(uint divisor, uint *remainder=0)
Definition: ttmathuint.h:1545
uint SubInt(uint value, uint index=0)
Definition: ttmathint.h:313
Int(const Int< argument_size > &u)
Definition: ttmathint.h:825
Int< value_size > & operator=(const std::wstring &s)
Definition: ttmathint.h:1515
Int< value_size > & operator+=(const Int< value_size > &p2)
Definition: ttmathint.h:1697
bool operator==(const UInt< value_size > &l) const
Definition: ttmathuint.h:3702
Int< value_size > & operator=(ulint n)
Definition: ttmathint.h:944
uint Sub(const Int< value_size > &ss2)
Definition: ttmathint.h:298
uint SubOne()
Definition: ttmathuint.h:395