defender-security / vendor / brick / math / src / BigInteger.php

BigInteger.php in Defender Security – Malware Scanner, Login Security & Firewall 3.1.0, at vendor/brick/math/src/BigInteger.php

1,167 lines 33.8 KB

Raw Download Zip

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	}
1167