001 /*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.math;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021 import static com.google.common.math.MathPreconditions.checkNoOverflow;
022 import static com.google.common.math.MathPreconditions.checkNonNegative;
023 import static com.google.common.math.MathPreconditions.checkPositive;
024 import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
025 import static java.lang.Math.abs;
026 import static java.math.RoundingMode.HALF_EVEN;
027 import static java.math.RoundingMode.HALF_UP;
028
029 import com.google.common.annotations.Beta;
030 import com.google.common.annotations.GwtCompatible;
031 import com.google.common.annotations.GwtIncompatible;
032 import com.google.common.annotations.VisibleForTesting;
033
034 import java.math.BigInteger;
035 import java.math.RoundingMode;
036
037 /**
038 * A class for arithmetic on values of type {@code int}. Where possible, methods are defined and
039 * named analogously to their {@code BigInteger} counterparts.
040 *
041 * <p>The implementations of many methods in this class are based on material from Henry S. Warren,
042 * Jr.'s <i>Hacker's Delight</i>, (Addison Wesley, 2002).
043 *
044 * <p>Similar functionality for {@code long} and for {@link BigInteger} can be found in
045 * {@link LongMath} and {@link BigIntegerMath} respectively. For other common operations on
046 * {@code int} values, see {@link com.google.common.primitives.Ints}.
047 *
048 * @author Louis Wasserman
049 * @since 11.0
050 */
051 @Beta
052 @GwtCompatible(emulated = true)
053 public final class IntMath {
054 // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
055
056 /**
057 * Returns {@code true} if {@code x} represents a power of two.
058 *
059 * <p>This differs from {@code Integer.bitCount(x) == 1}, because
060 * {@code Integer.bitCount(Integer.MIN_VALUE) == 1}, but {@link Integer#MIN_VALUE} is not a power
061 * of two.
062 */
063 public static boolean isPowerOfTwo(int x) {
064 return x > 0 & (x & (x - 1)) == 0;
065 }
066
067 /**
068 * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode.
069 *
070 * @throws IllegalArgumentException if {@code x <= 0}
071 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
072 * is not a power of two
073 */
074 @GwtIncompatible("need BigIntegerMath to adequately test")
075 @SuppressWarnings("fallthrough")
076 public static int log2(int x, RoundingMode mode) {
077 checkPositive("x", x);
078 switch (mode) {
079 case UNNECESSARY:
080 checkRoundingUnnecessary(isPowerOfTwo(x));
081 // fall through
082 case DOWN:
083 case FLOOR:
084 return (Integer.SIZE - 1) - Integer.numberOfLeadingZeros(x);
085
086 case UP:
087 case CEILING:
088 return Integer.SIZE - Integer.numberOfLeadingZeros(x - 1);
089
090 case HALF_DOWN:
091 case HALF_UP:
092 case HALF_EVEN:
093 // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5
094 int leadingZeros = Integer.numberOfLeadingZeros(x);
095 int cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros;
096 // floor(2^(logFloor + 0.5))
097 int logFloor = (Integer.SIZE - 1) - leadingZeros;
098 return (x <= cmp) ? logFloor : logFloor + 1;
099
100 default:
101 throw new AssertionError();
102 }
103 }
104
105 /** The biggest half power of two that can fit in an unsigned int. */
106 @VisibleForTesting static final int MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333;
107
108 /**
109 * Returns the base-10 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 ten
114 */
115 @GwtIncompatible("need BigIntegerMath to adequately test")
116 @SuppressWarnings("fallthrough")
117 public static int log10(int x, RoundingMode mode) {
118 checkPositive("x", x);
119 int logFloor = log10Floor(x);
120 int floorPow = POWERS_OF_10[logFloor];
121 switch (mode) {
122 case UNNECESSARY:
123 checkRoundingUnnecessary(x == floorPow);
124 // fall through
125 case FLOOR:
126 case DOWN:
127 return logFloor;
128 case CEILING:
129 case UP:
130 return (x == floorPow) ? logFloor : logFloor + 1;
131 case HALF_DOWN:
132 case HALF_UP:
133 case HALF_EVEN:
134 // sqrt(10) is irrational, so log10(x) - logFloor is never exactly 0.5
135 return (x <= HALF_POWERS_OF_10[logFloor]) ? logFloor : logFloor + 1;
136 default:
137 throw new AssertionError();
138 }
139 }
140
141 private static int log10Floor(int x) {
142 for (int i = 1; i < POWERS_OF_10.length; i++) {
143 if (x < POWERS_OF_10[i]) {
144 return i - 1;
145 }
146 }
147 return POWERS_OF_10.length - 1;
148 }
149
150 @VisibleForTesting static final int[] POWERS_OF_10 =
151 {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
152
153 // HALF_POWERS_OF_10[i] = largest int less than 10^(i + 0.5)
154 @VisibleForTesting static final int[] HALF_POWERS_OF_10 =
155 {3, 31, 316, 3162, 31622, 316227, 3162277, 31622776, 316227766, Integer.MAX_VALUE};
156
157 /**
158 * Returns {@code b} to the {@code k}th power. Even if the result overflows, it will be equal to
159 * {@code BigInteger.valueOf(b).pow(k).intValue()}. This implementation runs in {@code O(log k)}
160 * time.
161 *
162 * <p>Compare {@link #checkedPow}, which throws an {@link ArithmeticException} upon overflow.
163 *
164 * @throws IllegalArgumentException if {@code k < 0}
165 */
166 @GwtIncompatible("failing tests")
167 public static int pow(int b, int k) {
168 checkNonNegative("exponent", k);
169 switch (b) {
170 case 0:
171 return (k == 0) ? 1 : 0;
172 case 1:
173 return 1;
174 case (-1):
175 return ((k & 1) == 0) ? 1 : -1;
176 case 2:
177 return (k < Integer.SIZE) ? (1 << k) : 0;
178 case (-2):
179 if (k < Integer.SIZE) {
180 return ((k & 1) == 0) ? (1 << k) : -(1 << k);
181 } else {
182 return 0;
183 }
184 }
185 for (int accum = 1;; k >>= 1) {
186 switch (k) {
187 case 0:
188 return accum;
189 case 1:
190 return b * accum;
191 default:
192 accum *= ((k & 1) == 0) ? 1 : b;
193 b *= b;
194 }
195 }
196 }
197
198 /**
199 * Returns the square root of {@code x}, rounded with the specified rounding mode.
200 *
201 * @throws IllegalArgumentException if {@code x < 0}
202 * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and
203 * {@code sqrt(x)} is not an integer
204 */
205 @GwtIncompatible("need BigIntegerMath to adequately test")
206 @SuppressWarnings("fallthrough")
207 public static int sqrt(int x, RoundingMode mode) {
208 checkNonNegative("x", x);
209 int sqrtFloor = sqrtFloor(x);
210 switch (mode) {
211 case UNNECESSARY:
212 checkRoundingUnnecessary(sqrtFloor * sqrtFloor == x); // fall through
213 case FLOOR:
214 case DOWN:
215 return sqrtFloor;
216 case CEILING:
217 case UP:
218 return (sqrtFloor * sqrtFloor == x) ? sqrtFloor : sqrtFloor + 1;
219 case HALF_DOWN:
220 case HALF_UP:
221 case HALF_EVEN:
222 int halfSquare = sqrtFloor * sqrtFloor + sqrtFloor;
223 /*
224 * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25.
225 * Since both x and halfSquare are integers, this is equivalent to testing whether or not
226 * x <= halfSquare. (We have to deal with overflow, though.)
227 */
228 return (x <= halfSquare | halfSquare < 0) ? sqrtFloor : sqrtFloor + 1;
229 default:
230 throw new AssertionError();
231 }
232 }
233
234 private static int sqrtFloor(int x) {
235 // There is no loss of precision in converting an int to a double, according to
236 // http://java.sun.com/docs/books/jls/third_edition/html/conversions.html#5.1.2
237 return (int) Math.sqrt(x);
238 }
239
240 /**
241 * Returns the result of dividing {@code p} by {@code q}, rounding using the specified
242 * {@code RoundingMode}.
243 *
244 * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a}
245 * is not an integer multiple of {@code b}
246 */
247 @GwtIncompatible("failing tests")
248 @SuppressWarnings("fallthrough")
249 public static int divide(int p, int q, RoundingMode mode) {
250 checkNotNull(mode);
251 if (q == 0) {
252 throw new ArithmeticException("/ by zero"); // for GWT
253 }
254 int div = p / q;
255 int rem = p - q * div; // equal to p % q
256
257 if (rem == 0) {
258 return div;
259 }
260
261 /*
262 * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to
263 * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of
264 * p / q.
265 *
266 * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise.
267 */
268 int signum = 1 | ((p ^ q) >> (Integer.SIZE - 1));
269 boolean increment;
270 switch (mode) {
271 case UNNECESSARY:
272 checkRoundingUnnecessary(rem == 0);
273 // fall through
274 case DOWN:
275 increment = false;
276 break;
277 case UP:
278 increment = true;
279 break;
280 case CEILING:
281 increment = signum > 0;
282 break;
283 case FLOOR:
284 increment = signum < 0;
285 break;
286 case HALF_EVEN:
287 case HALF_DOWN:
288 case HALF_UP:
289 int absRem = abs(rem);
290 int cmpRemToHalfDivisor = absRem - (abs(q) - absRem);
291 // subtracting two nonnegative ints can't overflow
292 // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2).
293 if (cmpRemToHalfDivisor == 0) { // exactly on the half mark
294 increment = (mode == HALF_UP || (mode == HALF_EVEN & (div & 1) != 0));
295 } else {
296 increment = cmpRemToHalfDivisor > 0; // closer to the UP value
297 }
298 break;
299 default:
300 throw new AssertionError();
301 }
302 return increment ? div + signum : div;
303 }
304
305 /**
306 * Returns {@code x mod m}. This differs from {@code x % m} in that it always returns a
307 * non-negative result.
308 *
309 * <p>For example:<pre> {@code
310 *
311 * mod(7, 4) == 3
312 * mod(-7, 4) == 1
313 * mod(-1, 4) == 3
314 * mod(-8, 4) == 0
315 * mod(8, 4) == 0}</pre>
316 *
317 * @throws ArithmeticException if {@code m <= 0}
318 */
319 public static int mod(int x, int m) {
320 if (m <= 0) {
321 throw new ArithmeticException("Modulus " + m + " must be > 0");
322 }
323 int result = x % m;
324 return (result >= 0) ? result : result + m;
325 }
326
327 /**
328 * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if
329 * {@code a == 0 && b == 0}.
330 *
331 * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0}
332 */
333 public static int gcd(int a, int b) {
334 /*
335 * The reason we require both arguments to be >= 0 is because otherwise, what do you return on
336 * gcd(0, Integer.MIN_VALUE)? BigInteger.gcd would return positive 2^31, but positive 2^31
337 * isn't an int.
338 */
339 checkNonNegative("a", a);
340 checkNonNegative("b", b);
341 // The simple Euclidean algorithm is the fastest for ints, and is easily the most readable.
342 while (b != 0) {
343 int t = b;
344 b = a % b;
345 a = t;
346 }
347 return a;
348 }
349
350 /**
351 * Returns the sum of {@code a} and {@code b}, provided it does not overflow.
352 *
353 * @throws ArithmeticException if {@code a + b} overflows in signed {@code int} arithmetic
354 */
355 public static int checkedAdd(int a, int b) {
356 long result = (long) a + b;
357 checkNoOverflow(result == (int) result);
358 return (int) result;
359 }
360
361 /**
362 * Returns the difference of {@code a} and {@code b}, provided it does not overflow.
363 *
364 * @throws ArithmeticException if {@code a - b} overflows in signed {@code int} arithmetic
365 */
366 public static int checkedSubtract(int a, int b) {
367 long result = (long) a - b;
368 checkNoOverflow(result == (int) result);
369 return (int) result;
370 }
371
372 /**
373 * Returns the product of {@code a} and {@code b}, provided it does not overflow.
374 *
375 * @throws ArithmeticException if {@code a * b} overflows in signed {@code int} arithmetic
376 */
377 public static int checkedMultiply(int a, int b) {
378 long result = (long) a * b;
379 checkNoOverflow(result == (int) result);
380 return (int) result;
381 }
382
383 /**
384 * Returns the {@code b} to the {@code k}th power, provided it does not overflow.
385 *
386 * <p>{@link #pow} may be faster, but does not check for overflow.
387 *
388 * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed
389 * {@code int} arithmetic
390 */
391 @GwtIncompatible("failing tests")
392 public static int checkedPow(int b, int k) {
393 checkNonNegative("exponent", k);
394 switch (b) {
395 case 0:
396 return (k == 0) ? 1 : 0;
397 case 1:
398 return 1;
399 case (-1):
400 return ((k & 1) == 0) ? 1 : -1;
401 case 2:
402 checkNoOverflow(k < Integer.SIZE - 1);
403 return 1 << k;
404 case (-2):
405 checkNoOverflow(k < Integer.SIZE);
406 return ((k & 1) == 0) ? 1 << k : -1 << k;
407 }
408 int accum = 1;
409 while (true) {
410 switch (k) {
411 case 0:
412 return accum;
413 case 1:
414 return checkedMultiply(accum, b);
415 default:
416 if ((k & 1) != 0) {
417 accum = checkedMultiply(accum, b);
418 }
419 k >>= 1;
420 if (k > 0) {
421 checkNoOverflow(-FLOOR_SQRT_MAX_INT <= b & b <= FLOOR_SQRT_MAX_INT);
422 b *= b;
423 }
424 }
425 }
426 }
427
428 @VisibleForTesting static final int FLOOR_SQRT_MAX_INT = 46340;
429
430 /**
431 * Returns {@code n!}, that is, the product of the first {@code n} positive
432 * integers, {@code 1} if {@code n == 0}, or {@link Integer#MAX_VALUE} if the
433 * result does not fit in a {@code int}.
434 *
435 * @throws IllegalArgumentException if {@code n < 0}
436 */
437 @GwtIncompatible("need BigIntegerMath to adequately test")
438 public static int factorial(int n) {
439 checkNonNegative("n", n);
440 return (n < FACTORIALS.length) ? FACTORIALS[n] : Integer.MAX_VALUE;
441 }
442
443 static final int[] FACTORIALS = {
444 1,
445 1,
446 1 * 2,
447 1 * 2 * 3,
448 1 * 2 * 3 * 4,
449 1 * 2 * 3 * 4 * 5,
450 1 * 2 * 3 * 4 * 5 * 6,
451 1 * 2 * 3 * 4 * 5 * 6 * 7,
452 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8,
453 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
454 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
455 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
456 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12};
457
458 /**
459 * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and
460 * {@code k}, or {@link Integer#MAX_VALUE} if the result does not fit in an {@code int}.
461 *
462 * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0} or {@code k > n}
463 */
464 @GwtIncompatible("need BigIntegerMath to adequately test")
465 public static int binomial(int n, int k) {
466 checkNonNegative("n", n);
467 checkNonNegative("k", k);
468 checkArgument(k <= n, "k (%s) > n (%s)", k, n);
469 if (k > (n >> 1)) {
470 k = n - k;
471 }
472 if (k >= BIGGEST_BINOMIALS.length || n > BIGGEST_BINOMIALS[k]) {
473 return Integer.MAX_VALUE;
474 }
475 switch (k) {
476 case 0:
477 return 1;
478 case 1:
479 return n;
480 default:
481 long result = 1;
482 for (int i = 0; i < k; i++) {
483 result *= n - i;
484 result /= i + 1;
485 }
486 return (int) result;
487 }
488 }
489
490 // binomial(BIGGEST_BINOMIALS[k], k) fits in an int, but not binomial(BIGGEST_BINOMIALS[k]+1,k).
491 @VisibleForTesting static int[] BIGGEST_BINOMIALS = {
492 Integer.MAX_VALUE,
493 Integer.MAX_VALUE,
494 65536,
495 2345,
496 477,
497 193,
498 110,
499 75,
500 58,
501 49,
502 43,
503 39,
504 37,
505 35,
506 34,
507 34,
508 33
509 };
510
511 private IntMath() {}
512 }