Posted By

offs on 06/22/11


Tagged

integer long bitwise arithmetics


Versions (?)

Long integer


 / Published in: C++
 

Длинное целое, построенное на std::bitset. Код к разбору большого домашнего задания для студентов ШАД.

  1. #pragma once
  2.  
  3. #include <bitset>
  4.  
  5. const unsigned BITS = 256;
  6. const unsigned BASE = 10;
  7.  
  8. class LongInt
  9. {
  10. public:
  11. LongInt(int number = 0);
  12. LongInt(const LongInt& other);
  13. LongInt& operator =(const LongInt& other);
  14.  
  15. public:
  16. class reference //прокси-класс для элемента
  17. {
  18. friend class LongInt;
  19.  
  20. public:
  21. reference& operator =(const reference& ref)
  22. {
  23. valuePtr->Set(myPosition, unsigned(ref));
  24. return *this;
  25. }
  26.  
  27. reference& operator =(unsigned value)
  28. {
  29. valuePtr->Set(myPosition, value);
  30. return *this;
  31. }
  32.  
  33. operator unsigned() const
  34. {
  35. return valuePtr->Get(myPosition);
  36. }
  37.  
  38. private:
  39. reference(LongInt* value, unsigned position)
  40. : valuePtr(value)
  41. , myPosition(position)
  42. {}
  43.  
  44. private:
  45. unsigned myPosition;
  46. LongInt* valuePtr;
  47. };
  48.  
  49. public: // арифметические операторы
  50. LongInt& operator +=(const LongInt& other);
  51. LongInt& operator -=(const LongInt& other);
  52. LongInt& operator *=(const LongInt& other);
  53. LongInt& operator /=(const LongInt& other);
  54. LongInt& operator %=(const LongInt& other);
  55.  
  56. public: // битовые операторы
  57. LongInt& operator |=(const LongInt& other);
  58. LongInt& operator ^=(const LongInt& other);
  59. LongInt& operator &=(const LongInt& other);
  60.  
  61. public: // операторы битового сдвига
  62. LongInt& operator <<=(unsigned offs);
  63. LongInt& operator >>=(unsigned offs);
  64.  
  65. public:
  66. LongInt& operator ++();
  67. LongInt& operator --();
  68. const LongInt operator ++(int);
  69. const LongInt operator --(int);
  70.  
  71. public: //унарные операторы арифметического и битового отрицания
  72. const LongInt operator -() const;
  73. const LongInt operator ~() const;
  74.  
  75. public:
  76. //operator bool() const;
  77.  
  78. public:
  79. size_t size();
  80.  
  81. public:
  82. reference operator [](unsigned index);
  83. unsigned operator [](unsigned index) const;
  84.  
  85. public:
  86. bool IsEqual(const LongInt& other) const; // Существует по соображениям эффективности и удобства.
  87. bool IsLess(const LongInt& other) const; // Отношения порядка достаточно. "==" можно представить, как !(l < r) && !(r < l))
  88.  
  89. public: // обмен без генерации исключений
  90. void Swap(LongInt& other);
  91.  
  92. private:
  93. void Divide(const LongInt& left, const LongInt& right, LongInt& quotient, LongInt& reminder);
  94. void SignedDivide(const LongInt& left, const LongInt& right, LongInt& quotient, LongInt& reminder);
  95.  
  96. private: // установка разряда
  97. void Set(unsigned position, unsigned value);
  98. unsigned Get(unsigned position) const;
  99.  
  100. private:
  101. typedef std::bitset<BITS> Bitset;
  102. Bitset value;
  103. };
  104.  
  105. // Бинарные операторы как свободные функции.
  106.  
  107. const LongInt operator <<(const LongInt& value, unsigned shift);
  108. const LongInt operator >>(const LongInt& value, unsigned shift);
  109.  
  110. const LongInt operator +(const LongInt& left, const LongInt& right);
  111. const LongInt operator -(const LongInt& left, const LongInt& right);
  112. const LongInt operator *(const LongInt& left, const LongInt& right);
  113. const LongInt operator /(const LongInt& left, const LongInt& right);
  114. const LongInt operator %(const LongInt& left, const LongInt& right);
  115. const LongInt operator ^(const LongInt& left, const LongInt& right);
  116. const LongInt operator &(const LongInt& left, const LongInt& right);
  117. const LongInt operator |(const LongInt& left, const LongInt& right);
  118.  
  119. bool operator ==(const LongInt& left, const LongInt& right);
  120. bool operator !=(const LongInt& left, const LongInt& right);
  121. bool operator >=(const LongInt& left, const LongInt& right);
  122. bool operator <=(const LongInt& left, const LongInt& right);
  123. bool operator >(const LongInt& left, const LongInt& right);
  124. bool operator <(const LongInt& left, const LongInt& right);
  125.  
  126. const LongInt Gcd(const LongInt& left, const LongInt& right)
  127. const LongInt Pow(const LongInt& number, unsigned pow);
  128. const LongInt Abs(const LongInt& number);
  129. const LongInt Factorial(const LongInt& other);
  130.  
  131.  
  132. LongInt::LongInt(int number) : value(number)
  133. {}
  134.  
  135. LongInt::LongInt(const LongInt& other) : value(other.value)
  136. {}
  137.  
  138. LongInt& LongInt::operator =(const LongInt& other) //Канонический вид оператора присваивания через копирующий конструктор и swap.
  139. {
  140. LongInt temp(other); //Все исключения могут произойти только здесь.
  141. temp.Swap(*this); //Не вызывает исключений.
  142. return *this;
  143. }
  144.  
  145. void LongInt::Swap(LongInt& other) //swap через xor. Работает для произвольных битовых наборов равной длины.
  146. {
  147. value ^= other.value;
  148. other.value ^= value;
  149. value ^= other.value;
  150. }
  151.  
  152. bool LongInt::IsEqual(const LongInt& other) const
  153. {
  154. return value == other.value;
  155. }
  156.  
  157. bool LongInt::IsLess(const LongInt& other) const //Знаковый оператор "меньше".
  158. {
  159. LongInt diff = *this - other;
  160. LongInt xorr = *this ^ other;
  161.  
  162. return (diff ^= xorr &= diff ^= *this).value.test(BITS - 1);
  163. }
  164.  
  165. inline bool add(bool l, bool r, bool& carry) //Сложение битов с флагом переноса.
  166. {
  167. bool sum = l ^ r ^ carry;
  168. carry = (l && r) || (l && carry) || (r && carry);
  169.  
  170. return sum;
  171. }
  172.  
  173. inline bool sub(bool l, bool r, bool& borrow) //Вычитание битов с флагом заема.
  174. {
  175. bool diff = borrow ? !(l ^ r) : l ^ r;
  176. borrow = borrow ? !l || (l && r) : !l && r;
  177.  
  178. return diff;
  179. }
  180.  
  181. // Операторы доступа
  182.  
  183. LongInt::reference LongInt::operator [](unsigned index)
  184. {
  185. return reference(this, index);
  186. }
  187.  
  188. unsigned LongInt::operator [](unsigned index) const
  189. {
  190. return Get(index);
  191. }
  192.  
  193. // Операторы вида @= являются членами класса и модифицируют объект.
  194. // Возвращают ссылку на себя.
  195.  
  196. LongInt& LongInt::operator +=(const LongInt& other)
  197. {
  198. bool carry = false;
  199.  
  200. for (unsigned i = 0; i != BITS; ++i)
  201. value[i] = add(value[i], other.value[i], carry);
  202.  
  203. return *this;
  204. }
  205.  
  206. LongInt& LongInt::operator -=(const LongInt& other)
  207. {
  208. bool borrow = false;
  209.  
  210. for (unsigned i = 0; i != BITS; ++i)
  211. value[i] = sub(value[i], other.value[i], borrow);
  212.  
  213. return *this;
  214. }
  215.  
  216. LongInt& LongInt::operator *=(const LongInt& other)
  217. {
  218. LongInt temp(*this);
  219. value.reset();
  220.  
  221. bool hasMoreZeroes = temp.value.count() < other.value.count();
  222.  
  223. const LongInt& mult1 = hasMoreZeroes ? temp : other;
  224. const LongInt& mult2 = hasMoreZeroes ? other : temp;
  225.  
  226. for (unsigned shift = 0; shift != BITS; ++shift)
  227. if (mult1.value.test(shift)) (*this) += (mult2 << shift);
  228.  
  229. return *this;
  230. }
  231.  
  232. LongInt& LongInt::operator /=(const LongInt& other)
  233. {
  234. SignedDivide(LongInt(*this), other, *this, LongInt());
  235. return *this;
  236. }
  237.  
  238. LongInt& LongInt::operator %=(const LongInt& other)
  239. {
  240. SignedDivide(LongInt(*this), other, LongInt(), *this);
  241. return *this;
  242. }
  243.  
  244. LongInt& LongInt::operator |=(const LongInt& other)
  245. {
  246. value |= other.value;
  247. return *this;
  248. }
  249.  
  250. LongInt& LongInt::operator ^=(const LongInt& other)
  251. {
  252. value ^= other.value;
  253. return *this;
  254. }
  255.  
  256. LongInt& LongInt::operator &=(const LongInt& other)
  257. {
  258. value &= other.value;
  259. return *this;
  260. }
  261.  
  262. LongInt& LongInt::operator <<=(unsigned shift) // знаковый сдвиг влево совпадает с беззнаковым
  263. {
  264. value <<= shift;
  265. return *this;
  266. }
  267.  
  268. LongInt& LongInt::operator >>=(unsigned shift) // знаковый сдвиг вправо на основе беззнакового
  269. {
  270. unsigned MSB = BITS - 1;
  271.  
  272. value.flip(MSB);
  273. value >>= shift;
  274.  
  275. LongInt tmp;
  276. if (shift <= MSB) tmp.value.set(MSB - shift);
  277.  
  278. return *this -= tmp;
  279. }
  280.  
  281.  
  282. // Префиксный инкремент/декремент изменят свой объект
  283.  
  284. LongInt& LongInt::operator ++()
  285. {
  286. return *this += 1;
  287. }
  288.  
  289. LongInt& LongInt::operator --()
  290. {
  291. return *this -= 1;
  292. }
  293.  
  294. // Постфиксный инкремент/декремент использует префиксную версию.
  295. // Все изменения, внесенные в ++, воспринимаюстя ++(int) автоматически.
  296.  
  297. const LongInt LongInt::operator ++(int)
  298. {
  299. LongInt temp(*this);
  300. ++(*this);
  301. return temp;
  302. }
  303.  
  304. const LongInt LongInt::operator --(int)
  305. {
  306. LongInt temp(*this);
  307. --(*this);
  308. return temp;
  309. }
  310.  
  311. // Неявное приведение к bool.
  312. // Используется в конструкциях вида if (a) ...
  313. // Прежде, чем раскомментировать эту функцию,
  314. // нужно написать перегруженные фукнции для каждой операции, для каждого встроенного типа.
  315. // Иначе, код не будет компилироваться из-за невозможности однозначно подобрать нужное преобразование.
  316. /*
  317. LongInt::operator bool() const
  318. {
  319.   return value.any();
  320. }
  321. */
  322.  
  323. // Унарные операторы.
  324. // Возвращают const Obj, чтобы не компилировалось следующее: -b += c;
  325.  
  326. const LongInt LongInt::operator ~() const
  327. {
  328. LongInt temp(*this);
  329. temp.value.flip();
  330. return temp;
  331. }
  332.  
  333. const LongInt LongInt::operator -() const //-a == ~a + 1 == ~(a - 1)
  334. {
  335. return ~(*this - 1);
  336. }
  337.  
  338. // Все бинарные операторы вида Res operator @(L, R) используют Res operator @=(R)
  339. // Правки вносятся только в operator @=. operator @ воспринимает изменения автоматически.
  340. // ****
  341. // Все бинарные операторы реализованы, как свободные функции. Этот прием позволяет _не_ухудшать_
  342. // инкапсуляцию и, как следствие, делать более переносимый код. Класс LongInt может полностью поменяться
  343. // сохранив лишь интерфейс и это не отразится на работе операторов.
  344. // ****
  345. // Наличие свободного бинарного оператора позволяет записывать выражения вроде 5 + LongInt(10).
  346. // 5 будет неявно преобразовано к LongInt, потому, что у LongInt есть соответсвующий конструктор.
  347.  
  348. const LongInt operator +(const LongInt& left, const LongInt& right)
  349. {
  350. LongInt temp(left);
  351. temp += right;
  352. return temp;
  353. }
  354.  
  355. const LongInt operator -(const LongInt& left, const LongInt& right)
  356. {
  357. LongInt temp(left);
  358. temp -= right;
  359. return temp;
  360. }
  361.  
  362. const LongInt operator *(const LongInt& left, const LongInt& right)
  363. {
  364. LongInt temp(left);
  365. temp *= right;
  366. return temp;
  367. }
  368.  
  369. const LongInt operator /(const LongInt& left, const LongInt& right)
  370. {
  371. LongInt temp(left);
  372. temp /= right;
  373. return temp;
  374. }
  375.  
  376. const LongInt operator %(const LongInt& left, const LongInt& right)
  377. {
  378. LongInt temp(left);
  379. temp %= right;
  380. return temp;
  381. }
  382.  
  383. const LongInt operator |(const LongInt& left, const LongInt& right)
  384. {
  385. LongInt temp(left);
  386. temp |= right;
  387. return temp;
  388. }
  389.  
  390. const LongInt operator ^(const LongInt& left, const LongInt& right)
  391. {
  392. LongInt temp(left);
  393. temp ^= right;
  394. return temp;
  395. }
  396.  
  397. const LongInt operator &(const LongInt& left, const LongInt& right)
  398. {
  399. LongInt temp(left);
  400. temp &= right;
  401. return temp;
  402. }
  403.  
  404. const LongInt operator <<(const LongInt& value, unsigned shift)
  405. {
  406. LongInt temp(value);
  407. temp <<= shift;
  408. return temp;
  409. }
  410.  
  411. const LongInt operator >>(const LongInt& value, unsigned shift)
  412. {
  413. LongInt temp(value);
  414. temp >>= shift;
  415. return temp;
  416. }
  417.  
  418. const bool operator ==(const LongInt& left, const LongInt& right)
  419. {
  420. return left.IsEqual(right);
  421. }
  422.  
  423. const bool operator !=(const LongInt& left, const LongInt& right)
  424. {
  425. return !(left == right);
  426. }
  427.  
  428. const bool operator <(const LongInt& left, const LongInt& right)
  429. {
  430. return left.IsLess(right);
  431. }
  432.  
  433. const bool operator <=(const LongInt& left, const LongInt& right)
  434. {
  435. return (left < right) || (left == right);
  436. }
  437.  
  438. const bool operator >(const LongInt& left, const LongInt& right)
  439. {
  440. return !(left <= right);
  441. }
  442.  
  443. const bool operator >=(const LongInt& left, const LongInt& right)
  444. {
  445. return !(left < right);
  446. }
  447.  
  448. // Функция установки разряда
  449.  
  450. void LongInt::Set(unsigned position, unsigned value)
  451. {
  452. *this += Pow(BASE, position) * LongInt(std::min(value, BASE - 1) - Get(position));
  453. }
  454.  
  455. unsigned LongInt::Get(unsigned position) const
  456. {
  457. LongInt lDigit = Pow(BASE, position); // единица данного разряда
  458. LongInt hDigit = position =lDigit * BASE; // единица следующего разряда
  459.  
  460. return Abs(*this % hDigit / lDigit).value.to_ulong();
  461. }
  462.  
  463. // Функция деления длинных чисел, считающая частное и остаток.
  464.  
  465. void LongInt::Divide(const LongInt& left, const LongInt& right, LongInt& quotient, LongInt& reminder)
  466. {
  467. if (right == 0)
  468. throw std::domain_error("division by zero");
  469.  
  470. quotient.value.reset();
  471.  
  472. if (left == right)
  473. {
  474. quotient.value.set(0);
  475. }
  476. else
  477. {
  478. reminder = left;
  479.  
  480. if (left >= right)
  481. {
  482. unsigned leftMsbIndex = 0;
  483. for (leftMsbIndex = BITS - 1; !left.value[leftMsbIndex] && leftMsbIndex >= 0; --leftMsbIndex);
  484.  
  485. unsigned rightMsbIndex = 0;
  486. for (rightMsbIndex = BITS - 1; !right.value[rightMsbIndex] && rightMsbIndex >= 0; --rightMsbIndex);
  487.  
  488. unsigned alignment = leftMsbIndex - rightMsbIndex;
  489. LongInt temp(right << alignment);
  490.  
  491. do
  492. {
  493. if (temp <= reminder)
  494. {
  495. quotient.value.set(alignment);
  496. reminder -= temp;
  497. }
  498.  
  499. temp >>= 1;
  500. }
  501. while (alignment--);
  502. }
  503. }
  504. }
  505.  
  506. void LongInt::SignedDivide(const LongInt& left, const LongInt& right, LongInt& quotient, LongInt& reminder)
  507. {
  508. bool leftSign = left < 0;
  509. bool rightSign = right < 0;
  510.  
  511. if (leftSign && rightSign)
  512. Divide(-left, -right, quotient, reminder);
  513. else if (leftSign && !rightSign)
  514. Divide(-left, right, quotient, reminder);
  515. else if (!leftSign && rightSign)
  516. Divide(left, -right, quotient, reminder);
  517. else
  518. Divide(left, right, quotient, reminder);
  519.  
  520. if (leftSign && rightSign)
  521. {
  522. reminder = -reminder;
  523. }
  524. else if (leftSign && !rightSign)
  525. {
  526. quotient = -quotient;
  527. reminder = -reminder;
  528. }
  529. else if (!leftSign && rightSign)
  530. {
  531. quotient = -quotient;
  532. }
  533. }
  534.  
  535. size_t LongInt::size()
  536. {
  537. return BITS / (log(BASE) / log(2));
  538. }
  539.  
  540. // Дополнительные возможности реализованы, как свободные функции по тем же причинам, что и бинарные операторы.
  541.  
  542. const LongInt Gcd(const LongInt& left, const LongInt& right)
  543. {
  544. LongInt a = left, b = right;
  545.  
  546. while (a > 0 && b > 0)
  547. a >= b ? a = a % b : b = b % a;
  548.  
  549. return a + b; //одно из них всегда равно 0
  550. }
  551.  
  552. const LongInt Pow(const LongInt& number, unsigned pow) //быстрое возведение в степень
  553. {
  554. LongInt result = 1;
  555. LongInt temp = number;
  556.  
  557. while (pow)
  558. {
  559. if (pow & 1) // pow % 2 == 1
  560. result *= temp;
  561.  
  562. temp *= temp;
  563. pow >>= 1;
  564. }
  565. // Можно в одну строчку: while(pow = pow & 1 ? (result *= temp, pow - 1) : (temp *= temp, pow >> 1));
  566. // но будьте готовы, что коллеги вас побьют.
  567.  
  568. return result;
  569. }
  570.  
  571. const LongInt Abs(const LongInt& number)
  572. {
  573. return number >= 0 ? number : -number;
  574. }
  575.  
  576. const LongInt Factorial(const LongInt& number)
  577. {
  578. LongInt result = 1;
  579.  
  580. if (number > 1)
  581. {
  582. LongInt temp = number + 1; // +1, чтобы избежать постфиксного декремента.
  583. // Постфиксный декремент(как и инкремент) работает медленнее т.к. создает временный объект.
  584. while (--temp > 0)
  585. result *= temp;
  586. }
  587.  
  588. return result;
  589. }

Report this snippet  

You need to login to post a comment.