API tools faq
paste
Guest User

Untitled

a guest
Nov 23rd, 2017
67
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 24.49 KB | None | 0 0
raw download clone embed print report
  1. #ifndef WIZ_UTILITY_INT128_H
  2. #define WIZ_UTILITY_INT128_H
  3.  
  4. #include <cassert>
  5. #include <cstdint>
  6. #include <cstddef>
  7. #include <cstring>
  8. #include <cstdlib>
  9. #include <utility>
  10. #include <string>
  11. #include <iostream>
  12.  
  13. namespace wiz {
  14. struct Int128 {
  15. Int128()
  16. : low(0), high(0) {}
  17.  
  18. Int128(const Int128& other) = default;
  19. Int128(Int128&& other) = default;
  20.  
  21. explicit Int128(std::int8_t value)
  22. : low(value < 0
  23. ? (((static_cast<uint64_t>(-value) ^ 0xFF) + 1) | (0xFFFFFFFFFFFFFF00))
  24. : static_cast<uint64_t>(value)),
  25. high(value < 0 ? UINT64_MAX : 0) {}
  26.  
  27. explicit Int128(std::int16_t value)
  28. : low(value < 0
  29. ? (((static_cast<uint64_t>(-value) ^ 0xFFFF) + 1) | (0xFFFFFFFFFFFF0000))
  30. : static_cast<uint64_t>(value)),
  31. high(value < 0 ? UINT64_MAX : 0) {}
  32.  
  33. explicit Int128(std::int32_t value)
  34. : low(value < 0
  35. ? (((static_cast<uint64_t>(-value) ^ 0xFFFFFFFF) + 1) | (0xFFFFFFFF00000000))
  36. : static_cast<uint64_t>(value)),
  37. high(value < 0 ? UINT64_MAX : 0) {}
  38.  
  39. explicit Int128(std::int64_t value)
  40. : low(value < 0
  41. ? ((static_cast<uint64_t>(-value) ^ UINT64_MAX) + 1)
  42. : static_cast<uint64_t>(value)),
  43. high(value < 0 ? UINT64_MAX : 0) {}
  44.  
  45. explicit Int128(std::uint8_t value)
  46. : low(value), high(0) {}
  47.  
  48. explicit Int128(std::uint16_t value)
  49. : low(value), high(0) {}
  50.  
  51. explicit Int128(std::uint32_t value)
  52. : low(value), high(0) {}
  53.  
  54. explicit Int128(std::uint64_t value)
  55. : low(value), high(0) {}
  56.  
  57. Int128(std::uint64_t low, std::uint64_t high)
  58. : low(low), high(high) {}
  59.  
  60. static Int128 zero() {
  61. return Int128(0, 0);
  62. }
  63.  
  64. static Int128 one() {
  65. return Int128(1, 0);
  66. }
  67.  
  68. static Int128 minValue() {
  69. return Int128(0, 0x8000000000000000);
  70. }
  71.  
  72. static Int128 maxValue() {
  73. return Int128(UINT64_MAX, 0x7FFFFFFFFFFFFFFF);
  74. }
  75.  
  76. enum class ParseResult {
  77. Success,
  78. InvalidArgument,
  79. FormatError,
  80. RangeError,
  81. };
  82.  
  83. static std::pair<ParseResult, Int128> parse(const char* str, std::size_t base = 10) {
  84. std::size_t length = std::strlen(str);
  85. return parse(str, str + length, base);
  86. }
  87.  
  88. template <class InputIterator>
  89. static std::pair<ParseResult, Int128> parse(InputIterator first, InputIterator last, std::size_t base = 10, bool negative = false) {
  90. if (base < 2 || base > 36 || first == last) {
  91. return {ParseResult::InvalidArgument, zero()};
  92. }
  93.  
  94. if (!negative) {
  95. if (first != last) {
  96. if (*first == '-') {
  97. negative = true;
  98. ++first;
  99. } else if (*first == '+') {
  100. ++first;
  101. }
  102. }
  103. }
  104.  
  105. std::pair<CheckedArithmeticResult, Int128> result = {CheckedArithmeticResult::Success, zero()};
  106.  
  107. if (first == last) {
  108. return {ParseResult::FormatError, zero()};
  109. }
  110.  
  111. while (first != last) {
  112. result = result.second.checkedMultiply(Int128(base, 0));
  113. if (result.first == CheckedArithmeticResult::OverflowError) {
  114. return {ParseResult::RangeError, zero()};
  115. }
  116.  
  117. const auto c = static_cast<uint8_t>(*first);
  118.  
  119. Int128 digit;
  120. if (c >= '0' && c <= '0' + base) {
  121. digit = Int128(c - '0');
  122. } else if (base > 10 && c >= 'a' && c <= ('a' + base - 10)) {
  123. digit = Int128((c - 'a') + 10);
  124. } else if (base > 10 && c >= 'A' && c <= ('A' + base - 10)) {
  125. digit = Int128((c - 'A') + 10);
  126. } else {
  127. return {ParseResult::FormatError, zero()};
  128. }
  129.  
  130. result = result.second.checkedAdd(negative ? -digit : digit);
  131. if (result.first == CheckedArithmeticResult::OverflowError) {
  132. return {ParseResult::RangeError, zero()};
  133. }
  134.  
  135. ++first;
  136. }
  137.  
  138. return {ParseResult::Success, result.second};
  139. }
  140.  
  141. bool isZero() const {
  142. return low == 0 && high == 0;
  143. }
  144.  
  145. bool isPositive() const {
  146. return !isZero() && !isNegative();
  147. }
  148.  
  149. bool isNegative() const {
  150. return (high & 0x8000000000000000) != 0;
  151. }
  152.  
  153. Int128 getAbsoluteValue() const {
  154. return isNegative() ? -*this : *this;
  155. }
  156.  
  157. bool getBit(std::size_t bit) const {
  158. if (bit >= 128) {
  159. return 0;
  160. } else if (bit >= 64) {
  161. return (high & (static_cast<uint64_t>(1) << static_cast<uint64_t>(bit - 64))) != 0;
  162. } else {
  163. return (low & (static_cast<uint64_t>(1) << static_cast<uint64_t>(bit))) != 0;
  164. }
  165. }
  166.  
  167. void setBit(std::size_t bit, bool value) {
  168. if (bit >= 128) {
  169. return;
  170. } else if (bit >= 64) {
  171. std::uint64_t mask = static_cast<uint64_t>(1) << static_cast<uint64_t>(bit - 64);
  172. if (value) {
  173. high |= mask;
  174. } else {
  175. high &= ~mask;
  176. }
  177. } else {
  178. std::uint64_t mask = static_cast<uint64_t>(1) << static_cast<uint64_t>(bit);
  179. if (value) {
  180. low |= mask;
  181. } else {
  182. low &= ~mask;
  183. }
  184. }
  185. }
  186.  
  187. Int128 logicalShiftLeftOnce() const {
  188. return Int128(low << 1, (high << 1) | (low >> 63));
  189. }
  190.  
  191. Int128 logicalShiftRightOnce() const {
  192. return Int128((low >> 1) | (high << 63), high >> 1);
  193. }
  194.  
  195. Int128 arithmeticShiftRightOnce() const {
  196. return Int128((low >> 1) | (high << 63), (high >> 1) | (high & 0x8000000000000000));
  197. }
  198.  
  199. Int128 logicalShiftLeft(std::size_t bits) const {
  200. return *this << bits;
  201. }
  202.  
  203. Int128 logicalShiftRight(std::size_t bits) const {
  204. if (bits == 0) {
  205. return *this;
  206. } else if (bits >= 128) {
  207. return zero();
  208. } else if (bits >= 64) {
  209. return Int128(high >> (bits - 64), 0);
  210. } else {
  211. return Int128((low >> bits) | (high << (64 - bits)), high >> bits);
  212. }
  213. }
  214.  
  215. Int128 arithmeticShiftLeft(std::size_t bits) const {
  216. return *this << bits;
  217. }
  218.  
  219. Int128 arithmeticShiftRight(std::size_t bits) const {
  220. if (bits == 0) {
  221. return *this;
  222. } else if (bits >= 128) {
  223. return isNegative() ? Int128(-1) : zero();
  224. } else if (bits >= 64) {
  225. return Int128((high >> (bits - 64)) | (isNegative() ? (UINT64_MAX << (64 - (bits - 64))) : 0), UINT64_MAX);
  226. } else {
  227. return Int128((low >> bits) | (high << (64 - bits)), (high >> bits) | (isNegative() ? (UINT64_MAX << (64 - bits)) : 0));
  228. }
  229. }
  230.  
  231. std::pair<Int128, Int128> unsignedDivisionWithRemainder(Int128 other) const {
  232. if (other.isZero()) {
  233. assert(!other.isZero());
  234. std::abort();
  235. return {zero(), zero()};
  236. } else if (other == one()) {
  237. return {*this, zero()};
  238. } else if (*this == other) {
  239. return {one(), zero()};
  240. } else if (isZero() || (*this != minValue() && *this < other)) {
  241. return {zero(), *this};
  242. } else if (high == 0 && other.high == 0) {
  243. return {Int128(low / other.low, 0), Int128(low % other.low, 0)};
  244. } else {
  245. auto quotient = zero();
  246. auto remainder = zero();
  247. for (std::size_t i = findMostSignificantBit(); i >= 0 && i <= 128; --i) {
  248. remainder = remainder.logicalShiftLeftOnce();
  249. remainder.setBit(0, getBit(i));
  250. if (remainder >= other) {
  251. remainder -= other;
  252. quotient.setBit(i, true);
  253. }
  254. }
  255. return {quotient, remainder};
  256. }
  257. }
  258.  
  259. std::pair<Int128, Int128> divisionWithRemainder(Int128 other) const {
  260. if (isNegative()) {
  261. const auto negativeThis = -*this;
  262. if (other.isNegative()) {
  263. const auto result = negativeThis.unsignedDivisionWithRemainder(-other);
  264. return {result.first, -result.second};
  265. } else {
  266. const auto result = negativeThis.unsignedDivisionWithRemainder(other);
  267. return {-result.first, -result.second};
  268. }
  269. } else {
  270. if (other.isNegative()) {
  271. const auto result = unsignedDivisionWithRemainder(-other);
  272. return {-result.first, result.second};
  273. } else {
  274. return unsignedDivisionWithRemainder(other);
  275. }
  276. }
  277. }
  278.  
  279. std::size_t findLeastSignificantBit() const {
  280. std::size_t index = 0;
  281. auto value = *this;
  282. while (!value.getBit(0)) {
  283. ++index;
  284. value = value.logicalShiftRightOnce();
  285. }
  286. return index;
  287. }
  288.  
  289. std::size_t findMostSignificantBit() const {
  290. std::size_t index = 0;
  291. auto value = *this;
  292. while (!value.isZero()) {
  293. ++index;
  294. value = value.logicalShiftRightOnce();
  295. }
  296. return index;
  297. }
  298.  
  299. std::string toString(std::size_t base = 10) const {
  300. if (base < 2 || base >= 36) {
  301. return "";
  302. }
  303.  
  304. const auto negative = isNegative();
  305. if (base == 10 && (high == 0 || (low < 0x8000000000000000 && high == UINT64_MAX))) {
  306. if (negative) {
  307. return std::to_string(-static_cast<int64_t>((low - 1) ^ UINT64_MAX));
  308. } else {
  309. return std::to_string(low);
  310. }
  311. } else {
  312. char buffer[129] = {0};
  313. std::size_t bufferIndex = 128;
  314. std::pair<Int128, Int128> quotientAndRemainder(getAbsoluteValue(), zero());
  315.  
  316. do {
  317. quotientAndRemainder = quotientAndRemainder.first.unsignedDivisionWithRemainder(Int128(base));
  318. if (quotientAndRemainder.second.low < 10) {
  319. buffer[--bufferIndex] = static_cast<char>(quotientAndRemainder.second.low + '0');
  320. } else if (quotientAndRemainder.second.low < 36) {
  321. buffer[--bufferIndex] = static_cast<char>(quotientAndRemainder.second.low - 10 + 'a');
  322. }
  323. } while (!quotientAndRemainder.first.isZero());
  324.  
  325. if (negative) {
  326. buffer[--bufferIndex] = '-';
  327. }
  328.  
  329. return std::string(&buffer[bufferIndex]);
  330. }
  331. }
  332.  
  333. enum class CheckedArithmeticResult {
  334. Success,
  335. OverflowError,
  336. DivideByZeroError
  337. };
  338.  
  339. std::pair<CheckedArithmeticResult, Int128> checkedAdd(Int128 other) const {
  340. if (isNegative()) {
  341. if (other.isNegative() && *this < minValue() - other) {
  342. return {CheckedArithmeticResult::OverflowError, zero()};
  343. }
  344. } else {
  345. if (!other.isNegative() && *this > maxValue() - other) {
  346. return {CheckedArithmeticResult::OverflowError, zero()};
  347. }
  348. }
  349. return {CheckedArithmeticResult::Success, *this + other};
  350. }
  351.  
  352. std::pair<CheckedArithmeticResult, Int128> checkedSubtract(Int128 other) const {
  353. if (isNegative()) {
  354. if (!other.isNegative() && *this < minValue() + other) {
  355. return {CheckedArithmeticResult::OverflowError, zero()};
  356. }
  357. } else {
  358. if (other.isNegative() && *this > maxValue() + other) {
  359. return {CheckedArithmeticResult::OverflowError, zero()};
  360. }
  361. }
  362. return {CheckedArithmeticResult::Success, *this - other};
  363. }
  364.  
  365. std::pair<CheckedArithmeticResult, Int128> checkedMultiply(Int128 other) const {
  366. Int128 result;
  367. if (isZero() || other.isZero()) {
  368. return {CheckedArithmeticResult::Success, Int128()};
  369. }
  370.  
  371. if (isNegative()) {
  372. if (other.isNegative()) {
  373. if (other < maxValue() / *this) {
  374. return {CheckedArithmeticResult::OverflowError, Int128()};
  375. }
  376. } else {
  377. const auto limit = minValue() / other;
  378. if (*this < limit) {
  379. return {CheckedArithmeticResult::OverflowError, Int128()};
  380. }
  381. }
  382. } else {
  383. if (other.isNegative()) {
  384. if (other < minValue() / *this) {
  385. return {CheckedArithmeticResult::OverflowError, Int128()};
  386. }
  387. } else {
  388. if (*this > maxValue() / other) {
  389. return {CheckedArithmeticResult::OverflowError, Int128()};
  390. }
  391. }
  392. }
  393.  
  394. return {CheckedArithmeticResult::Success, *this * other};
  395. }
  396.  
  397.  
  398. std::pair<CheckedArithmeticResult, Int128> checkedDivide(Int128 other) const {
  399. if (other.isZero()) {
  400. return {CheckedArithmeticResult::DivideByZeroError, Int128()};
  401. } else if (*this == minValue() && other == Int128(-1)) {
  402. return {CheckedArithmeticResult::OverflowError, Int128()};
  403. }
  404.  
  405. return {CheckedArithmeticResult::Success, *this / other};
  406. }
  407.  
  408. std::pair<CheckedArithmeticResult, Int128> checkedModulo(Int128 other) const {
  409. if (other.isZero()) {
  410. return {CheckedArithmeticResult::DivideByZeroError, Int128()};
  411. } else if (*this == minValue() && other == Int128(-1)) {
  412. return {CheckedArithmeticResult::OverflowError, Int128()};
  413. }
  414.  
  415. return {CheckedArithmeticResult::Success, *this % other};
  416. }
  417.  
  418. std::pair<CheckedArithmeticResult, Int128> checkedLogicalShiftLeft(std::size_t bits) const {
  419. if (!isZero()) {
  420. if (bits >= 128 || (bits > 0 && !logicalShiftRight(127 - bits).isZero())) {
  421. return {CheckedArithmeticResult::OverflowError, Int128()};
  422. }
  423. }
  424. return {CheckedArithmeticResult::Success, *this << bits};
  425. }
  426.  
  427. explicit operator std::int8_t() const {
  428. return isNegative() ? -static_cast<std::int8_t>((low - 1) ^ UINT64_MAX) : static_cast<std::int8_t>(low);
  429. }
  430.  
  431. explicit operator std::int16_t() const {
  432. return isNegative() ? -static_cast<std::int16_t>((low - 1) ^ UINT64_MAX) : static_cast<std::int16_t>(low);
  433. }
  434.  
  435. explicit operator std::int32_t() const {
  436. return isNegative() ? -static_cast<std::int32_t>((low - 1) ^ UINT64_MAX) : static_cast<std::int32_t>(low);
  437. }
  438.  
  439. explicit operator std::int64_t() const {
  440. return isNegative() ? -static_cast<std::int64_t>((low - 1) ^ UINT64_MAX) : static_cast<std::int64_t>(low);
  441. }
  442.  
  443. explicit operator std::uint8_t() const {
  444. return static_cast<std::uint8_t>(low);
  445. }
  446.  
  447. explicit operator std::uint16_t() const {
  448. return static_cast<std::uint16_t>(low);
  449. }
  450.  
  451. explicit operator std::uint32_t() const {
  452. return static_cast<std::uint32_t>(low);
  453. }
  454.  
  455. explicit operator std::uint64_t() const {
  456. return static_cast<std::uint64_t>(low);
  457. }
  458.  
  459. Int128& operator =(const Int128& other) = default;
  460. Int128& operator =(Int128&& other) = default;
  461.  
  462. bool operator ==(Int128 other) const {
  463. return low == other.low && high == other.high;
  464. }
  465.  
  466. bool operator !=(Int128 other) const {
  467. return !(*this == other);
  468. }
  469.  
  470. bool operator <(Int128 other) const {
  471. if (isNegative()) {
  472. if (other.isNegative()) {
  473. return high < other.high
  474. || high == other.high && low < other.low;
  475. } else {
  476. return true;
  477. }
  478. } else {
  479. if (other.isNegative()) {
  480. return false;
  481. } else {
  482. return high < other.high
  483. || high == other.high && low < other.low;
  484. }
  485. }
  486. }
  487.  
  488. bool operator <=(Int128 other) const {
  489. return !(other < *this);
  490. }
  491.  
  492. bool operator >(Int128 other) const {
  493. return other < *this;
  494. }
  495.  
  496. bool operator >=(Int128 other) const {
  497. return !(*this < other);
  498. }
  499.  
  500. Int128 operator ~() const {
  501. return Int128(~low, ~high);
  502. }
  503.  
  504. Int128 operator +() const {
  505. return *this;
  506. }
  507.  
  508. Int128 operator -() const {
  509. Int128 result = ~*this;
  510. ++result;
  511. return result;
  512. }
  513.  
  514. Int128 operator &(Int128 other) const {
  515. return Int128(low & other.low, high & other.high);
  516. }
  517.  
  518. Int128 operator |(Int128 other) const {
  519. return Int128(low | other.low, high | other.high);
  520. }
  521.  
  522. Int128 operator ^(Int128 other) const {
  523. return Int128(low ^ other.low, high ^ other.high);
  524. }
  525.  
  526. Int128 operator <<(std::size_t bits) const {
  527. if (bits == 0) {
  528. return *this;
  529. } else if (bits >= 128) {
  530. return zero();
  531. } else if (bits >= 64) {
  532. return Int128(0, low << (bits - 64));
  533. } else {
  534. return Int128(low << bits, (high << bits) | (low >> (64 - bits)));
  535. }
  536. }
  537.  
  538. Int128& operator --() {
  539. if (low == 0) {
  540. --high;
  541. }
  542. --low;
  543. return *this;
  544. }
  545.  
  546. Int128& operator ++() {
  547. ++low;
  548. if (low == 0) {
  549. ++high;
  550. }
  551. return *this;
  552. }
  553.  
  554. Int128 operator --(int) {
  555. Int128 result = *this;
  556. --*this;
  557. return result;
  558. }
  559.  
  560. Int128 operator ++(int) {
  561. Int128 result = *this;
  562. ++*this;
  563. return result;
  564. }
  565.  
  566. Int128 operator +(Int128 other) const {
  567. const auto carry = other.low > UINT64_MAX - low;
  568. return Int128(low + other.low, high + other.high + (carry ? 1 : 0));
  569. }
  570.  
  571. Int128 operator -(Int128 other) const {
  572. return *this + -other;
  573. }
  574.  
  575. Int128 operator *(Int128 other) const {
  576. if (other == one()) {
  577. return *this;
  578. } else if (isZero() || other.isZero()) {
  579. return Int128();
  580. } else if (((high == 0 || high == UINT64_MAX) && low <= UINT32_MAX) && ((other.high == 0 || other.high == UINT64_MAX) && other.low <= UINT32_MAX)) {
  581. return Int128(low * other.low, (high == UINT64_MAX) != (other.high == UINT64_MAX) ? UINT64_MAX : 0);
  582. } else {
  583. // First do a 64 x 64 -> 128-bit multiply.
  584. //
  585. // a * b
  586. // = (2^32 * ah + al) * (2^32 * bh + bl) [rewriting 64-bit values in their split 32-bit form]
  587. // = 2^64 * ah * bh + 2^32 * ah * bl + 2^32 * al * bh + al * bl [expanding product]
  588. // = w + z + y + x [giving names to each sub-product]
  589. //
  590. // x: 32 x 32 -> 64-bit product, bits 0..63
  591. // y and z: 32 x 32 -> 64-bit product, shifted by 32 bits, bits 32..95
  592. // w: 32 x 32 -> 64-bit product, bits 64..128
  593. // addition happens across lo/hi word boundaries and can generate middle carries, so we need to add each piece separately as 128-bit integers.
  594. //
  595. // Then to make a 128 x 128 -> 128-bit multiply, we do similarly, but since we're asking for 128-bit instead of 256-bit result,
  596. // we discard the upper product, and just keep the lower 128 bits of the result.
  597. //
  598. // 2^128 * (ah64 * bh64) + 2^64 * (ah64 * bl64 + al64 * bh64) + (al64 * bl64)
  599. // = 2^64 * (ah64 * bl64 + al64 * bh64) + (al64 * bl64) modulo 2^128 [note: al64 * bl64 was figured out by 64x64 -> 64 multiply]
  600. const auto al = low & 0xFFFFFFFF;
  601. const auto ah = (low >> 32) & 0xFFFFFFFF;
  602. const auto bl = other.low & 0xFFFFFFFF;
  603. const auto bh = (other.low >> 32) & 0xFFFFFFFF;
  604. const auto x = al * bl;
  605. const auto y = al * bh;
  606. const auto z = ah * bl;
  607. const auto w = ah * bh;
  608. return Int128(x, 0) + Int128(y << 32, y >> 32) + Int128(z << 32, z >> 32) + Int128(0, w + low * other.high + high * other.low);
  609. }
  610. }
  611.  
  612. Int128 operator /(Int128 other) const {
  613. return divisionWithRemainder(other).first;
  614. }
  615.  
  616. Int128 operator %(Int128 other) const {
  617. return divisionWithRemainder(other).second;
  618. }
  619.  
  620. Int128& operator +=(Int128 other) {
  621. *this = *this + other;
  622. return *this;
  623. }
  624.  
  625. Int128& operator -=(Int128 other) {
  626. *this = *this - other;
  627. return *this;
  628. }
  629.  
  630. Int128& operator *=(Int128 other) {
  631. *this = *this * other;
  632. return *this;
  633. }
  634.  
  635. Int128& operator /=(Int128 other) {
  636. *this = *this / other;
  637. return *this;
  638. }
  639.  
  640. Int128& operator %=(Int128 other) {
  641. *this = *this % other;
  642. return *this;
  643. }
  644.  
  645. Int128& operator &=(Int128 other) {
  646. *this = *this & other;
  647. return *this;
  648. }
  649.  
  650. Int128& operator |=(Int128 other) {
  651. *this = *this | other;
  652. return *this;
  653. }
  654.  
  655. Int128& operator ^=(Int128 other) {
  656. *this = *this ^ other;
  657. return *this;
  658. }
  659.  
  660. Int128& operator <<=(std::size_t bits) {
  661. *this = *this << bits;
  662. return *this;
  663. }
  664.  
  665. friend std::ostream& operator<<(std::ostream& out, const Int128& value);
  666.  
  667. std::uint64_t low;
  668. std::uint64_t high;
  669. };
  670.  
  671. inline std::ostream& operator <<(std::ostream& out, const Int128& value) {
  672. const auto negative = value.isNegative();
  673. if (value.high == 0 || (value.low < 0x8000000000000000 && value.high == UINT64_MAX)) {
  674. if (negative) {
  675. out << -static_cast<int64_t>((value.low - 1) ^ UINT64_MAX);
  676. } else {
  677. out << value.low;
  678. }
  679. } else {
  680. std::size_t base = 10;
  681. if ((out.flags() & out.dec) != 0) {
  682. base = 10;
  683. } else if ((out.flags() & out.hex) != 0) {
  684. base = 16;
  685. } else if ((out.flags() & out.oct) != 0) {
  686. base = 8;
  687. }
  688.  
  689. char buffer[129] = {0};
  690. std::size_t bufferIndex = 128;
  691. std::pair<Int128, Int128> quotientAndRemainder(value.getAbsoluteValue(), Int128::zero());
  692.  
  693. do {
  694. quotientAndRemainder = quotientAndRemainder.first.unsignedDivisionWithRemainder(Int128(base));
  695. if (quotientAndRemainder.second.low < 10) {
  696. buffer[--bufferIndex] = static_cast<char>(quotientAndRemainder.second.low + '0');
  697. } else if (quotientAndRemainder.second.low < 36) {
  698. buffer[--bufferIndex] = static_cast<char>(quotientAndRemainder.second.low - 10 + 'a');
  699. }
  700. } while (!quotientAndRemainder.first.isZero());
  701.  
  702. if (negative) {
  703. buffer[--bufferIndex] = '-';
  704. }
  705.  
  706. out << &buffer[bufferIndex];
  707. }
  708.  
  709. return out;
  710. }
  711. }
  712.  
  713. #endif
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!