media-cloud-sync / includes / sdk / google / brick / math / src / BigInteger.php

BigInteger.php in Media Cloud Sync 1.2.6, at includes/sdk/google/brick/math/src/BigInteger.php

1,000 lines 33.6 KB

Raw Download Zip

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