001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.math;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019import static com.google.common.math.MathPreconditions.checkNoOverflow;
020import static com.google.common.math.MathPreconditions.checkNonNegative;
021import static com.google.common.math.MathPreconditions.checkPositive;
022import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
023import static java.lang.Math.abs;
024import static java.lang.Math.min;
025import static java.math.RoundingMode.HALF_EVEN;
026import static java.math.RoundingMode.HALF_UP;
027
028import com.google.common.annotations.Beta;
029import com.google.common.annotations.GwtCompatible;
030import com.google.common.annotations.GwtIncompatible;
031import com.google.common.annotations.VisibleForTesting;
032import com.google.common.primitives.Ints;
033import java.math.BigInteger;
034import java.math.RoundingMode;
035
036/**
037 * A class for arithmetic on values of type {@code int}. Where possible, methods are defined and
038 * named analogously to their {@code BigInteger} counterparts.
039 *
040 * <p>The implementations of many methods in this class are based on material from Henry S. Warren,
041 * Jr.'s <i>Hacker's Delight</i>, (Addison Wesley, 2002).
042 *
043 * <p>Similar functionality for {@code long} and for {@link BigInteger} can be found in
044 * {@link LongMath} and {@link BigIntegerMath} respectively. For other common operations on
045 * {@code int} values, see {@link com.google.common.primitives.Ints}.
046 *
047 * @author Louis Wasserman
048 * @since 11.0
049 */
050@GwtCompatible(emulated = true)
051public final class IntMath {
052  // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
053
054  @VisibleForTesting static final int MAX_SIGNED_POWER_OF_TWO = 1 << (Integer.SIZE - 2);
055
056  /**
057   * Returns the smallest power of two greater than or equal to {@code x}.  This is equivalent to
058   * {@code checkedPow(2, log2(x, CEILING))}.
059   *
060   * @throws IllegalArgumentException if {@code x <= 0}
061   * @throws ArithmeticException of the next-higher power of two is not representable as an
062   *         {@code int}, i.e. when {@code x > 2^30}
063   * @since 20.0
064   */
065  @Beta
066  public static int ceilingPowerOfTwo(int x) {
067    checkPositive("x", x);
068    if (x > MAX_SIGNED_POWER_OF_TWO) {
069      throw new ArithmeticException("ceilingPowerOfTwo(" + x + ") not representable as an int");
070    }
071    return 1 << -Integer.numberOfLeadingZeros(x - 1);
072  }
073
074  /**
075   * Returns the largest power of two less than or equal to {@code x}.  This is equivalent to
076   * {@code checkedPow(2, log2(x, FLOOR))}.
077   *
078   * @throws IllegalArgumentException if {@code x <= 0}
079   * @since 20.0
080   */
081  @Beta
082  public static int floorPowerOfTwo(int x) {
083    checkPositive("x", x);
084    return Integer.highestOneBit(x);
085  }
086
087  /**
088   * Returns {@code true} if {@code x} represents a power of two.
089   *
090   * <p>This differs from {@code Integer.bitCount(x) == 1}, because
091   * {@code Integer.bitCount(Integer.MIN_VALUE) == 1}, but {@link Integer#MIN_VALUE} is not a power
092   * of two.
093   */
094  public static boolean isPowerOfTwo(int x) {
095    return x > 0 & (x & (x - 1)) == 0;
096  }
097
098  /**
099   * 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  @GwtIncompatible // need BigIntegerMath to adequately test
649  public static int binomial(int n, int k) {
650    checkNonNegative("n", n);
651    checkNonNegative("k", k);
652    checkArgument(k <= n, "k (%s) > n (%s)", k, n);
653    if (k > (n >> 1)) {
654      k = n - k;
655    }
656    if (k >= biggestBinomials.length || n > biggestBinomials[k]) {
657      return Integer.MAX_VALUE;
658    }
659    switch (k) {
660      case 0:
661        return 1;
662      case 1:
663        return n;
664      default:
665        long result = 1;
666        for (int i = 0; i < k; i++) {
667          result *= n - i;
668          result /= i + 1;
669        }
670        return (int) result;
671    }
672  }
673
674  // binomial(biggestBinomials[k], k) fits in an int, but not binomial(biggestBinomials[k]+1,k).
675  @VisibleForTesting
676  static int[] biggestBinomials = {
677    Integer.MAX_VALUE,
678    Integer.MAX_VALUE,
679    65536,
680    2345,
681    477,
682    193,
683    110,
684    75,
685    58,
686    49,
687    43,
688    39,
689    37,
690    35,
691    34,
692    34,
693    33
694  };
695
696  /**
697   * Returns the arithmetic mean of {@code x} and {@code y}, rounded towards negative infinity. This
698   * method is overflow resilient.
699   *
700   * @since 14.0
701   */
702  public static int mean(int x, int y) {
703    // Efficient method for computing the arithmetic mean.
704    // The alternative (x + y) / 2 fails for large values.
705    // The alternative (x + y) >>> 1 fails for negative values.
706    return (x & y) + ((x ^ y) >> 1);
707  }
708
709  /**
710   * Returns {@code true} if {@code n} is a
711   * <a href="http://mathworld.wolfram.com/PrimeNumber.html">prime number</a>: an integer <i>greater
712   * than one</i> that cannot be factored into a product of <i>smaller</i> positive integers.
713   * Returns {@code false} if {@code n} is zero, one, or a composite number (one which <i>can</i>
714   * be factored into smaller positive integers).
715   *
716   * <p>To test larger numbers, use {@link LongMath#isPrime} or {@link BigInteger#isProbablePrime}.
717   *
718   * @throws IllegalArgumentException if {@code n} is negative
719   * @since 20.0
720   */
721  @GwtIncompatible // TODO
722  @Beta
723  public static boolean isPrime(int n) {
724    return LongMath.isPrime(n);
725  }
726
727  private IntMath() {}
728}