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) 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 @Beta 067 public static int ceilingPowerOfTwo(int x) { 068 checkPositive("x", x); 069 if (x > MAX_SIGNED_POWER_OF_TWO) { 070 throw new ArithmeticException("ceilingPowerOfTwo(" + x + ") not representable as an int"); 071 } 072 return 1 << -Integer.numberOfLeadingZeros(x - 1); 073 } 074 075 /** 076 * Returns the largest power of two less than or equal to {@code x}. This is equivalent to {@code 077 * checkedPow(2, log2(x, FLOOR))}. 078 * 079 * @throws IllegalArgumentException if {@code x <= 0} 080 * @since 20.0 081 */ 082 @Beta 083 public static int floorPowerOfTwo(int x) { 084 checkPositive("x", x); 085 return Integer.highestOneBit(x); 086 } 087 088 /** 089 * Returns {@code true} if {@code x} represents a power of two. 090 * 091 * <p>This differs from {@code Integer.bitCount(x) == 1}, because {@code 092 * Integer.bitCount(Integer.MIN_VALUE) == 1}, but {@link Integer#MIN_VALUE} is not a power 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 {@code 266 * sqrt(x)} is not an integer 267 */ 268 @GwtIncompatible // need BigIntegerMath to adequately test 269 @SuppressWarnings("fallthrough") 270 public static int sqrt(int x, RoundingMode mode) { 271 checkNonNegative("x", x); 272 int sqrtFloor = sqrtFloor(x); 273 switch (mode) { 274 case UNNECESSARY: 275 checkRoundingUnnecessary(sqrtFloor * sqrtFloor == x); // fall through 276 case FLOOR: 277 case DOWN: 278 return sqrtFloor; 279 case CEILING: 280 case UP: 281 return sqrtFloor + lessThanBranchFree(sqrtFloor * sqrtFloor, x); 282 case HALF_DOWN: 283 case HALF_UP: 284 case HALF_EVEN: 285 int halfSquare = sqrtFloor * sqrtFloor + sqrtFloor; 286 /* 287 * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. Since both x 288 * and halfSquare are integers, this is equivalent to testing whether or not x <= 289 * halfSquare. (We have to deal with overflow, though.) 290 * 291 * If we treat halfSquare as an unsigned int, we know that 292 * sqrtFloor^2 <= x < (sqrtFloor + 1)^2 293 * halfSquare - sqrtFloor <= x < halfSquare + sqrtFloor + 1 294 * so |x - halfSquare| <= sqrtFloor. Therefore, it's safe to treat x - halfSquare as a 295 * signed int, so lessThanBranchFree is safe for use. 296 */ 297 return sqrtFloor + lessThanBranchFree(halfSquare, x); 298 default: 299 throw new AssertionError(); 300 } 301 } 302 303 private static int sqrtFloor(int x) { 304 // There is no loss of precision in converting an int to a double, according to 305 // http://java.sun.com/docs/books/jls/third_edition/html/conversions.html#5.1.2 306 return (int) Math.sqrt(x); 307 } 308 309 /** 310 * Returns the result of dividing {@code p} by {@code q}, rounding using the specified {@code 311 * RoundingMode}. 312 * 313 * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a} 314 * is not an integer multiple of {@code b} 315 */ 316 @SuppressWarnings("fallthrough") 317 public static int divide(int p, int q, RoundingMode mode) { 318 checkNotNull(mode); 319 if (q == 0) { 320 throw new ArithmeticException("/ by zero"); // for GWT 321 } 322 int div = p / q; 323 int rem = p - q * div; // equal to p % q 324 325 if (rem == 0) { 326 return div; 327 } 328 329 /* 330 * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to 331 * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of 332 * p / q. 333 * 334 * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise. 335 */ 336 int signum = 1 | ((p ^ q) >> (Integer.SIZE - 1)); 337 boolean increment; 338 switch (mode) { 339 case UNNECESSARY: 340 checkRoundingUnnecessary(rem == 0); 341 // fall through 342 case DOWN: 343 increment = false; 344 break; 345 case UP: 346 increment = true; 347 break; 348 case CEILING: 349 increment = signum > 0; 350 break; 351 case FLOOR: 352 increment = signum < 0; 353 break; 354 case HALF_EVEN: 355 case HALF_DOWN: 356 case HALF_UP: 357 int absRem = abs(rem); 358 int cmpRemToHalfDivisor = absRem - (abs(q) - absRem); 359 // subtracting two nonnegative ints can't overflow 360 // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2). 361 if (cmpRemToHalfDivisor == 0) { // exactly on the half mark 362 increment = (mode == HALF_UP || (mode == HALF_EVEN & (div & 1) != 0)); 363 } else { 364 increment = cmpRemToHalfDivisor > 0; // closer to the UP value 365 } 366 break; 367 default: 368 throw new AssertionError(); 369 } 370 return increment ? div + signum : div; 371 } 372 373 /** 374 * Returns {@code x mod m}, a non-negative value less than {@code m}. This differs from {@code x % 375 * m}, which might be negative. 376 * 377 * <p>For example: 378 * 379 * <pre>{@code 380 * mod(7, 4) == 3 381 * mod(-7, 4) == 1 382 * mod(-1, 4) == 3 383 * mod(-8, 4) == 0 384 * mod(8, 4) == 0 385 * }</pre> 386 * 387 * @throws ArithmeticException if {@code m <= 0} 388 * @see <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.17.3"> 389 * Remainder Operator</a> 390 */ 391 public static int mod(int x, int m) { 392 if (m <= 0) { 393 throw new ArithmeticException("Modulus " + m + " must be > 0"); 394 } 395 int result = x % m; 396 return (result >= 0) ? result : result + m; 397 } 398 399 /** 400 * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if {@code a == 0 && b == 401 * 0}. 402 * 403 * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0} 404 */ 405 public static int gcd(int a, int b) { 406 /* 407 * The reason we require both arguments to be >= 0 is because otherwise, what do you return on 408 * gcd(0, Integer.MIN_VALUE)? BigInteger.gcd would return positive 2^31, but positive 2^31 isn't 409 * an int. 410 */ 411 checkNonNegative("a", a); 412 checkNonNegative("b", b); 413 if (a == 0) { 414 // 0 % b == 0, so b divides a, but the converse doesn't hold. 415 // BigInteger.gcd is consistent with this decision. 416 return b; 417 } else if (b == 0) { 418 return a; // similar logic 419 } 420 /* 421 * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm. This is 422 * >40% faster than the Euclidean algorithm in benchmarks. 423 */ 424 int aTwos = Integer.numberOfTrailingZeros(a); 425 a >>= aTwos; // divide out all 2s 426 int bTwos = Integer.numberOfTrailingZeros(b); 427 b >>= bTwos; // divide out all 2s 428 while (a != b) { // both a, b are odd 429 // The key to the binary GCD algorithm is as follows: 430 // Both a and b are odd. Assume a > b; then gcd(a - b, b) = gcd(a, b). 431 // But in gcd(a - b, b), a - b is even and b is odd, so we can divide out powers of two. 432 433 // We bend over backwards to avoid branching, adapting a technique from 434 // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax 435 436 int delta = a - b; // can't overflow, since a and b are nonnegative 437 438 int minDeltaOrZero = delta & (delta >> (Integer.SIZE - 1)); 439 // equivalent to Math.min(delta, 0) 440 441 a = delta - minDeltaOrZero - minDeltaOrZero; // sets a to Math.abs(a - b) 442 // a is now nonnegative and even 443 444 b += minDeltaOrZero; // sets b to min(old a, b) 445 a >>= Integer.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b 446 } 447 return a << min(aTwos, bTwos); 448 } 449 450 /** 451 * Returns the sum of {@code a} and {@code b}, provided it does not overflow. 452 * 453 * @throws ArithmeticException if {@code a + b} overflows in signed {@code int} arithmetic 454 */ 455 public static int checkedAdd(int a, int b) { 456 long result = (long) a + b; 457 checkNoOverflow(result == (int) result, "checkedAdd", a, b); 458 return (int) result; 459 } 460 461 /** 462 * Returns the difference of {@code a} and {@code b}, provided it does not overflow. 463 * 464 * @throws ArithmeticException if {@code a - b} overflows in signed {@code int} arithmetic 465 */ 466 public static int checkedSubtract(int a, int b) { 467 long result = (long) a - b; 468 checkNoOverflow(result == (int) result, "checkedSubtract", a, b); 469 return (int) result; 470 } 471 472 /** 473 * Returns the product of {@code a} and {@code b}, provided it does not overflow. 474 * 475 * @throws ArithmeticException if {@code a * b} overflows in signed {@code int} arithmetic 476 */ 477 public static int checkedMultiply(int a, int b) { 478 long result = (long) a * b; 479 checkNoOverflow(result == (int) result, "checkedMultiply", a, b); 480 return (int) result; 481 } 482 483 /** 484 * Returns the {@code b} to the {@code k}th power, provided it does not overflow. 485 * 486 * <p>{@link #pow} may be faster, but does not check for overflow. 487 * 488 * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed {@code 489 * int} arithmetic 490 */ 491 public static int checkedPow(int b, int k) { 492 checkNonNegative("exponent", k); 493 switch (b) { 494 case 0: 495 return (k == 0) ? 1 : 0; 496 case 1: 497 return 1; 498 case (-1): 499 return ((k & 1) == 0) ? 1 : -1; 500 case 2: 501 checkNoOverflow(k < Integer.SIZE - 1, "checkedPow", b, k); 502 return 1 << k; 503 case (-2): 504 checkNoOverflow(k < Integer.SIZE, "checkedPow", b, k); 505 return ((k & 1) == 0) ? 1 << k : -1 << k; 506 default: 507 // continue below to handle the general case 508 } 509 int accum = 1; 510 while (true) { 511 switch (k) { 512 case 0: 513 return accum; 514 case 1: 515 return checkedMultiply(accum, b); 516 default: 517 if ((k & 1) != 0) { 518 accum = checkedMultiply(accum, b); 519 } 520 k >>= 1; 521 if (k > 0) { 522 checkNoOverflow(-FLOOR_SQRT_MAX_INT <= b & b <= FLOOR_SQRT_MAX_INT, "checkedPow", b, k); 523 b *= b; 524 } 525 } 526 } 527 } 528 529 /** 530 * Returns the sum of {@code a} and {@code b} unless it would overflow or underflow in which case 531 * {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively. 532 * 533 * @since 20.0 534 */ 535 @Beta 536 public static int saturatedAdd(int a, int b) { 537 return Ints.saturatedCast((long) a + b); 538 } 539 540 /** 541 * Returns the difference of {@code a} and {@code b} unless it would overflow or underflow in 542 * which case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively. 543 * 544 * @since 20.0 545 */ 546 @Beta 547 public static int saturatedSubtract(int a, int b) { 548 return Ints.saturatedCast((long) a - b); 549 } 550 551 /** 552 * Returns the product of {@code a} and {@code b} unless it would overflow or underflow in which 553 * case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively. 554 * 555 * @since 20.0 556 */ 557 @Beta 558 public static int saturatedMultiply(int a, int b) { 559 return Ints.saturatedCast((long) a * b); 560 } 561 562 /** 563 * Returns the {@code b} to the {@code k}th power, unless it would overflow or underflow in which 564 * case {@code Integer.MAX_VALUE} or {@code Integer.MIN_VALUE} is returned, respectively. 565 * 566 * @since 20.0 567 */ 568 @Beta 569 public static int saturatedPow(int b, int k) { 570 checkNonNegative("exponent", k); 571 switch (b) { 572 case 0: 573 return (k == 0) ? 1 : 0; 574 case 1: 575 return 1; 576 case (-1): 577 return ((k & 1) == 0) ? 1 : -1; 578 case 2: 579 if (k >= Integer.SIZE - 1) { 580 return Integer.MAX_VALUE; 581 } 582 return 1 << k; 583 case (-2): 584 if (k >= Integer.SIZE) { 585 return Integer.MAX_VALUE + (k & 1); 586 } 587 return ((k & 1) == 0) ? 1 << k : -1 << k; 588 default: 589 // continue below to handle the general case 590 } 591 int accum = 1; 592 // if b is negative and k is odd then the limit is MIN otherwise the limit is MAX 593 int limit = Integer.MAX_VALUE + ((b >>> Integer.SIZE - 1) & (k & 1)); 594 while (true) { 595 switch (k) { 596 case 0: 597 return accum; 598 case 1: 599 return saturatedMultiply(accum, b); 600 default: 601 if ((k & 1) != 0) { 602 accum = saturatedMultiply(accum, b); 603 } 604 k >>= 1; 605 if (k > 0) { 606 if (-FLOOR_SQRT_MAX_INT > b | b > FLOOR_SQRT_MAX_INT) { 607 return limit; 608 } 609 b *= b; 610 } 611 } 612 } 613 } 614 615 @VisibleForTesting static final int FLOOR_SQRT_MAX_INT = 46340; 616 617 /** 618 * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if 619 * {@code n == 0}, or {@link Integer#MAX_VALUE} if the result does not fit in a {@code int}. 620 * 621 * @throws IllegalArgumentException if {@code n < 0} 622 */ 623 public static int factorial(int n) { 624 checkNonNegative("n", n); 625 return (n < factorials.length) ? factorials[n] : Integer.MAX_VALUE; 626 } 627 628 private static final int[] factorials = { 629 1, 630 1, 631 1 * 2, 632 1 * 2 * 3, 633 1 * 2 * 3 * 4, 634 1 * 2 * 3 * 4 * 5, 635 1 * 2 * 3 * 4 * 5 * 6, 636 1 * 2 * 3 * 4 * 5 * 6 * 7, 637 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8, 638 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9, 639 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10, 640 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11, 641 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 642 }; 643 644 /** 645 * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and 646 * {@code k}, or {@link Integer#MAX_VALUE} if the result does not fit in an {@code int}. 647 * 648 * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0} or {@code k > n} 649 */ 650 public static int binomial(int n, int k) { 651 checkNonNegative("n", n); 652 checkNonNegative("k", k); 653 checkArgument(k <= n, "k (%s) > n (%s)", k, n); 654 if (k > (n >> 1)) { 655 k = n - k; 656 } 657 if (k >= biggestBinomials.length || n > biggestBinomials[k]) { 658 return Integer.MAX_VALUE; 659 } 660 switch (k) { 661 case 0: 662 return 1; 663 case 1: 664 return n; 665 default: 666 long result = 1; 667 for (int i = 0; i < k; i++) { 668 result *= n - i; 669 result /= i + 1; 670 } 671 return (int) result; 672 } 673 } 674 675 // binomial(biggestBinomials[k], k) fits in an int, but not binomial(biggestBinomials[k]+1,k). 676 @VisibleForTesting 677 static int[] biggestBinomials = { 678 Integer.MAX_VALUE, 679 Integer.MAX_VALUE, 680 65536, 681 2345, 682 477, 683 193, 684 110, 685 75, 686 58, 687 49, 688 43, 689 39, 690 37, 691 35, 692 34, 693 34, 694 33 695 }; 696 697 /** 698 * Returns the arithmetic mean of {@code x} and {@code y}, rounded towards negative infinity. This 699 * method is overflow resilient. 700 * 701 * @since 14.0 702 */ 703 public static int mean(int x, int y) { 704 // Efficient method for computing the arithmetic mean. 705 // The alternative (x + y) / 2 fails for large values. 706 // The alternative (x + y) >>> 1 fails for negative values. 707 return (x & y) + ((x ^ y) >> 1); 708 } 709 710 /** 711 * Returns {@code true} if {@code n} is a <a 712 * href="http://mathworld.wolfram.com/PrimeNumber.html">prime number</a>: an integer <i>greater 713 * than one</i> that cannot be factored into a product of <i>smaller</i> positive integers. 714 * Returns {@code false} if {@code n} is zero, one, or a composite number (one which <i>can</i> be 715 * factored into smaller positive integers). 716 * 717 * <p>To test larger numbers, use {@link LongMath#isPrime} or {@link BigInteger#isProbablePrime}. 718 * 719 * @throws IllegalArgumentException if {@code n} is negative 720 * @since 20.0 721 */ 722 @GwtIncompatible // TODO 723 @Beta 724 public static boolean isPrime(int n) { 725 return LongMath.isPrime(n); 726 } 727 728 private IntMath() {} 729}