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

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

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