1 /*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15 package com.google.common.math;
16
17 import static com.google.common.base.Preconditions.checkArgument;
18 import static com.google.common.base.Preconditions.checkNotNull;
19 import static com.google.common.math.MathPreconditions.checkNoOverflow;
20 import static com.google.common.math.MathPreconditions.checkNonNegative;
21 import static com.google.common.math.MathPreconditions.checkPositive;
22 import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
23 import static java.lang.Math.abs;
24 import static java.lang.Math.min;
25 import static java.math.RoundingMode.HALF_EVEN;
26 import static java.math.RoundingMode.HALF_UP;
27
28 import com.google.common.annotations.Beta;
29 import com.google.common.annotations.GwtCompatible;
30 import com.google.common.annotations.GwtIncompatible;
31 import com.google.common.annotations.VisibleForTesting;
32 import com.google.common.primitives.Ints;
33 import java.math.BigInteger;
34 import java.math.RoundingMode;
35
36 /**
37 * A class for arithmetic on values of type {@code int}. Where possible, methods are defined and
38 * named analogously to their {@code BigInteger} counterparts.
39 *
40 * <p>The implementations of many methods in this class are based on material from Henry S. Warren,
41 * Jr.'s <i>Hacker's Delight</i>, (Addison Wesley, 2002).
42 *
43 * <p>Similar functionality for {@code long} and for {@link BigInteger} can be found in {@link
44 * LongMath} and {@link BigIntegerMath} respectively. For other common operations on {@code int}
45 * values, see {@link com.google.common.primitives.Ints}.
46 *
47 * @author Louis Wasserman
48 * @since 11.0
49 */
50 @GwtCompatible(emulated = true)
51 @ElementTypesAreNonnullByDefault
52 public final class IntMath {
53 // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
54
55 @VisibleForTesting static final int MAX_SIGNED_POWER_OF_TWO = 1 << (Integer.SIZE - 2);
56
57 /**
58 * Returns the smallest power of two greater than or equal to {@code x}. This is equivalent to
59 * {@code checkedPow(2, log2(x, CEILING))}.
60 *
61 * @throws IllegalArgumentException if {@code x <= 0}
62 * @throws ArithmeticException of the next-higher power of two is not representable as an {@code
63 * int}, i.e. when {@code x > 2^30}
64 * @since 20.0
65 */
66 @Beta
67 public static int ceilingPowerOfTwo(int x) {
68 checkPositive("x", x);
69 if (x > MAX_SIGNED_POWER_OF_TWO) {
70 throw new ArithmeticException("ceilingPowerOfTwo(" + x + ") not representable as an int");
71 }
72 return 1 << -Integer.numberOfLeadingZeros(x - 1);
73 }
74
75 /**
76 * Returns the largest power of two less than or equal to {@code x}. This is equivalent to {@code
77 * checkedPow(2, log2(x, FLOOR))}.
78 *
79 * @throws IllegalArgumentException if {@code x <= 0}
80 * @since 20.0
81 */
82 @Beta
83 public static int floorPowerOfTwo(int x) {
84 checkPositive("x", x);
85 return Integer.highestOneBit(x);
86 }
87
88 /**
89 * Returns {@code true} if {@code x} represents a power of two.
90 *
91 * <p>This differs from {@code Integer.bitCount(x) == 1}, because {@code
92 * Integer.bitCount(Integer.MIN_VALUE) == 1}, but {@link Integer#MIN_VALUE} is not a power of two.
93 */
94 public static boolean isPowerOfTwo(int x) {
95 return x > 0 & (x & (x - 1)) == 0;
96 }
97
98 /**
99 * Returns 1 if {@code x < y} as unsigned integers, and 0 otherwise. Assumes that x - y fits into
100 * a signed int. The implementation is branch-free, and benchmarks suggest it is measurably (if
101 * narrowly) faster than the straightforward ternary expression.
102 */
103 @VisibleForTesting
104 static int lessThanBranchFree(int x, int y) {
105 // The double negation is optimized away by normal Java, but is necessary for GWT
106 // to make sure bit twiddling works as expected.
107 return ~~(x - y) >>> (Integer.SIZE - 1);
108 }
109
110 /**
111 * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode.
112 *
113 * @throws IllegalArgumentException if {@code x <= 0}
114 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
115 * is not a power of two
116 */
117 @SuppressWarnings("fallthrough")
118 // TODO(kevinb): remove after this warning is disabled globally
119 public static int log2(int x, RoundingMode mode) {
120 checkPositive("x", x);
121 switch (mode) {
122 case UNNECESSARY:
123 checkRoundingUnnecessary(isPowerOfTwo(x));
124 // fall through
125 case DOWN:
126 case FLOOR:
127 return (Integer.SIZE - 1) - Integer.numberOfLeadingZeros(x);
128
129 case UP:
130 case CEILING:
131 return Integer.SIZE - Integer.numberOfLeadingZeros(x - 1);
132
133 case HALF_DOWN:
134 case HALF_UP:
135 case HALF_EVEN:
136 // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5
137 int leadingZeros = Integer.numberOfLeadingZeros(x);
138 int cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros;
139 // floor(2^(logFloor + 0.5))
140 int logFloor = (Integer.SIZE - 1) - leadingZeros;
141 return logFloor + lessThanBranchFree(cmp, x);
142
143 default:
144 throw new AssertionError();
145 }
146 }
147
148 /** The biggest half power of two that can fit in an unsigned int. */
149 @VisibleForTesting static final int MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333;
150
151 /**
152 * Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode.
153 *
154 * @throws IllegalArgumentException if {@code x <= 0}
155 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
156 * is not a power of ten
157 */
158 @GwtIncompatible // need BigIntegerMath to adequately test
159 @SuppressWarnings("fallthrough")
160 public static int log10(int x, RoundingMode mode) {
161 checkPositive("x", x);
162 int logFloor = log10Floor(x);
163 int floorPow = powersOf10[logFloor];
164 switch (mode) {
165 case UNNECESSARY:
166 checkRoundingUnnecessary(x == floorPow);
167 // fall through
168 case FLOOR:
169 case DOWN:
170 return logFloor;
171 case CEILING:
172 case UP:
173 return logFloor + lessThanBranchFree(floorPow, x);
174 case HALF_DOWN:
175 case HALF_UP:
176 case HALF_EVEN:
177 // sqrt(10) is irrational, so log10(x) - logFloor is never exactly 0.5
178 return logFloor + lessThanBranchFree(halfPowersOf10[logFloor], x);
179 default:
180 throw new AssertionError();
181 }
182 }
183
184 private static int log10Floor(int x) {
185 /*
186 * Based on Hacker's Delight Fig. 11-5, the two-table-lookup, branch-free implementation.
187 *
188 * The key idea is that based on the number of leading zeros (equivalently, floor(log2(x))), we
189 * can narrow the possible floor(log10(x)) values to two. For example, if floor(log2(x)) is 6,
190 * then 64 <= x < 128, so floor(log10(x)) is either 1 or 2.
191 */
192 int y = maxLog10ForLeadingZeros[Integer.numberOfLeadingZeros(x)];
193 /*
194 * y is the higher of the two possible values of floor(log10(x)). If x < 10^y, then we want the
195 * lower of the two possible values, or y - 1, otherwise, we want y.
196 */
197 return y - lessThanBranchFree(x, powersOf10[y]);
198 }
199
200 // maxLog10ForLeadingZeros[i] == floor(log10(2^(Long.SIZE - i)))
201 @VisibleForTesting
202 static final byte[] maxLog10ForLeadingZeros = {
203 9, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0,
204 0
205 };
206
207 @VisibleForTesting
208 static final int[] powersOf10 = {
209 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000
210 };
211
212 // halfPowersOf10[i] = largest int less than 10^(i + 0.5)
213 @VisibleForTesting
214 static final int[] halfPowersOf10 = {
215 3, 31, 316, 3162, 31622, 316227, 3162277, 31622776, 316227766, Integer.MAX_VALUE
216 };
217
218 /**
219 * Returns {@code b} to the {@code k}th power. Even if the result overflows, it will be equal to
220 * {@code BigInteger.valueOf(b).pow(k).intValue()}. This implementation runs in {@code O(log k)}
221 * time.
222 *
223 * <p>Compare {@link #checkedPow}, which throws an {@link ArithmeticException} upon overflow.
224 *
225 * @throws IllegalArgumentException if {@code k < 0}
226 */
227 @GwtIncompatible // failing tests
228 public static int pow(int b, int k) {
229 checkNonNegative("exponent", k);
230 switch (b) {
231 case 0:
232 return (k == 0) ? 1 : 0;
233 case 1:
234 return 1;
235 case (-1):
236 return ((k & 1) == 0) ? 1 : -1;
237 case 2:
238 return (k < Integer.SIZE) ? (1 << k) : 0;
239 case (-2):
240 if (k < Integer.SIZE) {
241 return ((k & 1) == 0) ? (1 << k) : -(1 << k);
242 } else {
243 return 0;
244 }
245 default:
246 // continue below to handle the general case
247 }
248 for (int accum = 1; ; k >>= 1) {
249 switch (k) {
250 case 0:
251 return accum;
252 case 1:
253 return b * accum;
254 default:
255 accum *= ((k & 1) == 0) ? 1 : b;
256 b *= b;
257 }
258 }
259 }
260
261 /**
262 * Returns the square root of {@code x}, rounded with the specified rounding mode.
263 *
264 * @throws IllegalArgumentException if {@code x < 0}
265 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code
266 * sqrt(x)} is not an integer
267 */
268 @GwtIncompatible // need BigIntegerMath to adequately test
269 @SuppressWarnings("fallthrough")
270 public static int sqrt(int x, RoundingMode mode) {
271 checkNonNegative("x", x);
272 int sqrtFloor = sqrtFloor(x);
273 switch (mode) {
274 case UNNECESSARY:
275 checkRoundingUnnecessary(sqrtFloor * sqrtFloor == x); // fall through
276 case FLOOR:
277 case DOWN:
278 return sqrtFloor;
279 case CEILING:
280 case UP:
281 return sqrtFloor + lessThanBranchFree(sqrtFloor * sqrtFloor, x);
282 case HALF_DOWN:
283 case HALF_UP:
284 case HALF_EVEN:
285 int halfSquare = sqrtFloor * sqrtFloor + sqrtFloor;
286 /*
287 * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. Since both x
288 * and halfSquare are integers, this is equivalent to testing whether or not x <=
289 * halfSquare. (We have to deal with overflow, though.)
290 *
291 * If we treat halfSquare as an unsigned int, we know that
292 * sqrtFloor^2 <= x < (sqrtFloor + 1)^2
293 * halfSquare - sqrtFloor <= x < halfSquare + sqrtFloor + 1
294 * so |x - halfSquare| <= sqrtFloor. Therefore, it's safe to treat x - halfSquare as a
295 * signed int, so lessThanBranchFree is safe for use.
296 */
297 return sqrtFloor + lessThanBranchFree(halfSquare, x);
298 default:
299 throw new AssertionError();
300 }
301 }
302
303 private static int sqrtFloor(int x) {
304 // There is no loss of precision in converting an int to a double, according to
305 // http://java.sun.com/docs/books/jls/third_edition/html/conversions.html#5.1.2
306 return (int) Math.sqrt(x);
307 }
308
309 /**
310 * Returns the result of dividing {@code p} by {@code q}, rounding using the specified {@code
311 * RoundingMode}.
312 *
313 * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a}
314 * is not an integer multiple of {@code b}
315 */
316 @SuppressWarnings("fallthrough")
317 public static int divide(int p, int q, RoundingMode mode) {
318 checkNotNull(mode);
319 if (q == 0) {
320 throw new ArithmeticException("/ by zero"); // for GWT
321 }
322 int div = p / q;
323 int rem = p - q * div; // equal to p % q
324
325 if (rem == 0) {
326 return div;
327 }
328
329 /*
330 * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to
331 * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of
332 * p / q.
333 *
334 * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise.
335 */
336 int signum = 1 | ((p ^ q) >> (Integer.SIZE - 1));
337 boolean increment;
338 switch (mode) {
339 case UNNECESSARY:
340 checkRoundingUnnecessary(rem == 0);
341 // fall through
342 case DOWN:
343 increment = false;
344 break;
345 case UP:
346 increment = true;
347 break;
348 case CEILING:
349 increment = signum > 0;
350 break;
351 case FLOOR:
352 increment = signum < 0;
353 break;
354 case HALF_EVEN:
355 case HALF_DOWN:
356 case HALF_UP:
357 int absRem = abs(rem);
358 int cmpRemToHalfDivisor = absRem - (abs(q) - absRem);
359 // subtracting two nonnegative ints can't overflow
360 // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2).
361 if (cmpRemToHalfDivisor == 0) { // exactly on the half mark
362 increment = (mode == HALF_UP || (mode == HALF_EVEN & (div & 1) != 0));
363 } else {
364 increment = cmpRemToHalfDivisor > 0; // closer to the UP value
365 }
366 break;
367 default:
368 throw new AssertionError();
369 }
370 return increment ? div + signum : div;
371 }
372
373 /**
374 * Returns {@code x mod m}, a non-negative value less than {@code m}. This differs from {@code x %
375 * m}, which might be negative.
376 *
377 * <p>For example:
378 *
379 * <pre>{@code
380 * mod(7, 4) == 3
381 * mod(-7, 4) == 1
382 * mod(-1, 4) == 3
383 * mod(-8, 4) == 0
384 * mod(8, 4) == 0
385 * }</pre>
386 *
387 * @throws ArithmeticException if {@code m <= 0}
388 * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3">
389 * Remainder Operator</a>
390 */
391 public static int mod(int x, int m) {
392 if (m <= 0) {
393 throw new ArithmeticException("Modulus " + m + " must be > 0");
394 }
395 int result = x % m;
396 return (result >= 0) ? result : result + m;
397 }
398
399 /**
400 * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if {@code a == 0 && b ==
401 * 0}.
402 *
403 * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0}
404 */
405 public static int gcd(int a, int b) {
406 /*
407 * The reason we require both arguments to be >= 0 is because otherwise, what do you return on
408 * gcd(0, Integer.MIN_VALUE)? BigInteger.gcd would return positive 2^31, but positive 2^31 isn't
409 * an int.
410 */
411 checkNonNegative("a", a);
412 checkNonNegative("b", b);
413 if (a == 0) {
414 // 0 % b == 0, so b divides a, but the converse doesn't hold.
415 // BigInteger.gcd is consistent with this decision.
416 return b;
417 } else if (b == 0) {
418 return a; // similar logic
419 }
420 /*
421 * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm. This is
422 * >40% faster than the Euclidean algorithm in benchmarks.
423 */
424 int aTwos = Integer.numberOfTrailingZeros(a);
425 a >>= aTwos; // divide out all 2s
426 int bTwos = Integer.numberOfTrailingZeros(b);
427 b >>= bTwos; // divide out all 2s
428 while (a != b) { // both a, b are odd
429 // The key to the binary GCD algorithm is as follows:
430 // Both a and b are odd. Assume a > b; then gcd(a - b, b) = gcd(a, b).
431 // But in gcd(a - b, b), a - b is even and b is odd, so we can divide out powers of two.
432
433 // We bend over backwards to avoid branching, adapting a technique from
434 // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
435
436 int delta = a - b; // can't overflow, since a and b are nonnegative
437
438 int minDeltaOrZero = delta & (delta >> (Integer.SIZE - 1));
439 // equivalent to Math.min(delta, 0)
440
441 a = delta - minDeltaOrZero - minDeltaOrZero; // sets a to Math.abs(a - b)
442 // a is now nonnegative and even
443
444 b += minDeltaOrZero; // sets b to min(old a, b)
445 a >>= Integer.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b
446 }
447 return a << min(aTwos, bTwos);
448 }
449
450 /**
451 * Returns the sum of {@code a} and {@code b}, provided it does not overflow.
452 *
453 * @throws ArithmeticException if {@code a + b} overflows in signed {@code int} arithmetic
454 */
455 public static int checkedAdd(int a, int b) {
456 long result = (long) a + b;
457 checkNoOverflow(result == (int) result, "checkedAdd", a, b);
458 return (int) result;
459 }
460
461 /**
462 * Returns the difference of {@code a} and {@code b}, provided it does not overflow.
463 *
464 * @throws ArithmeticException if {@code a - b} overflows in signed {@code int} arithmetic
465 */
466 public static int checkedSubtract(int a, int b) {
467 long result = (long) a - b;
468 checkNoOverflow(result == (int) result, "checkedSubtract", a, b);
469 return (int) result;
470 }
471
472 /**
473 * Returns the product of {@code a} and {@code b}, provided it does not overflow.
474 *
475 * @throws ArithmeticException if {@code a * b} overflows in signed {@code int} arithmetic
476 */
477 public static int checkedMultiply(int a, int b) {
478 long result = (long) a * b;
479 checkNoOverflow(result == (int) result, "checkedMultiply", a, b);
480 return (int) result;
481 }
482
483 /**
484 * Returns the {@code b} to the {@code k}th power, provided it does not overflow.
485 *
486 * <p>{@link #pow} may be faster, but does not check for overflow.
487 *
488 * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed {@code
489 * int} arithmetic
490 */
491 public static int checkedPow(int b, int k) {
492 checkNonNegative("exponent", k);
493 switch (b) {
494 case 0:
495 return (k == 0) ? 1 : 0;
496 case 1:
497 return 1;
498 case (-1):
499 return ((k & 1) == 0) ? 1 : -1;
500 case 2:
501 checkNoOverflow(k < Integer.SIZE - 1, "checkedPow", b, k);
502 return 1 << k;
503 case (-2):
504 checkNoOverflow(k < Integer.SIZE, "checkedPow", b, k);
505 return ((k & 1) == 0) ? 1 << k : -1 << k;
506 default:
507 // continue below to handle the general case
508 }
509 int accum = 1;
510 while (true) {
511 switch (k) {
512 case 0:
513 return accum;
514 case 1:
515 return checkedMultiply(accum, b);
516 default:
517 if ((k & 1) != 0) {
518 accum = checkedMultiply(accum, b);
519 }
520 k >>= 1;
521 if (k > 0) {
522 checkNoOverflow(-FLOOR_SQRT_MAX_INT <= b & b <= FLOOR_SQRT_MAX_INT, "checkedPow", b, k);
523 b *= b;
524 }
525 }
526 }
527 }
528
529 /**
530 * Returns the sum of {@code a} and {@code b} unless it would overflow or underflow in which case
531 * {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively.
532 *
533 * @since 20.0
534 */
535 @Beta
536 public static int saturatedAdd(int a, int b) {
537 return Ints.saturatedCast((long) a + b);
538 }
539
540 /**
541 * Returns the difference of {@code a} and {@code b} unless it would overflow or underflow in
542 * which case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively.
543 *
544 * @since 20.0
545 */
546 @Beta
547 public static int saturatedSubtract(int a, int b) {
548 return Ints.saturatedCast((long) a - b);
549 }
550
551 /**
552 * Returns the product of {@code a} and {@code b} unless it would overflow or underflow in which
553 * case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively.
554 *
555 * @since 20.0
556 */
557 @Beta
558 public static int saturatedMultiply(int a, int b) {
559 return Ints.saturatedCast((long) a * b);
560 }
561
562 /**
563 * Returns the {@code b} to the {@code k}th power, unless it would overflow or underflow in which
564 * case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively.
565 *
566 * @since 20.0
567 */
568 @Beta
569 public static int saturatedPow(int b, int k) {
570 checkNonNegative("exponent", k);
571 switch (b) {
572 case 0:
573 return (k == 0) ? 1 : 0;
574 case 1:
575 return 1;
576 case (-1):
577 return ((k & 1) == 0) ? 1 : -1;
578 case 2:
579 if (k >= Integer.SIZE - 1) {
580 return Integer.MAX_VALUE;
581 }
582 return 1 << k;
583 case (-2):
584 if (k >= Integer.SIZE) {
585 return Integer.MAX_VALUE + (k & 1);
586 }
587 return ((k & 1) == 0) ? 1 << k : -1 << k;
588 default:
589 // continue below to handle the general case
590 }
591 int accum = 1;
592 // if b is negative and k is odd then the limit is MIN otherwise the limit is MAX
593 int limit = Integer.MAX_VALUE + ((b >>> Integer.SIZE - 1) & (k & 1));
594 while (true) {
595 switch (k) {
596 case 0:
597 return accum;
598 case 1:
599 return saturatedMultiply(accum, b);
600 default:
601 if ((k & 1) != 0) {
602 accum = saturatedMultiply(accum, b);
603 }
604 k >>= 1;
605 if (k > 0) {
606 if (-FLOOR_SQRT_MAX_INT > b | b > FLOOR_SQRT_MAX_INT) {
607 return limit;
608 }
609 b *= b;
610 }
611 }
612 }
613 }
614
615 @VisibleForTesting static final int FLOOR_SQRT_MAX_INT = 46340;
616
617 /**
618 * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if
619 * {@code n == 0}, or {@link Integer#MAX_VALUE} if the result does not fit in a {@code int}.
620 *
621 * @throws IllegalArgumentException if {@code n < 0}
622 */
623 public static int factorial(int n) {
624 checkNonNegative("n", n);
625 return (n < factorials.length) ? factorials[n] : Integer.MAX_VALUE;
626 }
627
628 private static final int[] factorials = {
629 1,
630 1,
631 1 * 2,
632 1 * 2 * 3,
633 1 * 2 * 3 * 4,
634 1 * 2 * 3 * 4 * 5,
635 1 * 2 * 3 * 4 * 5 * 6,
636 1 * 2 * 3 * 4 * 5 * 6 * 7,
637 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8,
638 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
639 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
640 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
641 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12
642 };
643
644 /**
645 * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and
646 * {@code k}, or {@link Integer#MAX_VALUE} if the result does not fit in an {@code int}.
647 *
648 * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0} or {@code k > n}
649 */
650 public static int binomial(int n, int k) {
651 checkNonNegative("n", n);
652 checkNonNegative("k", k);
653 checkArgument(k <= n, "k (%s) > n (%s)", k, n);
654 if (k > (n >> 1)) {
655 k = n - k;
656 }
657 if (k >= biggestBinomials.length || n > biggestBinomials[k]) {
658 return Integer.MAX_VALUE;
659 }
660 switch (k) {
661 case 0:
662 return 1;
663 case 1:
664 return n;
665 default:
666 long result = 1;
667 for (int i = 0; i < k; i++) {
668 result *= n - i;
669 result /= i + 1;
670 }
671 return (int) result;
672 }
673 }
674
675 // binomial(biggestBinomials[k], k) fits in an int, but not binomial(biggestBinomials[k]+1,k).
676 @VisibleForTesting
677 static int[] biggestBinomials = {
678 Integer.MAX_VALUE,
679 Integer.MAX_VALUE,
680 65536,
681 2345,
682 477,
683 193,
684 110,
685 75,
686 58,
687 49,
688 43,
689 39,
690 37,
691 35,
692 34,
693 34,
694 33
695 };
696
697 /**
698 * Returns the arithmetic mean of {@code x} and {@code y}, rounded towards negative infinity. This
699 * method is overflow resilient.
700 *
701 * @since 14.0
702 */
703 public static int mean(int x, int y) {
704 // Efficient method for computing the arithmetic mean.
705 // The alternative (x + y) / 2 fails for large values.
706 // The alternative (x + y) >>> 1 fails for negative values.
707 return (x & y) + ((x ^ y) >> 1);
708 }
709
710 /**
711 * Returns {@code true} if {@code n} is a <a
712 * href="http://mathworld.wolfram.com/PrimeNumber.html">prime number</a>: an integer <i>greater
713 * than one</i> that cannot be factored into a product of <i>smaller</i> positive integers.
714 * Returns {@code false} if {@code n} is zero, one, or a composite number (one which <i>can</i> be
715 * factored into smaller positive integers).
716 *
717 * <p>To test larger numbers, use {@link LongMath#isPrime} or {@link BigInteger#isProbablePrime}.
718 *
719 * @throws IllegalArgumentException if {@code n} is negative
720 * @since 20.0
721 */
722 @GwtIncompatible // TODO
723 @Beta
724 public static boolean isPrime(int n) {
725 return LongMath.isPrime(n);
726 }
727
728 private IntMath() {}
729 }