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 {@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) 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 {@code 062 * 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 {@code 076 * 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 {@code 091 * Integer.bitCount(Integer.MIN_VALUE) == 1}, but {@link Integer#MIN_VALUE} is not a power of two. 092 */ 093 public static boolean isPowerOfTwo(int x) { 094 return x > 0 & (x & (x - 1)) == 0; 095 } 096 097 /** 098 * Returns 1 if {@code x < y} as unsigned integers, and 0 otherwise. Assumes that x - y fits into 099 * a signed int. The implementation is branch-free, and benchmarks suggest it is measurably (if 100 * narrowly) faster than the straightforward ternary expression. 101 */ 102 @VisibleForTesting 103 static int lessThanBranchFree(int x, int y) { 104 // The double negation is optimized away by normal Java, but is necessary for GWT 105 // to make sure bit twiddling works as expected. 106 return ~~(x - y) >>> (Integer.SIZE - 1); 107 } 108 109 /** 110 * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode. 111 * 112 * @throws IllegalArgumentException if {@code x <= 0} 113 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x} 114 * is not a power of two 115 */ 116 @SuppressWarnings("fallthrough") 117 // TODO(kevinb): remove after this warning is disabled globally 118 public static int log2(int x, RoundingMode mode) { 119 checkPositive("x", x); 120 switch (mode) { 121 case UNNECESSARY: 122 checkRoundingUnnecessary(isPowerOfTwo(x)); 123 // fall through 124 case DOWN: 125 case FLOOR: 126 return (Integer.SIZE - 1) - Integer.numberOfLeadingZeros(x); 127 128 case UP: 129 case CEILING: 130 return Integer.SIZE - Integer.numberOfLeadingZeros(x - 1); 131 132 case HALF_DOWN: 133 case HALF_UP: 134 case HALF_EVEN: 135 // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5 136 int leadingZeros = Integer.numberOfLeadingZeros(x); 137 int cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros; 138 // floor(2^(logFloor + 0.5)) 139 int logFloor = (Integer.SIZE - 1) - leadingZeros; 140 return logFloor + lessThanBranchFree(cmp, x); 141 142 default: 143 throw new AssertionError(); 144 } 145 } 146 147 /** The biggest half power of two that can fit in an unsigned int. */ 148 @VisibleForTesting static final int MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333; 149 150 /** 151 * Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode. 152 * 153 * @throws IllegalArgumentException if {@code x <= 0} 154 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x} 155 * is not a power of ten 156 */ 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 @GwtIncompatible // failing tests 227 public static int pow(int b, int k) { 228 checkNonNegative("exponent", k); 229 switch (b) { 230 case 0: 231 return (k == 0) ? 1 : 0; 232 case 1: 233 return 1; 234 case (-1): 235 return ((k & 1) == 0) ? 1 : -1; 236 case 2: 237 return (k < Integer.SIZE) ? (1 << k) : 0; 238 case (-2): 239 if (k < Integer.SIZE) { 240 return ((k & 1) == 0) ? (1 << k) : -(1 << k); 241 } else { 242 return 0; 243 } 244 default: 245 // continue below to handle the general case 246 } 247 for (int accum = 1; ; k >>= 1) { 248 switch (k) { 249 case 0: 250 return accum; 251 case 1: 252 return b * accum; 253 default: 254 accum *= ((k & 1) == 0) ? 1 : b; 255 b *= b; 256 } 257 } 258 } 259 260 /** 261 * Returns the square root of {@code x}, rounded with the specified rounding mode. 262 * 263 * @throws IllegalArgumentException if {@code x < 0} 264 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code 265 * sqrt(x)} is not an integer 266 */ 267 @GwtIncompatible // need BigIntegerMath to adequately test 268 @SuppressWarnings("fallthrough") 269 public static int sqrt(int x, RoundingMode mode) { 270 checkNonNegative("x", x); 271 int sqrtFloor = sqrtFloor(x); 272 switch (mode) { 273 case UNNECESSARY: 274 checkRoundingUnnecessary(sqrtFloor * sqrtFloor == x); // fall through 275 case FLOOR: 276 case DOWN: 277 return sqrtFloor; 278 case CEILING: 279 case UP: 280 return sqrtFloor + lessThanBranchFree(sqrtFloor * sqrtFloor, x); 281 case HALF_DOWN: 282 case HALF_UP: 283 case HALF_EVEN: 284 int halfSquare = sqrtFloor * sqrtFloor + sqrtFloor; 285 /* 286 * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. Since both x 287 * and halfSquare are integers, this is equivalent to testing whether or not x <= 288 * halfSquare. (We have to deal with overflow, though.) 289 * 290 * If we treat halfSquare as an unsigned int, we know that 291 * sqrtFloor^2 <= x < (sqrtFloor + 1)^2 292 * halfSquare - sqrtFloor <= x < halfSquare + sqrtFloor + 1 293 * so |x - halfSquare| <= sqrtFloor. Therefore, it's safe to treat x - halfSquare as a 294 * signed int, so lessThanBranchFree is safe for use. 295 */ 296 return sqrtFloor + lessThanBranchFree(halfSquare, x); 297 default: 298 throw new AssertionError(); 299 } 300 } 301 302 private static int sqrtFloor(int x) { 303 // There is no loss of precision in converting an int to a double, according to 304 // http://java.sun.com/docs/books/jls/third_edition/html/conversions.html#5.1.2 305 return (int) Math.sqrt(x); 306 } 307 308 /** 309 * Returns the result of dividing {@code p} by {@code q}, rounding using the specified {@code 310 * RoundingMode}. 311 * 312 * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a} 313 * is not an integer multiple of {@code b} 314 */ 315 @SuppressWarnings("fallthrough") 316 public static int divide(int p, int q, RoundingMode mode) { 317 checkNotNull(mode); 318 if (q == 0) { 319 throw new ArithmeticException("/ by zero"); // for GWT 320 } 321 int div = p / q; 322 int rem = p - q * div; // equal to p % q 323 324 if (rem == 0) { 325 return div; 326 } 327 328 /* 329 * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to 330 * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of 331 * p / q. 332 * 333 * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise. 334 */ 335 int signum = 1 | ((p ^ q) >> (Integer.SIZE - 1)); 336 boolean increment; 337 switch (mode) { 338 case UNNECESSARY: 339 checkRoundingUnnecessary(rem == 0); 340 // fall through 341 case DOWN: 342 increment = false; 343 break; 344 case UP: 345 increment = true; 346 break; 347 case CEILING: 348 increment = signum > 0; 349 break; 350 case FLOOR: 351 increment = signum < 0; 352 break; 353 case HALF_EVEN: 354 case HALF_DOWN: 355 case HALF_UP: 356 int absRem = abs(rem); 357 int cmpRemToHalfDivisor = absRem - (abs(q) - absRem); 358 // subtracting two nonnegative ints can't overflow 359 // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2). 360 if (cmpRemToHalfDivisor == 0) { // exactly on the half mark 361 increment = (mode == HALF_UP || (mode == HALF_EVEN & (div & 1) != 0)); 362 } else { 363 increment = cmpRemToHalfDivisor > 0; // closer to the UP value 364 } 365 break; 366 default: 367 throw new AssertionError(); 368 } 369 return increment ? div + signum : div; 370 } 371 372 /** 373 * Returns {@code x mod m}, a non-negative value less than {@code m}. This differs from {@code x % 374 * m}, which might be negative. 375 * 376 * <p>For example: 377 * 378 * <pre>{@code 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 384 * }</pre> 385 * 386 * @throws ArithmeticException if {@code m <= 0} 387 * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3"> 388 * Remainder Operator</a> 389 */ 390 public static int mod(int x, int m) { 391 if (m <= 0) { 392 throw new ArithmeticException("Modulus " + m + " must be > 0"); 393 } 394 int result = x % m; 395 return (result >= 0) ? result : result + m; 396 } 397 398 /** 399 * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if {@code a == 0 && b == 400 * 0}. 401 * 402 * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0} 403 */ 404 public static int gcd(int a, int b) { 405 /* 406 * The reason we require both arguments to be >= 0 is because otherwise, what do you return on 407 * gcd(0, Integer.MIN_VALUE)? BigInteger.gcd would return positive 2^31, but positive 2^31 isn't 408 * an int. 409 */ 410 checkNonNegative("a", a); 411 checkNonNegative("b", b); 412 if (a == 0) { 413 // 0 % b == 0, so b divides a, but the converse doesn't hold. 414 // BigInteger.gcd is consistent with this decision. 415 return b; 416 } else if (b == 0) { 417 return a; // similar logic 418 } 419 /* 420 * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm. This is 421 * >40% faster than the Euclidean algorithm in benchmarks. 422 */ 423 int aTwos = Integer.numberOfTrailingZeros(a); 424 a >>= aTwos; // divide out all 2s 425 int bTwos = Integer.numberOfTrailingZeros(b); 426 b >>= bTwos; // divide out all 2s 427 while (a != b) { // both a, b are odd 428 // The key to the binary GCD algorithm is as follows: 429 // Both a and b are odd. Assume a > b; then gcd(a - b, b) = gcd(a, b). 430 // But in gcd(a - b, b), a - b is even and b is odd, so we can divide out powers of two. 431 432 // We bend over backwards to avoid branching, adapting a technique from 433 // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax 434 435 int delta = a - b; // can't overflow, since a and b are nonnegative 436 437 int minDeltaOrZero = delta & (delta >> (Integer.SIZE - 1)); 438 // equivalent to Math.min(delta, 0) 439 440 a = delta - minDeltaOrZero - minDeltaOrZero; // sets a to Math.abs(a - b) 441 // a is now nonnegative and even 442 443 b += minDeltaOrZero; // sets b to min(old a, b) 444 a >>= Integer.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b 445 } 446 return a << min(aTwos, bTwos); 447 } 448 449 /** 450 * Returns the sum of {@code a} and {@code b}, provided it does not overflow. 451 * 452 * @throws ArithmeticException if {@code a + b} overflows in signed {@code int} arithmetic 453 */ 454 public static int checkedAdd(int a, int b) { 455 long result = (long) a + b; 456 checkNoOverflow(result == (int) result, "checkedAdd", a, b); 457 return (int) result; 458 } 459 460 /** 461 * Returns the difference of {@code a} and {@code b}, provided it does not overflow. 462 * 463 * @throws ArithmeticException if {@code a - b} overflows in signed {@code int} arithmetic 464 */ 465 public static int checkedSubtract(int a, int b) { 466 long result = (long) a - b; 467 checkNoOverflow(result == (int) result, "checkedSubtract", a, b); 468 return (int) result; 469 } 470 471 /** 472 * Returns the product of {@code a} and {@code b}, provided it does not overflow. 473 * 474 * @throws ArithmeticException if {@code a * b} overflows in signed {@code int} arithmetic 475 */ 476 public static int checkedMultiply(int a, int b) { 477 long result = (long) a * b; 478 checkNoOverflow(result == (int) result, "checkedMultiply", a, b); 479 return (int) result; 480 } 481 482 /** 483 * Returns the {@code b} to the {@code k}th power, provided it does not overflow. 484 * 485 * <p>{@link #pow} may be faster, but does not check for overflow. 486 * 487 * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed {@code 488 * int} arithmetic 489 */ 490 public static int checkedPow(int b, int k) { 491 checkNonNegative("exponent", k); 492 switch (b) { 493 case 0: 494 return (k == 0) ? 1 : 0; 495 case 1: 496 return 1; 497 case (-1): 498 return ((k & 1) == 0) ? 1 : -1; 499 case 2: 500 checkNoOverflow(k < Integer.SIZE - 1, "checkedPow", b, k); 501 return 1 << k; 502 case (-2): 503 checkNoOverflow(k < Integer.SIZE, "checkedPow", b, k); 504 return ((k & 1) == 0) ? 1 << k : -1 << k; 505 default: 506 // continue below to handle the general case 507 } 508 int accum = 1; 509 while (true) { 510 switch (k) { 511 case 0: 512 return accum; 513 case 1: 514 return checkedMultiply(accum, b); 515 default: 516 if ((k & 1) != 0) { 517 accum = checkedMultiply(accum, b); 518 } 519 k >>= 1; 520 if (k > 0) { 521 checkNoOverflow(-FLOOR_SQRT_MAX_INT <= b & b <= FLOOR_SQRT_MAX_INT, "checkedPow", b, k); 522 b *= b; 523 } 524 } 525 } 526 } 527 528 /** 529 * Returns the sum of {@code a} and {@code b} unless it would overflow or underflow in which case 530 * {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively. 531 * 532 * @since 20.0 533 */ 534 @Beta 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 @Beta 546 public static int saturatedSubtract(int a, int b) { 547 return Ints.saturatedCast((long) a - b); 548 } 549 550 /** 551 * Returns the product of {@code a} and {@code b} unless it would overflow or underflow in which 552 * case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively. 553 * 554 * @since 20.0 555 */ 556 @Beta 557 public static int saturatedMultiply(int a, int b) { 558 return Ints.saturatedCast((long) a * b); 559 } 560 561 /** 562 * Returns the {@code b} to the {@code k}th power, unless it would overflow or underflow in which 563 * case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively. 564 * 565 * @since 20.0 566 */ 567 @Beta 568 public static int saturatedPow(int b, int k) { 569 checkNonNegative("exponent", k); 570 switch (b) { 571 case 0: 572 return (k == 0) ? 1 : 0; 573 case 1: 574 return 1; 575 case (-1): 576 return ((k & 1) == 0) ? 1 : -1; 577 case 2: 578 if (k >= Integer.SIZE - 1) { 579 return Integer.MAX_VALUE; 580 } 581 return 1 << k; 582 case (-2): 583 if (k >= Integer.SIZE) { 584 return Integer.MAX_VALUE + (k & 1); 585 } 586 return ((k & 1) == 0) ? 1 << k : -1 << k; 587 default: 588 // continue below to handle the general case 589 } 590 int accum = 1; 591 // if b is negative and k is odd then the limit is MIN otherwise the limit is MAX 592 int limit = Integer.MAX_VALUE + ((b >>> Integer.SIZE - 1) & (k & 1)); 593 while (true) { 594 switch (k) { 595 case 0: 596 return accum; 597 case 1: 598 return saturatedMultiply(accum, b); 599 default: 600 if ((k & 1) != 0) { 601 accum = saturatedMultiply(accum, b); 602 } 603 k >>= 1; 604 if (k > 0) { 605 if (-FLOOR_SQRT_MAX_INT > b | b > FLOOR_SQRT_MAX_INT) { 606 return limit; 607 } 608 b *= b; 609 } 610 } 611 } 612 } 613 614 @VisibleForTesting static final int FLOOR_SQRT_MAX_INT = 46340; 615 616 /** 617 * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if 618 * {@code n == 0}, or {@link Integer#MAX_VALUE} if the result does not fit in a {@code int}. 619 * 620 * @throws IllegalArgumentException if {@code n < 0} 621 */ 622 public static int factorial(int n) { 623 checkNonNegative("n", n); 624 return (n < factorials.length) ? factorials[n] : Integer.MAX_VALUE; 625 } 626 627 private static final int[] factorials = { 628 1, 629 1, 630 1 * 2, 631 1 * 2 * 3, 632 1 * 2 * 3 * 4, 633 1 * 2 * 3 * 4 * 5, 634 1 * 2 * 3 * 4 * 5 * 6, 635 1 * 2 * 3 * 4 * 5 * 6 * 7, 636 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8, 637 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9, 638 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10, 639 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11, 640 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 641 }; 642 643 /** 644 * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and 645 * {@code k}, or {@link Integer#MAX_VALUE} if the result does not fit in an {@code int}. 646 * 647 * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0} or {@code k > n} 648 */ 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 <a 711 * 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> be 714 * 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}