[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  declare(strict_types=1);
   4  
   5  namespace Brick\Math;
   6  
   7  use Brick\Math\Exception\DivisionByZeroException;
   8  use Brick\Math\Exception\IntegerOverflowException;
   9  use Brick\Math\Exception\MathException;
  10  use Brick\Math\Exception\NegativeNumberException;
  11  use Brick\Math\Exception\NumberFormatException;
  12  use Brick\Math\Internal\Calculator;
  13  
  14  /**
  15   * An arbitrary-size integer.
  16   *
  17   * All methods accepting a number as a parameter accept either a BigInteger instance,
  18   * an integer, or a string representing an arbitrary size integer.
  19   *
  20   * @psalm-immutable
  21   */
  22  final class BigInteger extends BigNumber
  23  {
  24      /**
  25       * The value, as a string of digits with optional leading minus sign.
  26       *
  27       * No leading zeros must be present.
  28       * No leading minus sign must be present if the number is zero.
  29       *
  30       * @var string
  31       */
  32      private $value;
  33  
  34      /**
  35       * Protected constructor. Use a factory method to obtain an instance.
  36       *
  37       * @param string $value A string of digits, with optional leading minus sign.
  38       */
  39      protected function __construct(string $value)
  40      {
  41          $this->value = $value;
  42      }
  43  
  44      /**
  45       * Creates a BigInteger of the given value.
  46       *
  47       * @param BigNumber|int|float|string $value
  48       *
  49       * @return BigInteger
  50       *
  51       * @throws MathException If the value cannot be converted to a BigInteger.
  52       *
  53       * @psalm-pure
  54       */
  55      public static function of($value) : BigNumber
  56      {
  57          return parent::of($value)->toBigInteger();
  58      }
  59  
  60      /**
  61       * Parses a string containing an integer in an arbitrary base.
  62       *
  63       * @deprecated will be removed in version 0.9 - use fromBase() instead
  64       *
  65       * The string can optionally be prefixed with the `+` or `-` sign.
  66       * For bases greater than 10, both uppercase and lowercase letters are allowed.
  67       *
  68       * @param string $number The number to parse.
  69       * @param int    $base   The base of the number, between 2 and 36.
  70       *
  71       * @return BigInteger
  72       *
  73       * @throws \InvalidArgumentException If the number is invalid or the base is out of range.
  74       */
  75      public static function parse(string $number, int $base = 10) : BigInteger
  76      {
  77          try {
  78              return self::fromBase($number, $base);
  79          } catch (NumberFormatException $e) {
  80              throw new \InvalidArgumentException($e->getMessage(), 0, $e);
  81          }
  82      }
  83  
  84      /**
  85       * Creates a number from a string in a given base.
  86       *
  87       * The string can optionally be prefixed with the `+` or `-` sign.
  88       *
  89       * Bases greater than 36 are not supported by this method, as there is no clear consensus on which of the lowercase
  90       * or uppercase characters should come first. Instead, this method accepts any base up to 36, and does not
  91       * differentiate lowercase and uppercase characters, which are considered equal.
  92       *
  93       * For bases greater than 36, and/or custom alphabets, use the fromArbitraryBase() method.
  94       *
  95       * @param string $number The number to convert, in the given base.
  96       * @param int    $base   The base of the number, between 2 and 36.
  97       *
  98       * @return BigInteger
  99       *
 100       * @throws NumberFormatException     If the number is empty, or contains invalid chars for the given base.
 101       * @throws \InvalidArgumentException If the base is out of range.
 102       *
 103       * @psalm-pure
 104       */
 105      public static function fromBase(string $number, int $base) : BigInteger
 106      {
 107          if ($number === '') {
 108              throw new NumberFormatException('The number cannot be empty.');
 109          }
 110  
 111          if ($base < 2 || $base > 36) {
 112              throw new \InvalidArgumentException(\sprintf('Base %d is not in range 2 to 36.', $base));
 113          }
 114  
 115          if ($number[0] === '-') {
 116              $sign = '-';
 117              $number = \substr($number, 1);
 118          } elseif ($number[0] === '+') {
 119              $sign = '';
 120              $number = \substr($number, 1);
 121          } else {
 122              $sign = '';
 123          }
 124  
 125          if ($number === '') {
 126              throw new NumberFormatException('The number cannot be empty.');
 127          }
 128  
 129          $number = \ltrim($number, '0');
 130  
 131          if ($number === '') {
 132              // The result will be the same in any base, avoid further calculation.
 133              return BigInteger::zero();
 134          }
 135  
 136          if ($number === '1') {
 137              // The result will be the same in any base, avoid further calculation.
 138              return new BigInteger($sign . '1');
 139          }
 140  
 141          $pattern = '/[^' . \substr(Calculator::ALPHABET, 0, $base) . ']/';
 142  
 143          if (\preg_match($pattern, \strtolower($number), $matches) === 1) {
 144              throw new NumberFormatException(\sprintf('"%s" is not a valid character in base %d.', $matches[0], $base));
 145          }
 146  
 147          if ($base === 10) {
 148              // The number is usable as is, avoid further calculation.
 149              return new BigInteger($sign . $number);
 150          }
 151  
 152          $result = Calculator::get()->fromBase($number, $base);
 153  
 154          return new BigInteger($sign . $result);
 155      }
 156  
 157      /**
 158       * Parses a string containing an integer in an arbitrary base, using a custom alphabet.
 159       *
 160       * Because this method accepts an alphabet with any character, including dash, it does not handle negative numbers.
 161       *
 162       * @param string $number   The number to parse.
 163       * @param string $alphabet The alphabet, for example '01' for base 2, or '01234567' for base 8.
 164       *
 165       * @return BigInteger
 166       *
 167       * @throws NumberFormatException     If the given number is empty or contains invalid chars for the given alphabet.
 168       * @throws \InvalidArgumentException If the alphabet does not contain at least 2 chars.
 169       *
 170       * @psalm-pure
 171       */
 172      public static function fromArbitraryBase(string $number, string $alphabet) : BigInteger
 173      {
 174          if ($number === '') {
 175              throw new NumberFormatException('The number cannot be empty.');
 176          }
 177  
 178          $base = \strlen($alphabet);
 179  
 180          if ($base < 2) {
 181              throw new \InvalidArgumentException('The alphabet must contain at least 2 chars.');
 182          }
 183  
 184          $pattern = '/[^' . \preg_quote($alphabet, '/') . ']/';
 185  
 186          if (\preg_match($pattern, $number, $matches) === 1) {
 187              throw NumberFormatException::charNotInAlphabet($matches[0]);
 188          }
 189  
 190          $number = Calculator::get()->fromArbitraryBase($number, $alphabet, $base);
 191  
 192          return new BigInteger($number);
 193      }
 194  
 195      /**
 196       * Translates a string of bytes containing the binary representation of a BigInteger into a BigInteger.
 197       *
 198       * The input string is assumed to be in big-endian byte-order: the most significant byte is in the zeroth element.
 199       *
 200       * If `$signed` is true, the input is assumed to be in two's-complement representation, and the leading bit is
 201       * interpreted as a sign bit. If `$signed` is false, the input is interpreted as an unsigned number, and the
 202       * resulting BigInteger will always be positive or zero.
 203       *
 204       * This method can be used to retrieve a number exported by `toBytes()`, as long as the `$signed` flags match.
 205       *
 206       * @param string $value  The byte string.
 207       * @param bool   $signed Whether to interpret as a signed number in two's-complement representation with a leading
 208       *                       sign bit.
 209       *
 210       * @return BigInteger
 211       *
 212       * @throws NumberFormatException If the string is empty.
 213       */
 214      public static function fromBytes(string $value, bool $signed = true) : BigInteger
 215      {
 216          if ($value === '') {
 217              throw new NumberFormatException('The byte string must not be empty.');
 218          }
 219  
 220          $twosComplement = false;
 221  
 222          if ($signed) {
 223              $x = ord($value[0]);
 224  
 225              if (($twosComplement = ($x >= 0x80))) {
 226                  $value = ~$value;
 227              }
 228          }
 229  
 230          $number = self::fromBase(bin2hex($value), 16);
 231  
 232          if ($twosComplement) {
 233              return $number->plus(1)->negated();
 234          }
 235  
 236          return $number;
 237      }
 238  
 239      /**
 240       * Generates a pseudo-random number in the range 0 to 2^numBits - 1.
 241       *
 242       * Using the default random bytes generator, this method is suitable for cryptographic use.
 243       *
 244       * @param int           $numBits              The number of bits.
 245       * @param callable|null $randomBytesGenerator A function that accepts a number of bytes as an integer, and returns a
 246       *                                            string of random bytes of the given length. Defaults to the
 247       *                                            `random_bytes()` function.
 248       *
 249       * @return BigInteger
 250       *
 251       * @throws \InvalidArgumentException If $numBits is negative.
 252       */
 253      public static function randomBits(int $numBits, ?callable $randomBytesGenerator = null) : BigInteger
 254      {
 255          if ($numBits < 0) {
 256              throw new \InvalidArgumentException('The number of bits cannot be negative.');
 257          }
 258  
 259          if ($numBits === 0) {
 260              return BigInteger::zero();
 261          }
 262  
 263          if ($randomBytesGenerator === null) {
 264              $randomBytesGenerator = 'random_bytes';
 265          }
 266  
 267          $byteLength = intdiv($numBits - 1, 8) + 1;
 268  
 269          $extraBits = ($byteLength * 8 - $numBits);
 270          $bitmask   = chr(0xFF >> $extraBits);
 271  
 272          $randomBytes    = $randomBytesGenerator($byteLength);
 273          $randomBytes[0] = $randomBytes[0] & $bitmask;
 274  
 275          return self::fromBytes($randomBytes, false);
 276      }
 277  
 278      /**
 279       * Generates a pseudo-random number between `$min` and `$max`.
 280       *
 281       * Using the default random bytes generator, this method is suitable for cryptographic use.
 282       *
 283       * @param BigNumber|int|float|string $min                  The lower bound. Must be convertible to a BigInteger.
 284       * @param BigNumber|int|float|string $max                  The upper bound. Must be convertible to a BigInteger.
 285       * @param callable|null              $randomBytesGenerator A function that accepts a number of bytes as an integer,
 286       *                                                         and returns a string of random bytes of the given length.
 287       *                                                         Defaults to the `random_bytes()` function.
 288       *
 289       * @return BigInteger
 290       *
 291       * @throws MathException If one of the parameters cannot be converted to a BigInteger,
 292       *                       or `$min` is greater than `$max`.
 293       */
 294      public static function randomRange($min, $max, ?callable $randomBytesGenerator = null) : BigInteger
 295      {
 296          $min = BigInteger::of($min);
 297          $max = BigInteger::of($max);
 298  
 299          if ($min->isGreaterThan($max)) {
 300              throw new MathException('$min cannot be greater than $max.');
 301          }
 302  
 303          if ($min->isEqualTo($max)) {
 304              return $min;
 305          }
 306  
 307          $diff      = $max->minus($min);
 308          $bitLength = $diff->getBitLength();
 309  
 310          // try until the number is in range (50% to 100% chance of success)
 311          do {
 312              $randomNumber = self::randomBits($bitLength, $randomBytesGenerator);
 313          } while ($randomNumber->isGreaterThan($diff));
 314  
 315          return $randomNumber->plus($min);
 316      }
 317  
 318      /**
 319       * Returns a BigInteger representing zero.
 320       *
 321       * @return BigInteger
 322       *
 323       * @psalm-pure
 324       */
 325      public static function zero() : BigInteger
 326      {
 327          /** @psalm-suppress ImpureStaticVariable */
 328          static $zero;
 329  
 330          if ($zero === null) {
 331              $zero = new BigInteger('0');
 332          }
 333  
 334          return $zero;
 335      }
 336  
 337      /**
 338       * Returns a BigInteger representing one.
 339       *
 340       * @return BigInteger
 341       *
 342       * @psalm-pure
 343       */
 344      public static function one() : BigInteger
 345      {
 346          /** @psalm-suppress ImpureStaticVariable */
 347          static $one;
 348  
 349          if ($one === null) {
 350              $one = new BigInteger('1');
 351          }
 352  
 353          return $one;
 354      }
 355  
 356      /**
 357       * Returns a BigInteger representing ten.
 358       *
 359       * @return BigInteger
 360       *
 361       * @psalm-pure
 362       */
 363      public static function ten() : BigInteger
 364      {
 365          /** @psalm-suppress ImpureStaticVariable */
 366          static $ten;
 367  
 368          if ($ten === null) {
 369              $ten = new BigInteger('10');
 370          }
 371  
 372          return $ten;
 373      }
 374  
 375      /**
 376       * Returns the sum of this number and the given one.
 377       *
 378       * @param BigNumber|int|float|string $that The number to add. Must be convertible to a BigInteger.
 379       *
 380       * @return BigInteger The result.
 381       *
 382       * @throws MathException If the number is not valid, or is not convertible to a BigInteger.
 383       */
 384      public function plus($that) : BigInteger
 385      {
 386          $that = BigInteger::of($that);
 387  
 388          if ($that->value === '0') {
 389              return $this;
 390          }
 391  
 392          if ($this->value === '0') {
 393              return $that;
 394          }
 395  
 396          $value = Calculator::get()->add($this->value, $that->value);
 397  
 398          return new BigInteger($value);
 399      }
 400  
 401      /**
 402       * Returns the difference of this number and the given one.
 403       *
 404       * @param BigNumber|int|float|string $that The number to subtract. Must be convertible to a BigInteger.
 405       *
 406       * @return BigInteger The result.
 407       *
 408       * @throws MathException If the number is not valid, or is not convertible to a BigInteger.
 409       */
 410      public function minus($that) : BigInteger
 411      {
 412          $that = BigInteger::of($that);
 413  
 414          if ($that->value === '0') {
 415              return $this;
 416          }
 417  
 418          $value = Calculator::get()->sub($this->value, $that->value);
 419  
 420          return new BigInteger($value);
 421      }
 422  
 423      /**
 424       * Returns the product of this number and the given one.
 425       *
 426       * @param BigNumber|int|float|string $that The multiplier. Must be convertible to a BigInteger.
 427       *
 428       * @return BigInteger The result.
 429       *
 430       * @throws MathException If the multiplier is not a valid number, or is not convertible to a BigInteger.
 431       */
 432      public function multipliedBy($that) : BigInteger
 433      {
 434          $that = BigInteger::of($that);
 435  
 436          if ($that->value === '1') {
 437              return $this;
 438          }
 439  
 440          if ($this->value === '1') {
 441              return $that;
 442          }
 443  
 444          $value = Calculator::get()->mul($this->value, $that->value);
 445  
 446          return new BigInteger($value);
 447      }
 448  
 449      /**
 450       * Returns the result of the division of this number by the given one.
 451       *
 452       * @param BigNumber|int|float|string $that         The divisor. Must be convertible to a BigInteger.
 453       * @param int                        $roundingMode An optional rounding mode.
 454       *
 455       * @return BigInteger The result.
 456       *
 457       * @throws MathException If the divisor is not a valid number, is not convertible to a BigInteger, is zero,
 458       *                       or RoundingMode::UNNECESSARY is used and the remainder is not zero.
 459       */
 460      public function dividedBy($that, int $roundingMode = RoundingMode::UNNECESSARY) : BigInteger
 461      {
 462          $that = BigInteger::of($that);
 463  
 464          if ($that->value === '1') {
 465              return $this;
 466          }
 467  
 468          if ($that->value === '0') {
 469              throw DivisionByZeroException::divisionByZero();
 470          }
 471  
 472          $result = Calculator::get()->divRound($this->value, $that->value, $roundingMode);
 473  
 474          return new BigInteger($result);
 475      }
 476  
 477      /**
 478       * Returns this number exponentiated to the given value.
 479       *
 480       * @param int $exponent The exponent.
 481       *
 482       * @return BigInteger The result.
 483       *
 484       * @throws \InvalidArgumentException If the exponent is not in the range 0 to 1,000,000.
 485       */
 486      public function power(int $exponent) : BigInteger
 487      {
 488          if ($exponent === 0) {
 489              return BigInteger::one();
 490          }
 491  
 492          if ($exponent === 1) {
 493              return $this;
 494          }
 495  
 496          if ($exponent < 0 || $exponent > Calculator::MAX_POWER) {
 497              throw new \InvalidArgumentException(\sprintf(
 498                  'The exponent %d is not in the range 0 to %d.',
 499                  $exponent,
 500                  Calculator::MAX_POWER
 501              ));
 502          }
 503  
 504          return new BigInteger(Calculator::get()->pow($this->value, $exponent));
 505      }
 506  
 507      /**
 508       * Returns the quotient of the division of this number by the given one.
 509       *
 510       * @param BigNumber|int|float|string $that The divisor. Must be convertible to a BigInteger.
 511       *
 512       * @return BigInteger
 513       *
 514       * @throws DivisionByZeroException If the divisor is zero.
 515       */
 516      public function quotient($that) : BigInteger
 517      {
 518          $that = BigInteger::of($that);
 519  
 520          if ($that->value === '1') {
 521              return $this;
 522          }
 523  
 524          if ($that->value === '0') {
 525              throw DivisionByZeroException::divisionByZero();
 526          }
 527  
 528          $quotient = Calculator::get()->divQ($this->value, $that->value);
 529  
 530          return new BigInteger($quotient);
 531      }
 532  
 533      /**
 534       * Returns the remainder of the division of this number by the given one.
 535       *
 536       * The remainder, when non-zero, has the same sign as the dividend.
 537       *
 538       * @param BigNumber|int|float|string $that The divisor. Must be convertible to a BigInteger.
 539       *
 540       * @return BigInteger
 541       *
 542       * @throws DivisionByZeroException If the divisor is zero.
 543       */
 544      public function remainder($that) : BigInteger
 545      {
 546          $that = BigInteger::of($that);
 547  
 548          if ($that->value === '1') {
 549              return BigInteger::zero();
 550          }
 551  
 552          if ($that->value === '0') {
 553              throw DivisionByZeroException::divisionByZero();
 554          }
 555  
 556          $remainder = Calculator::get()->divR($this->value, $that->value);
 557  
 558          return new BigInteger($remainder);
 559      }
 560  
 561      /**
 562       * Returns the quotient and remainder of the division of this number by the given one.
 563       *
 564       * @param BigNumber|int|float|string $that The divisor. Must be convertible to a BigInteger.
 565       *
 566       * @return BigInteger[] An array containing the quotient and the remainder.
 567       *
 568       * @throws DivisionByZeroException If the divisor is zero.
 569       */
 570      public function quotientAndRemainder($that) : array
 571      {
 572          $that = BigInteger::of($that);
 573  
 574          if ($that->value === '0') {
 575              throw DivisionByZeroException::divisionByZero();
 576          }
 577  
 578          [$quotient, $remainder] = Calculator::get()->divQR($this->value, $that->value);
 579  
 580          return [
 581              new BigInteger($quotient),
 582              new BigInteger($remainder)
 583          ];
 584      }
 585  
 586      /**
 587       * Returns the modulo of this number and the given one.
 588       *
 589       * The modulo operation yields the same result as the remainder operation when both operands are of the same sign,
 590       * and may differ when signs are different.
 591       *
 592       * The result of the modulo operation, when non-zero, has the same sign as the divisor.
 593       *
 594       * @param BigNumber|int|float|string $that The divisor. Must be convertible to a BigInteger.
 595       *
 596       * @return BigInteger
 597       *
 598       * @throws DivisionByZeroException If the divisor is zero.
 599       */
 600      public function mod($that) : BigInteger
 601      {
 602          $that = BigInteger::of($that);
 603  
 604          if ($that->value === '0') {
 605              throw DivisionByZeroException::modulusMustNotBeZero();
 606          }
 607  
 608          $value = Calculator::get()->mod($this->value, $that->value);
 609  
 610          return new BigInteger($value);
 611      }
 612  
 613      /**
 614       * Returns the modular multiplicative inverse of this BigInteger modulo $m.
 615       *
 616       * @param BigInteger $m
 617       *
 618       * @return BigInteger
 619       *
 620       * @throws DivisionByZeroException If $m is zero.
 621       * @throws NegativeNumberException If $m is negative.
 622       * @throws MathException           If this BigInteger has no multiplicative inverse mod m (that is, this BigInteger
 623       *                                 is not relatively prime to m).
 624       */
 625      public function modInverse(BigInteger $m) : BigInteger
 626      {
 627          if ($m->value === '0') {
 628              throw DivisionByZeroException::modulusMustNotBeZero();
 629          }
 630  
 631          if ($m->isNegative()) {
 632              throw new NegativeNumberException('Modulus must not be negative.');
 633          }
 634  
 635          if ($m->value === '1') {
 636              return BigInteger::zero();
 637          }
 638  
 639          $value = Calculator::get()->modInverse($this->value, $m->value);
 640  
 641          if ($value === null) {
 642              throw new MathException('Unable to compute the modInverse for the given modulus.');
 643          }
 644  
 645          return new BigInteger($value);
 646      }
 647  
 648      /**
 649       * Returns this number raised into power with modulo.
 650       *
 651       * This operation only works on positive numbers.
 652       *
 653       * @param BigNumber|int|float|string $exp The positive exponent.
 654       * @param BigNumber|int|float|string $mod The modulus. Must not be zero.
 655       *
 656       * @return BigInteger
 657       *
 658       * @throws NegativeNumberException If any of the operands is negative.
 659       * @throws DivisionByZeroException If the modulus is zero.
 660       */
 661      public function modPow($exp, $mod) : BigInteger
 662      {
 663          $exp = BigInteger::of($exp);
 664          $mod = BigInteger::of($mod);
 665  
 666          if ($this->isNegative() || $exp->isNegative() || $mod->isNegative()) {
 667              throw new NegativeNumberException('The operands cannot be negative.');
 668          }
 669  
 670          if ($mod->isZero()) {
 671              throw DivisionByZeroException::modulusMustNotBeZero();
 672          }
 673  
 674          $result = Calculator::get()->modPow($this->value, $exp->value, $mod->value);
 675  
 676          return new BigInteger($result);
 677      }
 678  
 679      /**
 680       * Returns this number raised into power with modulo.
 681       *
 682       * @deprecated Use modPow() instead.
 683       *
 684       * @param BigNumber|int|float|string $exp The positive exponent.
 685       * @param BigNumber|int|float|string $mod The modulus. Must not be zero.
 686       *
 687       * @return BigInteger
 688       *
 689       * @throws NegativeNumberException If any of the operands is negative.
 690       * @throws DivisionByZeroException If the modulus is zero.
 691       */
 692      public function powerMod($exp, $mod) : BigInteger
 693      {
 694          return $this->modPow($exp, $mod);
 695      }
 696  
 697      /**
 698       * Returns the greatest common divisor of this number and the given one.
 699       *
 700       * The GCD is always positive, unless both operands are zero, in which case it is zero.
 701       *
 702       * @param BigNumber|int|float|string $that The operand. Must be convertible to an integer number.
 703       *
 704       * @return BigInteger
 705       */
 706      public function gcd($that) : BigInteger
 707      {
 708          $that = BigInteger::of($that);
 709  
 710          if ($that->value === '0' && $this->value[0] !== '-') {
 711              return $this;
 712          }
 713  
 714          if ($this->value === '0' && $that->value[0] !== '-') {
 715              return $that;
 716          }
 717  
 718          $value = Calculator::get()->gcd($this->value, $that->value);
 719  
 720          return new BigInteger($value);
 721      }
 722  
 723      /**
 724       * Returns the integer square root number of this number, rounded down.
 725       *
 726       * The result is the largest x such that x² ≤ n.
 727       *
 728       * @return BigInteger
 729       *
 730       * @throws NegativeNumberException If this number is negative.
 731       */
 732      public function sqrt() : BigInteger
 733      {
 734          if ($this->value[0] === '-') {
 735              throw new NegativeNumberException('Cannot calculate the square root of a negative number.');
 736          }
 737  
 738          $value = Calculator::get()->sqrt($this->value);
 739  
 740          return new BigInteger($value);
 741      }
 742  
 743      /**
 744       * Returns the absolute value of this number.
 745       *
 746       * @return BigInteger
 747       */
 748      public function abs() : BigInteger
 749      {
 750          return $this->isNegative() ? $this->negated() : $this;
 751      }
 752  
 753      /**
 754       * Returns the inverse of this number.
 755       *
 756       * @return BigInteger
 757       */
 758      public function negated() : BigInteger
 759      {
 760          return new BigInteger(Calculator::get()->neg($this->value));
 761      }
 762  
 763      /**
 764       * Returns the integer bitwise-and combined with another integer.
 765       *
 766       * This method returns a negative BigInteger if and only if both operands are negative.
 767       *
 768       * @param BigNumber|int|float|string $that The operand. Must be convertible to an integer number.
 769       *
 770       * @return BigInteger
 771       */
 772      public function and($that) : BigInteger
 773      {
 774          $that = BigInteger::of($that);
 775  
 776          return new BigInteger(Calculator::get()->and($this->value, $that->value));
 777      }
 778  
 779      /**
 780       * Returns the integer bitwise-or combined with another integer.
 781       *
 782       * This method returns a negative BigInteger if and only if either of the operands is negative.
 783       *
 784       * @param BigNumber|int|float|string $that The operand. Must be convertible to an integer number.
 785       *
 786       * @return BigInteger
 787       */
 788      public function or($that) : BigInteger
 789      {
 790          $that = BigInteger::of($that);
 791  
 792          return new BigInteger(Calculator::get()->or($this->value, $that->value));
 793      }
 794  
 795      /**
 796       * Returns the integer bitwise-xor combined with another integer.
 797       *
 798       * This method returns a negative BigInteger if and only if exactly one of the operands is negative.
 799       *
 800       * @param BigNumber|int|float|string $that The operand. Must be convertible to an integer number.
 801       *
 802       * @return BigInteger
 803       */
 804      public function xor($that) : BigInteger
 805      {
 806          $that = BigInteger::of($that);
 807  
 808          return new BigInteger(Calculator::get()->xor($this->value, $that->value));
 809      }
 810  
 811      /**
 812       * Returns the integer left shifted by a given number of bits.
 813       *
 814       * @param int $distance The distance to shift.
 815       *
 816       * @return BigInteger
 817       */
 818      public function shiftedLeft(int $distance) : BigInteger
 819      {
 820          if ($distance === 0) {
 821              return $this;
 822          }
 823  
 824          if ($distance < 0) {
 825              return $this->shiftedRight(- $distance);
 826          }
 827  
 828          return $this->multipliedBy(BigInteger::of(2)->power($distance));
 829      }
 830  
 831      /**
 832       * Returns the integer right shifted by a given number of bits.
 833       *
 834       * @param int $distance The distance to shift.
 835       *
 836       * @return BigInteger
 837       */
 838      public function shiftedRight(int $distance) : BigInteger
 839      {
 840          if ($distance === 0) {
 841              return $this;
 842          }
 843  
 844          if ($distance < 0) {
 845              return $this->shiftedLeft(- $distance);
 846          }
 847  
 848          $operand = BigInteger::of(2)->power($distance);
 849  
 850          if ($this->isPositiveOrZero()) {
 851              return $this->quotient($operand);
 852          }
 853  
 854          return $this->dividedBy($operand, RoundingMode::UP);
 855      }
 856  
 857      /**
 858       * Returns the number of bits in the minimal two's-complement representation of this BigInteger, excluding a sign bit.
 859       *
 860       * For positive BigIntegers, this is equivalent to the number of bits in the ordinary binary representation.
 861       * Computes (ceil(log2(this < 0 ? -this : this+1))).
 862       *
 863       * @return int
 864       */
 865      public function getBitLength() : int
 866      {
 867          if ($this->value === '0') {
 868              return 0;
 869          }
 870  
 871          if ($this->isNegative()) {
 872              return $this->abs()->minus(1)->getBitLength();
 873          }
 874  
 875          return strlen($this->toBase(2));
 876      }
 877  
 878      /**
 879       * Returns the index of the rightmost (lowest-order) one bit in this BigInteger.
 880       *
 881       * Returns -1 if this BigInteger contains no one bits.
 882       *
 883       * @return int
 884       */
 885      public function getLowestSetBit() : int
 886      {
 887          $n = $this;
 888          $bitLength = $this->getBitLength();
 889  
 890          for ($i = 0; $i <= $bitLength; $i++) {
 891              if ($n->isOdd()) {
 892                  return $i;
 893              }
 894  
 895              $n = $n->shiftedRight(1);
 896          }
 897  
 898          return -1;
 899      }
 900  
 901      /**
 902       * Returns whether this number is even.
 903       *
 904       * @return bool
 905       */
 906      public function isEven() : bool
 907      {
 908          return in_array($this->value[-1], ['0', '2', '4', '6', '8'], true);
 909      }
 910  
 911      /**
 912       * Returns whether this number is odd.
 913       *
 914       * @return bool
 915       */
 916      public function isOdd() : bool
 917      {
 918          return in_array($this->value[-1], ['1', '3', '5', '7', '9'], true);
 919      }
 920  
 921      /**
 922       * Returns true if and only if the designated bit is set.
 923       *
 924       * Computes ((this & (1<<n)) != 0).
 925       *
 926       * @param int $n The bit to test, 0-based.
 927       *
 928       * @return bool
 929       *
 930       * @throws \InvalidArgumentException If the bit to test is negative.
 931       */
 932      public function testBit(int $n) : bool
 933      {
 934          if ($n < 0) {
 935              throw new \InvalidArgumentException('The bit to test cannot be negative.');
 936          }
 937  
 938          return $this->shiftedRight($n)->isOdd();
 939      }
 940  
 941      /**
 942       * {@inheritdoc}
 943       */
 944      public function compareTo($that) : int
 945      {
 946          $that = BigNumber::of($that);
 947  
 948          if ($that instanceof BigInteger) {
 949              return Calculator::get()->cmp($this->value, $that->value);
 950          }
 951  
 952          return - $that->compareTo($this);
 953      }
 954  
 955      /**
 956       * {@inheritdoc}
 957       */
 958      public function getSign() : int
 959      {
 960          return ($this->value === '0') ? 0 : (($this->value[0] === '-') ? -1 : 1);
 961      }
 962  
 963      /**
 964       * {@inheritdoc}
 965       */
 966      public function toBigInteger() : BigInteger
 967      {
 968          return $this;
 969      }
 970  
 971      /**
 972       * {@inheritdoc}
 973       */
 974      public function toBigDecimal() : BigDecimal
 975      {
 976          return BigDecimal::create($this->value);
 977      }
 978  
 979      /**
 980       * {@inheritdoc}
 981       */
 982      public function toBigRational() : BigRational
 983      {
 984          return BigRational::create($this, BigInteger::one(), false);
 985      }
 986  
 987      /**
 988       * {@inheritdoc}
 989       */
 990      public function toScale(int $scale, int $roundingMode = RoundingMode::UNNECESSARY) : BigDecimal
 991      {
 992          return $this->toBigDecimal()->toScale($scale, $roundingMode);
 993      }
 994  
 995      /**
 996       * {@inheritdoc}
 997       */
 998      public function toInt() : int
 999      {
1000          $intValue = (int) $this->value;
1001  
1002          if ($this->value !== (string) $intValue) {
1003              throw IntegerOverflowException::toIntOverflow($this);
1004          }
1005  
1006          return $intValue;
1007      }
1008  
1009      /**
1010       * {@inheritdoc}
1011       */
1012      public function toFloat() : float
1013      {
1014          return (float) $this->value;
1015      }
1016  
1017      /**
1018       * Returns a string representation of this number in the given base.
1019       *
1020       * The output will always be lowercase for bases greater than 10.
1021       *
1022       * @param int $base
1023       *
1024       * @return string
1025       *
1026       * @throws \InvalidArgumentException If the base is out of range.
1027       */
1028      public function toBase(int $base) : string
1029      {
1030          if ($base === 10) {
1031              return $this->value;
1032          }
1033  
1034          if ($base < 2 || $base > 36) {
1035              throw new \InvalidArgumentException(\sprintf('Base %d is out of range [2, 36]', $base));
1036          }
1037  
1038          return Calculator::get()->toBase($this->value, $base);
1039      }
1040  
1041      /**
1042       * Returns a string representation of this number in an arbitrary base with a custom alphabet.
1043       *
1044       * Because this method accepts an alphabet with any character, including dash, it does not handle negative numbers;
1045       * a NegativeNumberException will be thrown when attempting to call this method on a negative number.
1046       *
1047       * @param string $alphabet The alphabet, for example '01' for base 2, or '01234567' for base 8.
1048       *
1049       * @return string
1050       *
1051       * @throws NegativeNumberException   If this number is negative.
1052       * @throws \InvalidArgumentException If the given alphabet does not contain at least 2 chars.
1053       */
1054      public function toArbitraryBase(string $alphabet) : string
1055      {
1056          $base = \strlen($alphabet);
1057  
1058          if ($base < 2) {
1059              throw new \InvalidArgumentException('The alphabet must contain at least 2 chars.');
1060          }
1061  
1062          if ($this->value[0] === '-') {
1063              throw new NegativeNumberException(__FUNCTION__ . '() does not support negative numbers.');
1064          }
1065  
1066          return Calculator::get()->toArbitraryBase($this->value, $alphabet, $base);
1067      }
1068  
1069      /**
1070       * Returns a string of bytes containing the binary representation of this BigInteger.
1071       *
1072       * The string is in big-endian byte-order: the most significant byte is in the zeroth element.
1073       *
1074       * If `$signed` is true, the output will be in two's-complement representation, and a sign bit will be prepended to
1075       * the output. If `$signed` is false, no sign bit will be prepended, and this method will throw an exception if the
1076       * number is negative.
1077       *
1078       * The string will contain the minimum number of bytes required to represent this BigInteger, including a sign bit
1079       * if `$signed` is true.
1080       *
1081       * This representation is compatible with the `fromBytes()` factory method, as long as the `$signed` flags match.
1082       *
1083       * @param bool $signed Whether to output a signed number in two's-complement representation with a leading sign bit.
1084       *
1085       * @return string
1086       *
1087       * @throws NegativeNumberException If $signed is false, and the number is negative.
1088       */
1089      public function toBytes(bool $signed = true) : string
1090      {
1091          if (! $signed && $this->isNegative()) {
1092              throw new NegativeNumberException('Cannot convert a negative number to a byte string when $signed is false.');
1093          }
1094  
1095          $hex = $this->abs()->toBase(16);
1096  
1097          if (strlen($hex) % 2 !== 0) {
1098              $hex = '0' . $hex;
1099          }
1100  
1101          $baseHexLength = strlen($hex);
1102  
1103          if ($signed) {
1104              if ($this->isNegative()) {
1105                  $hex = bin2hex(~hex2bin($hex));
1106                  $hex = self::fromBase($hex, 16)->plus(1)->toBase(16);
1107  
1108                  $hexLength = strlen($hex);
1109  
1110                  if ($hexLength < $baseHexLength) {
1111                      $hex = str_repeat('0', $baseHexLength - $hexLength) . $hex;
1112                  }
1113  
1114                  if ($hex[0] < '8') {
1115                      $hex = 'FF' . $hex;
1116                  }
1117              } else {
1118                  if ($hex[0] >= '8') {
1119                      $hex = '00' . $hex;
1120                  }
1121              }
1122          }
1123  
1124          return hex2bin($hex);
1125      }
1126  
1127      /**
1128       * {@inheritdoc}
1129       */
1130      public function __toString() : string
1131      {
1132          return $this->value;
1133      }
1134  
1135      /**
1136       * This method is required by interface Serializable and SHOULD NOT be accessed directly.
1137       *
1138       * @internal
1139       *
1140       * @return string
1141       */
1142      public function serialize() : string
1143      {
1144          return $this->value;
1145      }
1146  
1147      /**
1148       * This method is only here to implement interface Serializable and cannot be accessed directly.
1149       *
1150       * @internal
1151       *
1152       * @param string $value
1153       *
1154       * @return void
1155       *
1156       * @throws \LogicException
1157       */
1158      public function unserialize($value) : void
1159      {
1160          if (isset($this->value)) {
1161              throw new \LogicException('unserialize() is an internal function, it must not be called directly.');
1162          }
1163  
1164          $this->value = $value;
1165      }
1166  }