1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.util;
23
24 import java.math.BigInteger;
25
26 import org.hipparchus.exception.Localizable;
27 import org.hipparchus.exception.LocalizedCoreFormats;
28 import org.hipparchus.exception.MathRuntimeException;
29 import org.hipparchus.exception.MathIllegalArgumentException;
30
31 /**
32 * Some useful, arithmetics related, additions to the built-in functions in
33 * {@link Math}.
34 */
35 public final class ArithmeticUtils {
36
37 /** Private constructor. */
38 private ArithmeticUtils() {
39 super();
40 }
41
42 /**
43 * Add two integers, checking for overflow.
44 *
45 * @param x an addend
46 * @param y an addend
47 * @return the sum {@code x+y}
48 * @throws MathRuntimeException if the result can not be represented
49 * as an {@code int}.
50 */
51 public static int addAndCheck(int x, int y)
52 throws MathRuntimeException {
53 long s = (long) x + (long) y; // NOPMD - casts are intentional here
54 if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
55 throw new MathRuntimeException(LocalizedCoreFormats.OVERFLOW_IN_ADDITION, x, y);
56 }
57 return (int)s;
58 }
59
60 /**
61 * Add two long integers, checking for overflow.
62 *
63 * @param a an addend
64 * @param b an addend
65 * @return the sum {@code a+b}
66 * @throws MathRuntimeException if the result can not be represented as an long
67 */
68 public static long addAndCheck(long a, long b) throws MathRuntimeException {
69 return addAndCheck(a, b, LocalizedCoreFormats.OVERFLOW_IN_ADDITION);
70 }
71
72 /**
73 * Computes the greatest common divisor of the absolute value of two
74 * numbers, using a modified version of the "binary gcd" method.
75 * See Knuth 4.5.2 algorithm B.
76 * The algorithm is due to Josef Stein (1961).
77 * <br>
78 * Special cases:
79 * <ul>
80 * <li>The invocations
81 * {@code gcd(Integer.MIN_VALUE, Integer.MIN_VALUE)},
82 * {@code gcd(Integer.MIN_VALUE, 0)} and
83 * {@code gcd(0, Integer.MIN_VALUE)} throw an
84 * {@code ArithmeticException}, because the result would be 2^31, which
85 * is too large for an int value.</li>
86 * <li>The result of {@code gcd(x, x)}, {@code gcd(0, x)} and
87 * {@code gcd(x, 0)} is the absolute value of {@code x}, except
88 * for the special cases above.</li>
89 * <li>The invocation {@code gcd(0, 0)} is the only one which returns
90 * {@code 0}.</li>
91 * </ul>
92 *
93 * @param p Number.
94 * @param q Number.
95 * @return the greatest common divisor (never negative).
96 * @throws MathRuntimeException if the result cannot be represented as
97 * a non-negative {@code int} value.
98 */
99 public static int gcd(int p, int q) throws MathRuntimeException {
100 int a = p;
101 int b = q;
102 if (a == 0 ||
103 b == 0) {
104 if (a == Integer.MIN_VALUE ||
105 b == Integer.MIN_VALUE) {
106 throw new MathRuntimeException(LocalizedCoreFormats.GCD_OVERFLOW_32_BITS,
107 p, q);
108 }
109 return FastMath.abs(a + b);
110 }
111
112 long al = a;
113 long bl = b;
114 boolean useLong = false;
115 if (a < 0) {
116 if(Integer.MIN_VALUE == a) {
117 useLong = true;
118 } else {
119 a = -a;
120 }
121 al = -al;
122 }
123 if (b < 0) {
124 if (Integer.MIN_VALUE == b) {
125 useLong = true;
126 } else {
127 b = -b;
128 }
129 bl = -bl;
130 }
131 if (useLong) {
132 if(al == bl) {
133 throw new MathRuntimeException(LocalizedCoreFormats.GCD_OVERFLOW_32_BITS,
134 p, q);
135 }
136 long blbu = bl;
137 bl = al;
138 al = blbu % al;
139 if (al == 0) {
140 if (bl > Integer.MAX_VALUE) {
141 throw new MathRuntimeException(LocalizedCoreFormats.GCD_OVERFLOW_32_BITS,
142 p, q);
143 }
144 return (int) bl;
145 }
146 blbu = bl;
147
148 // Now "al" and "bl" fit in an "int".
149 b = (int) al;
150 a = (int) (blbu % al);
151 }
152
153 return gcdPositive(a, b);
154 }
155
156 /**
157 * Computes the greatest common divisor of two <em>positive</em> numbers
158 * (this precondition is <em>not</em> checked and the result is undefined
159 * if not fulfilled) using the "binary gcd" method which avoids division
160 * and modulo operations.
161 * See Knuth 4.5.2 algorithm B.
162 * The algorithm is due to Josef Stein (1961).
163 * <p>
164 * Special cases:
165 * <ul>
166 * <li>The result of {@code gcd(x, x)}, {@code gcd(0, x)} and
167 * {@code gcd(x, 0)} is the value of {@code x}.</li>
168 * <li>The invocation {@code gcd(0, 0)} is the only one which returns
169 * {@code 0}.</li>
170 * </ul>
171 *
172 * @param a Positive number.
173 * @param b Positive number.
174 * @return the greatest common divisor.
175 */
176 private static int gcdPositive(int a, int b) {
177 if (a == 0) {
178 return b;
179 }
180 else if (b == 0) {
181 return a;
182 }
183
184 // Make "a" and "b" odd, keeping track of common power of 2.
185 final int aTwos = Integer.numberOfTrailingZeros(a);
186 a >>= aTwos;
187 final int bTwos = Integer.numberOfTrailingZeros(b);
188 b >>= bTwos;
189 final int shift = FastMath.min(aTwos, bTwos);
190
191 // "a" and "b" are positive.
192 // If a > b then "gdc(a, b)" is equal to "gcd(a - b, b)".
193 // If a < b then "gcd(a, b)" is equal to "gcd(b - a, a)".
194 // Hence, in the successive iterations:
195 // "a" becomes the absolute difference of the current values,
196 // "b" becomes the minimum of the current values.
197 while (a != b) {
198 final int delta = a - b;
199 b = Math.min(a, b);
200 a = Math.abs(delta);
201
202 // Remove any power of 2 in "a" ("b" is guaranteed to be odd).
203 a >>= Integer.numberOfTrailingZeros(a);
204 }
205
206 // Recover the common power of 2.
207 return a << shift;
208 }
209
210 /**
211 * Gets the greatest common divisor of the absolute value of two numbers,
212 * using the "binary gcd" method which avoids division and modulo
213 * operations. See Knuth 4.5.2 algorithm B. This algorithm is due to Josef
214 * Stein (1961).
215 * <p>
216 * Special cases:
217 * <ul>
218 * <li>The invocations
219 * {@code gcd(Long.MIN_VALUE, Long.MIN_VALUE)},
220 * {@code gcd(Long.MIN_VALUE, 0L)} and
221 * {@code gcd(0L, Long.MIN_VALUE)} throw an
222 * {@code ArithmeticException}, because the result would be 2^63, which
223 * is too large for a long value.</li>
224 * <li>The result of {@code gcd(x, x)}, {@code gcd(0L, x)} and
225 * {@code gcd(x, 0L)} is the absolute value of {@code x}, except
226 * for the special cases above.
227 * <li>The invocation {@code gcd(0L, 0L)} is the only one which returns
228 * {@code 0L}.</li>
229 * </ul>
230 *
231 * @param p Number.
232 * @param q Number.
233 * @return the greatest common divisor, never negative.
234 * @throws MathRuntimeException if the result cannot be represented as
235 * a non-negative {@code long} value.
236 */
237 public static long gcd(final long p, final long q) throws MathRuntimeException {
238 long u = p;
239 long v = q;
240 if ((u == 0) || (v == 0)) {
241 if ((u == Long.MIN_VALUE) || (v == Long.MIN_VALUE)){
242 throw new MathRuntimeException(LocalizedCoreFormats.GCD_OVERFLOW_64_BITS,
243 p, q);
244 }
245 return FastMath.abs(u) + FastMath.abs(v);
246 }
247 // keep u and v negative, as negative integers range down to
248 // -2^63, while positive numbers can only be as large as 2^63-1
249 // (i.e. we can't necessarily negate a negative number without
250 // overflow)
251 /* assert u!=0 && v!=0; */
252 if (u > 0) {
253 u = -u;
254 } // make u negative
255 if (v > 0) {
256 v = -v;
257 } // make v negative
258 // B1. [Find power of 2]
259 int k = 0;
260 while ((u & 1) == 0 && (v & 1) == 0 && k < 63) { // while u and v are
261 // both even...
262 u /= 2;
263 v /= 2;
264 k++; // cast out twos.
265 }
266 if (k == 63) {
267 throw new MathRuntimeException(LocalizedCoreFormats.GCD_OVERFLOW_64_BITS,
268 p, q);
269 }
270 // B2. Initialize: u and v have been divided by 2^k and at least
271 // one is odd.
272 long t = ((u & 1) == 1) ? v : -(u / 2)/* B3 */;
273 // t negative: u was odd, v may be even (t replaces v)
274 // t positive: u was even, v is odd (t replaces u)
275 do {
276 /* assert u<0 && v<0; */
277 // B4/B3: cast out twos from t.
278 while ((t & 1) == 0) { // while t is even..
279 t /= 2; // cast out twos
280 }
281 // B5 [reset max(u,v)]
282 if (t > 0) {
283 u = -t;
284 } else {
285 v = t;
286 }
287 // B6/B3. at this point both u and v should be odd.
288 t = (v - u) / 2;
289 // |u| larger: t positive (replace u)
290 // |v| larger: t negative (replace v)
291 } while (t != 0);
292 return -u * (1L << k); // gcd is u*2^k
293 }
294
295 /**
296 * Returns the least common multiple of the absolute value of two numbers,
297 * using the formula {@code lcm(a,b) = (a / gcd(a,b)) * b}.
298 * <p>
299 * Special cases:
300 * <ul>
301 * <li>The invocations {@code lcm(Integer.MIN_VALUE, n)} and
302 * {@code lcm(n, Integer.MIN_VALUE)}, where {@code abs(n)} is a
303 * power of 2, throw an {@code ArithmeticException}, because the result
304 * would be 2^31, which is too large for an int value.</li>
305 * <li>The result of {@code lcm(0, x)} and {@code lcm(x, 0)} is
306 * {@code 0} for any {@code x}.
307 * </ul>
308 *
309 * @param a Number.
310 * @param b Number.
311 * @return the least common multiple, never negative.
312 * @throws MathRuntimeException if the result cannot be represented as
313 * a non-negative {@code int} value.
314 */
315 public static int lcm(int a, int b) throws MathRuntimeException {
316 if (a == 0 || b == 0){
317 return 0;
318 }
319 int lcm = FastMath.abs(mulAndCheck(a / gcd(a, b), b));
320 if (lcm == Integer.MIN_VALUE) {
321 throw new MathRuntimeException(LocalizedCoreFormats.LCM_OVERFLOW_32_BITS, a, b);
322 }
323 return lcm;
324 }
325
326 /**
327 * Returns the least common multiple of the absolute value of two numbers,
328 * using the formula {@code lcm(a,b) = (a / gcd(a,b)) * b}.
329 * <p>
330 * Special cases:
331 * <ul>
332 * <li>The invocations {@code lcm(Long.MIN_VALUE, n)} and
333 * {@code lcm(n, Long.MIN_VALUE)}, where {@code abs(n)} is a
334 * power of 2, throw an {@code ArithmeticException}, because the result
335 * would be 2^63, which is too large for an int value.</li>
336 * <li>The result of {@code lcm(0L, x)} and {@code lcm(x, 0L)} is
337 * {@code 0L} for any {@code x}.
338 * </ul>
339 *
340 * @param a Number.
341 * @param b Number.
342 * @return the least common multiple, never negative.
343 * @throws MathRuntimeException if the result cannot be represented
344 * as a non-negative {@code long} value.
345 */
346 public static long lcm(long a, long b) throws MathRuntimeException {
347 if (a == 0 || b == 0){
348 return 0;
349 }
350 long lcm = FastMath.abs(mulAndCheck(a / gcd(a, b), b));
351 if (lcm == Long.MIN_VALUE){
352 throw new MathRuntimeException(LocalizedCoreFormats.LCM_OVERFLOW_64_BITS, a, b);
353 }
354 return lcm;
355 }
356
357 /**
358 * Multiply two integers, checking for overflow.
359 *
360 * @param x Factor.
361 * @param y Factor.
362 * @return the product {@code x * y}.
363 * @throws MathRuntimeException if the result can not be
364 * represented as an {@code int}.
365 */
366 public static int mulAndCheck(int x, int y) throws MathRuntimeException {
367 long m = ((long) x) * ((long) y); // NOPMD - casts are intentional here
368 if (m < Integer.MIN_VALUE || m > Integer.MAX_VALUE) {
369 throw new MathRuntimeException(LocalizedCoreFormats.ARITHMETIC_EXCEPTION);
370 }
371 return (int)m;
372 }
373
374 /**
375 * Multiply two long integers, checking for overflow.
376 *
377 * @param a Factor.
378 * @param b Factor.
379 * @return the product {@code a * b}.
380 * @throws MathRuntimeException if the result can not be represented
381 * as a {@code long}.
382 */
383 public static long mulAndCheck(long a, long b) throws MathRuntimeException {
384 long ret;
385 if (a > b) {
386 // use symmetry to reduce boundary cases
387 ret = mulAndCheck(b, a);
388 } else {
389 if (a < 0) {
390 if (b < 0) {
391 // check for positive overflow with negative a, negative b
392 if (a >= Long.MAX_VALUE / b) {
393 ret = a * b;
394 } else {
395 throw new MathRuntimeException(LocalizedCoreFormats.ARITHMETIC_EXCEPTION);
396 }
397 } else if (b > 0) {
398 // check for negative overflow with negative a, positive b
399 if (Long.MIN_VALUE / b <= a) {
400 ret = a * b;
401 } else {
402 throw new MathRuntimeException(LocalizedCoreFormats.ARITHMETIC_EXCEPTION);
403
404 }
405 } else {
406 // assert b == 0
407 ret = 0;
408 }
409 } else if (a > 0) {
410 // assert a > 0
411 // assert b > 0
412
413 // check for positive overflow with positive a, positive b
414 if (a <= Long.MAX_VALUE / b) {
415 ret = a * b;
416 } else {
417 throw new MathRuntimeException(LocalizedCoreFormats.ARITHMETIC_EXCEPTION);
418 }
419 } else {
420 // assert a == 0
421 ret = 0;
422 }
423 }
424 return ret;
425 }
426
427 /**
428 * Subtract two integers, checking for overflow.
429 *
430 * @param x Minuend.
431 * @param y Subtrahend.
432 * @return the difference {@code x - y}.
433 * @throws MathRuntimeException if the result can not be represented
434 * as an {@code int}.
435 */
436 public static int subAndCheck(int x, int y) throws MathRuntimeException {
437 long s = (long) x - (long) y; // NOPMD - casts are intentional here
438 if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
439 throw new MathRuntimeException(LocalizedCoreFormats.OVERFLOW_IN_SUBTRACTION, x, y);
440 }
441 return (int)s;
442 }
443
444 /**
445 * Subtract two long integers, checking for overflow.
446 *
447 * @param a Value.
448 * @param b Value.
449 * @return the difference {@code a - b}.
450 * @throws MathRuntimeException if the result can not be represented as a
451 * {@code long}.
452 */
453 public static long subAndCheck(long a, long b) throws MathRuntimeException {
454 long ret;
455 if (b == Long.MIN_VALUE) {
456 if (a < 0) {
457 ret = a - b;
458 } else {
459 throw new MathRuntimeException(LocalizedCoreFormats.OVERFLOW_IN_ADDITION, a, -b);
460 }
461 } else {
462 // use additive inverse
463 ret = addAndCheck(a, -b, LocalizedCoreFormats.OVERFLOW_IN_ADDITION);
464 }
465 return ret;
466 }
467
468 /**
469 * Raise an int to an int power.
470 *
471 * @param k Number to raise.
472 * @param e Exponent (must be positive or zero).
473 * @return \( k^e \)
474 * @throws MathIllegalArgumentException if {@code e < 0}.
475 * @throws MathRuntimeException if the result would overflow.
476 */
477 public static int pow(final int k,
478 final int e)
479 throws MathIllegalArgumentException,
480 MathRuntimeException {
481 if (e < 0) {
482 throw new MathIllegalArgumentException(LocalizedCoreFormats.EXPONENT, e);
483 }
484
485 int exp = e;
486 int result = 1;
487 int k2p = k;
488 while (true) {
489 if ((exp & 0x1) != 0) {
490 result = mulAndCheck(result, k2p);
491 }
492
493 exp >>= 1;
494 if (exp == 0) {
495 break;
496 }
497
498 k2p = mulAndCheck(k2p, k2p);
499 }
500
501 return result;
502 }
503
504 /**
505 * Raise a long to an int power.
506 *
507 * @param k Number to raise.
508 * @param e Exponent (must be positive or zero).
509 * @return \( k^e \)
510 * @throws MathIllegalArgumentException if {@code e < 0}.
511 * @throws MathRuntimeException if the result would overflow.
512 */
513 public static long pow(final long k,
514 final int e)
515 throws MathIllegalArgumentException,
516 MathRuntimeException {
517 if (e < 0) {
518 throw new MathIllegalArgumentException(LocalizedCoreFormats.EXPONENT, e);
519 }
520
521 int exp = e;
522 long result = 1;
523 long k2p = k;
524 while (true) {
525 if ((exp & 0x1) != 0) {
526 result = mulAndCheck(result, k2p);
527 }
528
529 exp >>= 1;
530 if (exp == 0) {
531 break;
532 }
533
534 k2p = mulAndCheck(k2p, k2p);
535 }
536
537 return result;
538 }
539
540 /**
541 * Raise a BigInteger to an int power.
542 *
543 * @param k Number to raise.
544 * @param e Exponent (must be positive or zero).
545 * @return k<sup>e</sup>
546 * @throws MathIllegalArgumentException if {@code e < 0}.
547 */
548 public static BigInteger pow(final BigInteger k, int e) throws MathIllegalArgumentException {
549 if (e < 0) {
550 throw new MathIllegalArgumentException(LocalizedCoreFormats.EXPONENT, e);
551 }
552
553 return k.pow(e);
554 }
555
556 /**
557 * Raise a BigInteger to a long power.
558 *
559 * @param k Number to raise.
560 * @param e Exponent (must be positive or zero).
561 * @return k<sup>e</sup>
562 * @throws MathIllegalArgumentException if {@code e < 0}.
563 */
564 public static BigInteger pow(final BigInteger k, long e) throws MathIllegalArgumentException {
565 if (e < 0) {
566 throw new MathIllegalArgumentException(LocalizedCoreFormats.EXPONENT, e);
567 }
568
569 BigInteger result = BigInteger.ONE;
570 BigInteger k2p = k;
571 while (e != 0) {
572 if ((e & 0x1) != 0) {
573 result = result.multiply(k2p);
574 }
575 k2p = k2p.multiply(k2p);
576 e >>= 1;
577 }
578
579 return result;
580
581 }
582
583 /**
584 * Raise a BigInteger to a BigInteger power.
585 *
586 * @param k Number to raise.
587 * @param e Exponent (must be positive or zero).
588 * @return k<sup>e</sup>
589 * @throws MathIllegalArgumentException if {@code e < 0}.
590 */
591 public static BigInteger pow(final BigInteger k, BigInteger e) throws MathIllegalArgumentException {
592 if (e.compareTo(BigInteger.ZERO) < 0) {
593 throw new MathIllegalArgumentException(LocalizedCoreFormats.EXPONENT, e);
594 }
595
596 BigInteger result = BigInteger.ONE;
597 BigInteger k2p = k;
598 while (!BigInteger.ZERO.equals(e)) {
599 if (e.testBit(0)) {
600 result = result.multiply(k2p);
601 }
602 k2p = k2p.multiply(k2p);
603 e = e.shiftRight(1);
604 }
605
606 return result;
607 }
608
609 /**
610 * Add two long integers, checking for overflow.
611 *
612 * @param a Addend.
613 * @param b Addend.
614 * @param pattern Pattern to use for any thrown exception.
615 * @return the sum {@code a + b}.
616 * @throws MathRuntimeException if the result cannot be represented
617 * as a {@code long}.
618 */
619 private static long addAndCheck(long a, long b, Localizable pattern) throws MathRuntimeException {
620 final long result = a + b;
621 if (!((a ^ b) < 0 || (a ^ result) >= 0)) {
622 throw new MathRuntimeException(pattern, a, b);
623 }
624 return result;
625 }
626
627 /**
628 * Returns true if the argument is a power of two.
629 *
630 * @param n the number to test
631 * @return true if the argument is a power of two
632 */
633 public static boolean isPowerOfTwo(long n) {
634 return (n > 0) && ((n & (n - 1)) == 0);
635 }
636
637 /**
638 * Returns the unsigned remainder from dividing the first argument
639 * by the second where each argument and the result is interpreted
640 * as an unsigned value.
641 * <p>
642 * This method does not use the {@code long} datatype.
643 *
644 * @param dividend the value to be divided
645 * @param divisor the value doing the dividing
646 * @return the unsigned remainder of the first argument divided by
647 * the second argument.
648 */
649 public static int remainderUnsigned(int dividend, int divisor) {
650 if (divisor >= 0) {
651 if (dividend >= 0) {
652 return dividend % divisor;
653 }
654 // The implementation is a Java port of algorithm described in the book
655 // "Hacker's Delight" (section "Unsigned short division from signed division").
656 int q = ((dividend >>> 1) / divisor) << 1;
657 dividend -= q * divisor;
658 if (dividend < 0 || dividend >= divisor) {
659 dividend -= divisor;
660 }
661 return dividend;
662 }
663 return dividend >= 0 || dividend < divisor ? dividend : dividend - divisor;
664 }
665
666 /**
667 * Returns the unsigned remainder from dividing the first argument
668 * by the second where each argument and the result is interpreted
669 * as an unsigned value.
670 * <p>
671 * This method does not use the {@code BigInteger} datatype.
672 *
673 * @param dividend the value to be divided
674 * @param divisor the value doing the dividing
675 * @return the unsigned remainder of the first argument divided by
676 * the second argument.
677 */
678 public static long remainderUnsigned(long dividend, long divisor) {
679 if (divisor >= 0L) {
680 if (dividend >= 0L) {
681 return dividend % divisor;
682 }
683 // The implementation is a Java port of algorithm described in the book
684 // "Hacker's Delight" (section "Unsigned short division from signed division").
685 long q = ((dividend >>> 1) / divisor) << 1;
686 dividend -= q * divisor;
687 if (dividend < 0L || dividend >= divisor) {
688 dividend -= divisor;
689 }
690 return dividend;
691 }
692 return dividend >= 0L || dividend < divisor ? dividend : dividend - divisor;
693 }
694
695 /**
696 * Returns the unsigned quotient of dividing the first argument by
697 * the second where each argument and the result is interpreted as
698 * an unsigned value.
699 * <p>
700 * Note that in two's complement arithmetic, the three other
701 * basic arithmetic operations of add, subtract, and multiply are
702 * bit-wise identical if the two operands are regarded as both
703 * being signed or both being unsigned. Therefore separate {@code
704 * addUnsigned}, etc. methods are not provided.
705 * <p>
706 * This method does not use the {@code long} datatype.
707 *
708 * @param dividend the value to be divided
709 * @param divisor the value doing the dividing
710 * @return the unsigned quotient of the first argument divided by
711 * the second argument
712 */
713 public static int divideUnsigned(int dividend, int divisor) {
714 if (divisor >= 0) {
715 if (dividend >= 0) {
716 return dividend / divisor;
717 }
718 // The implementation is a Java port of algorithm described in the book
719 // "Hacker's Delight" (section "Unsigned short division from signed division").
720 int q = ((dividend >>> 1) / divisor) << 1;
721 dividend -= q * divisor;
722 if (dividend < 0L || dividend >= divisor) {
723 q++;
724 }
725 return q;
726 }
727 return dividend >= 0 || dividend < divisor ? 0 : 1;
728 }
729
730 /**
731 * Returns the unsigned quotient of dividing the first argument by
732 * the second where each argument and the result is interpreted as
733 * an unsigned value.
734 * <p>
735 * Note that in two's complement arithmetic, the three other
736 * basic arithmetic operations of add, subtract, and multiply are
737 * bit-wise identical if the two operands are regarded as both
738 * being signed or both being unsigned. Therefore separate {@code
739 * addUnsigned}, etc. methods are not provided.
740 * <p>
741 * This method does not use the {@code BigInteger} datatype.
742 *
743 * @param dividend the value to be divided
744 * @param divisor the value doing the dividing
745 * @return the unsigned quotient of the first argument divided by
746 * the second argument.
747 */
748 public static long divideUnsigned(long dividend, long divisor) {
749 if (divisor >= 0L) {
750 if (dividend >= 0L) {
751 return dividend / divisor;
752 }
753 // The implementation is a Java port of algorithm described in the book
754 // "Hacker's Delight" (section "Unsigned short division from signed division").
755 long q = ((dividend >>> 1) / divisor) << 1;
756 dividend -= q * divisor;
757 if (dividend < 0L || dividend >= divisor) {
758 q++;
759 }
760 return q;
761 }
762 return dividend >= 0L || dividend < divisor ? 0L : 1L;
763 }
764
765 }