View Javadoc
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
44   * {@link LongMath} and {@link BigIntegerMath} respectively. For other common operations on
45   * {@code int} values, see {@link com.google.common.primitives.Ints}.
46   *
47   * @author Louis Wasserman
48   * @since 11.0
49   */
50  @GwtCompatible(emulated = true)
51  public final class IntMath {
52    // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
53  
54    @VisibleForTesting static final int MAX_SIGNED_POWER_OF_TWO = 1 << (Integer.SIZE - 2);
55  
56    /**
57     * Returns the smallest power of two greater than or equal to {@code x}.  This is equivalent to
58     * {@code checkedPow(2, log2(x, CEILING))}.
59     *
60     * @throws IllegalArgumentException if {@code x <= 0}
61     * @throws ArithmeticException of the next-higher power of two is not representable as an
62     *         {@code int}, i.e. when {@code x > 2^30}
63     * @since 20.0
64     */
65    @Beta
66    public static int ceilingPowerOfTwo(int x) {
67      checkPositive("x", x);
68      if (x > MAX_SIGNED_POWER_OF_TWO) {
69        throw new ArithmeticException("ceilingPowerOfTwo(" + x + ") not representable as an int");
70      }
71      return 1 << -Integer.numberOfLeadingZeros(x - 1);
72    }
73  
74    /**
75     * Returns the largest power of two less than or equal to {@code x}.  This is equivalent to
76     * {@code checkedPow(2, log2(x, FLOOR))}.
77     *
78     * @throws IllegalArgumentException if {@code x <= 0}
79     * @since 20.0
80     */
81    @Beta
82    public static int floorPowerOfTwo(int x) {
83      checkPositive("x", x);
84      return Integer.highestOneBit(x);
85    }
86  
87    /**
88     * Returns {@code true} if {@code x} represents a power of two.
89     *
90     * <p>This differs from {@code Integer.bitCount(x) == 1}, because
91     * {@code Integer.bitCount(Integer.MIN_VALUE) == 1}, but {@link Integer#MIN_VALUE} is not a power
92     * 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
266    *     {@code 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
311    * {@code 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
375    * {@code x % m}, which might be negative.
376    *
377    * <p>For example:<pre> {@code
378    *
379    * mod(7, 4) == 3
380    * mod(-7, 4) == 1
381    * mod(-1, 4) == 3
382    * mod(-8, 4) == 0
383    * mod(8, 4) == 0}</pre>
384    *
385    * @throws ArithmeticException if {@code m <= 0}
386    * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3">
387    *     Remainder Operator</a>
388    */
389   public static int mod(int x, int m) {
390     if (m <= 0) {
391       throw new ArithmeticException("Modulus " + m + " must be > 0");
392     }
393     int result = x % m;
394     return (result >= 0) ? result : result + m;
395   }
396 
397   /**
398    * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if
399    * {@code a == 0 && b == 0}.
400    *
401    * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0}
402    */
403   public static int gcd(int a, int b) {
404     /*
405      * The reason we require both arguments to be >= 0 is because otherwise, what do you return on
406      * gcd(0, Integer.MIN_VALUE)? BigInteger.gcd would return positive 2^31, but positive 2^31 isn't
407      * an int.
408      */
409     checkNonNegative("a", a);
410     checkNonNegative("b", b);
411     if (a == 0) {
412       // 0 % b == 0, so b divides a, but the converse doesn't hold.
413       // BigInteger.gcd is consistent with this decision.
414       return b;
415     } else if (b == 0) {
416       return a; // similar logic
417     }
418     /*
419      * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm. This is
420      * >40% faster than the Euclidean algorithm in benchmarks.
421      */
422     int aTwos = Integer.numberOfTrailingZeros(a);
423     a >>= aTwos; // divide out all 2s
424     int bTwos = Integer.numberOfTrailingZeros(b);
425     b >>= bTwos; // divide out all 2s
426     while (a != b) { // both a, b are odd
427       // The key to the binary GCD algorithm is as follows:
428       // Both a and b are odd. Assume a > b; then gcd(a - b, b) = gcd(a, b).
429       // But in gcd(a - b, b), a - b is even and b is odd, so we can divide out powers of two.
430 
431       // We bend over backwards to avoid branching, adapting a technique from
432       // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
433 
434       int delta = a - b; // can't overflow, since a and b are nonnegative
435 
436       int minDeltaOrZero = delta & (delta >> (Integer.SIZE - 1));
437       // equivalent to Math.min(delta, 0)
438 
439       a = delta - minDeltaOrZero - minDeltaOrZero; // sets a to Math.abs(a - b)
440       // a is now nonnegative and even
441 
442       b += minDeltaOrZero; // sets b to min(old a, b)
443       a >>= Integer.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b
444     }
445     return a << min(aTwos, bTwos);
446   }
447 
448   /**
449    * Returns the sum of {@code a} and {@code b}, provided it does not overflow.
450    *
451    * @throws ArithmeticException if {@code a + b} overflows in signed {@code int} arithmetic
452    */
453   public static int checkedAdd(int a, int b) {
454     long result = (long) a + b;
455     checkNoOverflow(result == (int) result);
456     return (int) result;
457   }
458 
459   /**
460    * Returns the difference of {@code a} and {@code b}, provided it does not overflow.
461    *
462    * @throws ArithmeticException if {@code a - b} overflows in signed {@code int} arithmetic
463    */
464   public static int checkedSubtract(int a, int b) {
465     long result = (long) a - b;
466     checkNoOverflow(result == (int) result);
467     return (int) result;
468   }
469 
470   /**
471    * Returns the product of {@code a} and {@code b}, provided it does not overflow.
472    *
473    * @throws ArithmeticException if {@code a * b} overflows in signed {@code int} arithmetic
474    */
475   public static int checkedMultiply(int a, int b) {
476     long result = (long) a * b;
477     checkNoOverflow(result == (int) result);
478     return (int) result;
479   }
480 
481   /**
482    * Returns the {@code b} to the {@code k}th power, provided it does not overflow.
483    *
484    * <p>{@link #pow} may be faster, but does not check for overflow.
485    *
486    * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed
487    *     {@code int} arithmetic
488    */
489   public static int checkedPow(int b, int k) {
490     checkNonNegative("exponent", k);
491     switch (b) {
492       case 0:
493         return (k == 0) ? 1 : 0;
494       case 1:
495         return 1;
496       case (-1):
497         return ((k & 1) == 0) ? 1 : -1;
498       case 2:
499         checkNoOverflow(k < Integer.SIZE - 1);
500         return 1 << k;
501       case (-2):
502         checkNoOverflow(k < Integer.SIZE);
503         return ((k & 1) == 0) ? 1 << k : -1 << k;
504       default:
505         // continue below to handle the general case
506     }
507     int accum = 1;
508     while (true) {
509       switch (k) {
510         case 0:
511           return accum;
512         case 1:
513           return checkedMultiply(accum, b);
514         default:
515           if ((k & 1) != 0) {
516             accum = checkedMultiply(accum, b);
517           }
518           k >>= 1;
519           if (k > 0) {
520             checkNoOverflow(-FLOOR_SQRT_MAX_INT <= b & b <= FLOOR_SQRT_MAX_INT);
521             b *= b;
522           }
523       }
524     }
525   }
526 
527   /**
528    * Returns the sum of {@code a} and {@code b} unless it would overflow or underflow in which case
529    * {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively.
530    *
531    * @since 20.0
532    */
533   @Beta
534   public static int saturatedAdd(int a, int b) {
535     return Ints.saturatedCast((long) a + b);
536   }
537 
538   /**
539    * Returns the difference of {@code a} and {@code b} unless it would overflow or underflow in
540    * which case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively.
541    *
542    * @since 20.0
543    */
544   @Beta
545   public static int saturatedSubtract(int a, int b) {
546     return Ints.saturatedCast((long) a - b);
547   }
548 
549   /**
550    * Returns the product of {@code a} and {@code b} unless it would overflow or underflow in which
551    * case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively.
552    *
553    * @since 20.0
554    */
555   @Beta
556   public static int saturatedMultiply(int a, int b) {
557     return Ints.saturatedCast((long) a * b);
558   }
559 
560   /**
561    * Returns the {@code b} to the {@code k}th power, unless it would overflow or underflow in which
562    * case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively.
563    *
564    * @since 20.0
565    */
566   @Beta
567   public static int saturatedPow(int b, int k) {
568     checkNonNegative("exponent", k);
569     switch (b) {
570       case 0:
571         return (k == 0) ? 1 : 0;
572       case 1:
573         return 1;
574       case (-1):
575         return ((k & 1) == 0) ? 1 : -1;
576       case 2:
577         if (k >= Integer.SIZE - 1) {
578           return Integer.MAX_VALUE;
579         }
580         return 1 << k;
581       case (-2):
582         if (k >= Integer.SIZE) {
583           return Integer.MAX_VALUE + (k & 1);
584         }
585         return ((k & 1) == 0) ? 1 << k : -1 << k;
586       default:
587         // continue below to handle the general case
588     }
589     int accum = 1;
590     // if b is negative and k is odd then the limit is MIN otherwise the limit is MAX
591     int limit = Integer.MAX_VALUE + ((b >>> Integer.SIZE - 1) & (k & 1));
592     while (true) {
593       switch (k) {
594         case 0:
595           return accum;
596         case 1:
597           return saturatedMultiply(accum, b);
598         default:
599           if ((k & 1) != 0) {
600             accum = saturatedMultiply(accum, b);
601           }
602           k >>= 1;
603           if (k > 0) {
604             if (-FLOOR_SQRT_MAX_INT > b | b > FLOOR_SQRT_MAX_INT) {
605               return limit;
606             }
607             b *= b;
608           }
609       }
610     }
611   }
612 
613   @VisibleForTesting static final int FLOOR_SQRT_MAX_INT = 46340;
614 
615   /**
616    * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if
617    * {@code n == 0}, or {@link Integer#MAX_VALUE} if the result does not fit in a {@code int}.
618    *
619    * @throws IllegalArgumentException if {@code n < 0}
620    */
621   public static int factorial(int n) {
622     checkNonNegative("n", n);
623     return (n < factorials.length) ? factorials[n] : Integer.MAX_VALUE;
624   }
625 
626   private static final int[] factorials = {
627     1,
628     1,
629     1 * 2,
630     1 * 2 * 3,
631     1 * 2 * 3 * 4,
632     1 * 2 * 3 * 4 * 5,
633     1 * 2 * 3 * 4 * 5 * 6,
634     1 * 2 * 3 * 4 * 5 * 6 * 7,
635     1 * 2 * 3 * 4 * 5 * 6 * 7 * 8,
636     1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
637     1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
638     1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
639     1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12
640   };
641 
642   /**
643    * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and
644    * {@code k}, or {@link Integer#MAX_VALUE} if the result does not fit in an {@code int}.
645    *
646    * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0} or {@code k > n}
647    */
648   public static int binomial(int n, int k) {
649     checkNonNegative("n", n);
650     checkNonNegative("k", k);
651     checkArgument(k <= n, "k (%s) > n (%s)", k, n);
652     if (k > (n >> 1)) {
653       k = n - k;
654     }
655     if (k >= biggestBinomials.length || n > biggestBinomials[k]) {
656       return Integer.MAX_VALUE;
657     }
658     switch (k) {
659       case 0:
660         return 1;
661       case 1:
662         return n;
663       default:
664         long result = 1;
665         for (int i = 0; i < k; i++) {
666           result *= n - i;
667           result /= i + 1;
668         }
669         return (int) result;
670     }
671   }
672 
673   // binomial(biggestBinomials[k], k) fits in an int, but not binomial(biggestBinomials[k]+1,k).
674   @VisibleForTesting
675   static int[] biggestBinomials = {
676     Integer.MAX_VALUE,
677     Integer.MAX_VALUE,
678     65536,
679     2345,
680     477,
681     193,
682     110,
683     75,
684     58,
685     49,
686     43,
687     39,
688     37,
689     35,
690     34,
691     34,
692     33
693   };
694 
695   /**
696    * Returns the arithmetic mean of {@code x} and {@code y}, rounded towards negative infinity. This
697    * method is overflow resilient.
698    *
699    * @since 14.0
700    */
701   public static int mean(int x, int y) {
702     // Efficient method for computing the arithmetic mean.
703     // The alternative (x + y) / 2 fails for large values.
704     // The alternative (x + y) >>> 1 fails for negative values.
705     return (x & y) + ((x ^ y) >> 1);
706   }
707 
708   /**
709    * Returns {@code true} if {@code n} is a
710    * <a href="http://mathworld.wolfram.com/PrimeNumber.html">prime number</a>: an integer <i>greater
711    * than one</i> that cannot be factored into a product of <i>smaller</i> positive integers.
712    * Returns {@code false} if {@code n} is zero, one, or a composite number (one which <i>can</i>
713    * be factored into smaller positive integers).
714    *
715    * <p>To test larger numbers, use {@link LongMath#isPrime} or {@link BigInteger#isProbablePrime}.
716    *
717    * @throws IllegalArgumentException if {@code n} is negative
718    * @since 20.0
719    */
720   @GwtIncompatible // TODO
721   @Beta
722   public static boolean isPrime(int n) {
723     return LongMath.isPrime(n);
724   }
725 
726   private IntMath() {}
727 }