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.GwtCompatible; 029import com.google.common.annotations.GwtIncompatible; 030import com.google.common.annotations.J2ktIncompatible; 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 {@link 044 * LongMath} and {@link BigIntegerMath} respectively. For other common operations on {@code int} 045 * values, see {@link com.google.common.primitives.Ints}. 046 * 047 * @author Louis Wasserman 048 * @since 11.0 049 */ 050@GwtCompatible(emulated = true) 051@ElementTypesAreNonnullByDefault 052public final class IntMath { 053 // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, || 054 055 @VisibleForTesting static final int MAX_SIGNED_POWER_OF_TWO = 1 << (Integer.SIZE - 2); 056 057 /** 058 * Returns the smallest power of two greater than or equal to {@code x}. This is equivalent to 059 * {@code checkedPow(2, log2(x, CEILING))}. 060 * 061 * @throws IllegalArgumentException if {@code x <= 0} 062 * @throws ArithmeticException of the next-higher power of two is not representable as an {@code 063 * int}, i.e. when {@code x > 2^30} 064 * @since 20.0 065 */ 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 {@code 076 * checkedPow(2, log2(x, FLOOR))}. 077 * 078 * @throws IllegalArgumentException if {@code x <= 0} 079 * @since 20.0 080 */ 081 public static int floorPowerOfTwo(int x) { 082 checkPositive("x", x); 083 return Integer.highestOneBit(x); 084 } 085 086 /** 087 * Returns {@code true} if {@code x} represents a power of two. 088 * 089 * <p>This differs from {@code Integer.bitCount(x) == 1}, because {@code 090 * Integer.bitCount(Integer.MIN_VALUE) == 1}, but {@link Integer#MIN_VALUE} is not a power of two. 091 */ 092 public static boolean isPowerOfTwo(int x) { 093 return x > 0 & (x & (x - 1)) == 0; 094 } 095 096 /** 097 * Returns 1 if {@code x < y} as unsigned integers, and 0 otherwise. Assumes that x - y fits into 098 * a signed int. The implementation is branch-free, and benchmarks suggest it is measurably (if 099 * narrowly) faster than the straightforward ternary expression. 100 */ 101 @VisibleForTesting 102 static int lessThanBranchFree(int x, int y) { 103 // The double negation is optimized away by normal Java, but is necessary for GWT 104 // to make sure bit twiddling works as expected. 105 return ~~(x - y) >>> (Integer.SIZE - 1); 106 } 107 108 /** 109 * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode. 110 * 111 * @throws IllegalArgumentException if {@code x <= 0} 112 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x} 113 * is not a power of two 114 */ 115 @SuppressWarnings("fallthrough") 116 // TODO(kevinb): remove after this warning is disabled globally 117 public static int log2(int x, RoundingMode mode) { 118 checkPositive("x", x); 119 switch (mode) { 120 case UNNECESSARY: 121 checkRoundingUnnecessary(isPowerOfTwo(x)); 122 // fall through 123 case DOWN: 124 case FLOOR: 125 return (Integer.SIZE - 1) - Integer.numberOfLeadingZeros(x); 126 127 case UP: 128 case CEILING: 129 return Integer.SIZE - Integer.numberOfLeadingZeros(x - 1); 130 131 case HALF_DOWN: 132 case HALF_UP: 133 case HALF_EVEN: 134 // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5 135 int leadingZeros = Integer.numberOfLeadingZeros(x); 136 int cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros; 137 // floor(2^(logFloor + 0.5)) 138 int logFloor = (Integer.SIZE - 1) - leadingZeros; 139 return logFloor + lessThanBranchFree(cmp, x); 140 141 default: 142 throw new AssertionError(); 143 } 144 } 145 146 /** The biggest half power of two that can fit in an unsigned int. */ 147 @VisibleForTesting static final int MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333; 148 149 /** 150 * Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode. 151 * 152 * @throws IllegalArgumentException if {@code x <= 0} 153 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x} 154 * is not a power of ten 155 */ 156 @J2ktIncompatible 157 @GwtIncompatible // need BigIntegerMath to adequately test 158 @SuppressWarnings("fallthrough") 159 public static int log10(int x, RoundingMode mode) { 160 checkPositive("x", x); 161 int logFloor = log10Floor(x); 162 int floorPow = powersOf10[logFloor]; 163 switch (mode) { 164 case UNNECESSARY: 165 checkRoundingUnnecessary(x == floorPow); 166 // fall through 167 case FLOOR: 168 case DOWN: 169 return logFloor; 170 case CEILING: 171 case UP: 172 return logFloor + lessThanBranchFree(floorPow, x); 173 case HALF_DOWN: 174 case HALF_UP: 175 case HALF_EVEN: 176 // sqrt(10) is irrational, so log10(x) - logFloor is never exactly 0.5 177 return logFloor + lessThanBranchFree(halfPowersOf10[logFloor], x); 178 default: 179 throw new AssertionError(); 180 } 181 } 182 183 private static int log10Floor(int x) { 184 /* 185 * Based on Hacker's Delight Fig. 11-5, the two-table-lookup, branch-free implementation. 186 * 187 * The key idea is that based on the number of leading zeros (equivalently, floor(log2(x))), we 188 * can narrow the possible floor(log10(x)) values to two. For example, if floor(log2(x)) is 6, 189 * then 64 <= x < 128, so floor(log10(x)) is either 1 or 2. 190 */ 191 int y = maxLog10ForLeadingZeros[Integer.numberOfLeadingZeros(x)]; 192 /* 193 * y is the higher of the two possible values of floor(log10(x)). If x < 10^y, then we want the 194 * lower of the two possible values, or y - 1, otherwise, we want y. 195 */ 196 return y - lessThanBranchFree(x, powersOf10[y]); 197 } 198 199 // maxLog10ForLeadingZeros[i] == floor(log10(2^(Long.SIZE - i))) 200 @VisibleForTesting 201 static final byte[] maxLog10ForLeadingZeros = { 202 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, 203 0 204 }; 205 206 @VisibleForTesting 207 static final int[] powersOf10 = { 208 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 209 }; 210 211 // halfPowersOf10[i] = largest int less than 10^(i + 0.5) 212 @VisibleForTesting 213 static final int[] halfPowersOf10 = { 214 3, 31, 316, 3162, 31622, 316227, 3162277, 31622776, 316227766, Integer.MAX_VALUE 215 }; 216 217 /** 218 * Returns {@code b} to the {@code k}th power. Even if the result overflows, it will be equal to 219 * {@code BigInteger.valueOf(b).pow(k).intValue()}. This implementation runs in {@code O(log k)} 220 * time. 221 * 222 * <p>Compare {@link #checkedPow}, which throws an {@link ArithmeticException} upon overflow. 223 * 224 * @throws IllegalArgumentException if {@code k < 0} 225 */ 226 @J2ktIncompatible 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 public static int saturatedAdd(int a, int b) { 536 return Ints.saturatedCast((long) a + b); 537 } 538 539 /** 540 * Returns the difference of {@code a} and {@code b} unless it would overflow or underflow in 541 * which case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively. 542 * 543 * @since 20.0 544 */ 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 public static int saturatedMultiply(int a, int b) { 556 return Ints.saturatedCast((long) a * b); 557 } 558 559 /** 560 * Returns the {@code b} to the {@code k}th power, unless it would overflow or underflow in which 561 * case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively. 562 * 563 * @since 20.0 564 */ 565 public static int saturatedPow(int b, int k) { 566 checkNonNegative("exponent", k); 567 switch (b) { 568 case 0: 569 return (k == 0) ? 1 : 0; 570 case 1: 571 return 1; 572 case (-1): 573 return ((k & 1) == 0) ? 1 : -1; 574 case 2: 575 if (k >= Integer.SIZE - 1) { 576 return Integer.MAX_VALUE; 577 } 578 return 1 << k; 579 case (-2): 580 if (k >= Integer.SIZE) { 581 return Integer.MAX_VALUE + (k & 1); 582 } 583 return ((k & 1) == 0) ? 1 << k : -1 << k; 584 default: 585 // continue below to handle the general case 586 } 587 int accum = 1; 588 // if b is negative and k is odd then the limit is MIN otherwise the limit is MAX 589 int limit = Integer.MAX_VALUE + ((b >>> Integer.SIZE - 1) & (k & 1)); 590 while (true) { 591 switch (k) { 592 case 0: 593 return accum; 594 case 1: 595 return saturatedMultiply(accum, b); 596 default: 597 if ((k & 1) != 0) { 598 accum = saturatedMultiply(accum, b); 599 } 600 k >>= 1; 601 if (k > 0) { 602 if (-FLOOR_SQRT_MAX_INT > b | b > FLOOR_SQRT_MAX_INT) { 603 return limit; 604 } 605 b *= b; 606 } 607 } 608 } 609 } 610 611 @VisibleForTesting static final int FLOOR_SQRT_MAX_INT = 46340; 612 613 /** 614 * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if 615 * {@code n == 0}, or {@link Integer#MAX_VALUE} if the result does not fit in a {@code int}. 616 * 617 * @throws IllegalArgumentException if {@code n < 0} 618 */ 619 public static int factorial(int n) { 620 checkNonNegative("n", n); 621 return (n < factorials.length) ? factorials[n] : Integer.MAX_VALUE; 622 } 623 624 private static final int[] factorials = { 625 1, 626 1, 627 1 * 2, 628 1 * 2 * 3, 629 1 * 2 * 3 * 4, 630 1 * 2 * 3 * 4 * 5, 631 1 * 2 * 3 * 4 * 5 * 6, 632 1 * 2 * 3 * 4 * 5 * 6 * 7, 633 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8, 634 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9, 635 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10, 636 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11, 637 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 638 }; 639 640 /** 641 * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and 642 * {@code k}, or {@link Integer#MAX_VALUE} if the result does not fit in an {@code int}. 643 * 644 * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0} or {@code k > n} 645 */ 646 public static int binomial(int n, int k) { 647 checkNonNegative("n", n); 648 checkNonNegative("k", k); 649 checkArgument(k <= n, "k (%s) > n (%s)", k, n); 650 if (k > (n >> 1)) { 651 k = n - k; 652 } 653 if (k >= biggestBinomials.length || n > biggestBinomials[k]) { 654 return Integer.MAX_VALUE; 655 } 656 switch (k) { 657 case 0: 658 return 1; 659 case 1: 660 return n; 661 default: 662 long result = 1; 663 for (int i = 0; i < k; i++) { 664 result *= n - i; 665 result /= i + 1; 666 } 667 return (int) result; 668 } 669 } 670 671 // binomial(biggestBinomials[k], k) fits in an int, but not binomial(biggestBinomials[k]+1,k). 672 @VisibleForTesting 673 static int[] biggestBinomials = { 674 Integer.MAX_VALUE, 675 Integer.MAX_VALUE, 676 65536, 677 2345, 678 477, 679 193, 680 110, 681 75, 682 58, 683 49, 684 43, 685 39, 686 37, 687 35, 688 34, 689 34, 690 33 691 }; 692 693 /** 694 * Returns the arithmetic mean of {@code x} and {@code y}, rounded towards negative infinity. This 695 * method is overflow resilient. 696 * 697 * @since 14.0 698 */ 699 public static int mean(int x, int y) { 700 // Efficient method for computing the arithmetic mean. 701 // The alternative (x + y) / 2 fails for large values. 702 // The alternative (x + y) >>> 1 fails for negative values. 703 return (x & y) + ((x ^ y) >> 1); 704 } 705 706 /** 707 * Returns {@code true} if {@code n} is a <a 708 * href="http://mathworld.wolfram.com/PrimeNumber.html">prime number</a>: an integer <i>greater 709 * than one</i> that cannot be factored into a product of <i>smaller</i> positive integers. 710 * Returns {@code false} if {@code n} is zero, one, or a composite number (one which <i>can</i> be 711 * factored into smaller positive integers). 712 * 713 * <p>To test larger numbers, use {@link LongMath#isPrime} or {@link BigInteger#isProbablePrime}. 714 * 715 * @throws IllegalArgumentException if {@code n} is negative 716 * @since 20.0 717 */ 718 @J2ktIncompatible 719 @GwtIncompatible // TODO 720 public static boolean isPrime(int n) { 721 return LongMath.isPrime(n); 722 } 723 724 private IntMath() {} 725}