Subversion-Projekte lars-tiefland.laravel_shop

Revision

Zur aktuellen Revision | Details | Letzte Änderung | Log anzeigen | RSS feed

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