A class for arithmetic on values of type BigInteger. The implementations of many methods in this class are based on material from Henry S. Warren, Jr.'s Hacker's Delight , (Addison Wesley, 2002). Similar functionality for int and for long can be found in {@link
| 47 | |
| 48 | |
| 49 | @GwtCompatible(emulated = true) |
| 50 | public final class BigIntegerMath { |
| 51 | /** |
| 52 | * Returns the smallest power of two greater than or equal to {@code x}. This is equivalent to |
| 53 | * {@code BigInteger.valueOf(2).pow(log2(x, CEILING))}. |
| 54 | * |
| 55 | * @throws IllegalArgumentException if {@code x <= 0} |
| 56 | * @since 20.0 |
| 57 | */ |
| 58 | @Beta |
| 59 | public static BigInteger ceilingPowerOfTwo(BigInteger x) { |
| 60 | return BigInteger.ZERO.setBit(log2(x, RoundingMode.CEILING)); |
| 61 | } |
| 62 | |
| 63 | /** |
| 64 | * Returns the largest power of two less than or equal to {@code x}. This is equivalent to |
| 65 | * {@code BigInteger.valueOf(2).pow(log2(x, FLOOR))}. |
| 66 | * |
| 67 | * @throws IllegalArgumentException if {@code x <= 0} |
| 68 | * @since 20.0 |
| 69 | */ |
| 70 | |
| 71 | @Beta |
| 72 | public static BigInteger floorPowerOfTwo(BigInteger x) { |
| 73 | return BigInteger.ZERO.setBit(log2(x, RoundingMode.FLOOR)); |
| 74 | } |
| 75 | |
| 76 | /** |
| 77 | * Returns {@code true} if {@code x} represents a power of two. |
| 78 | */ |
| 79 | |
| 80 | |
| 81 | public static boolean isPowerOfTwo(BigInteger x) { |
| 82 | checkNotNull(x); |
| 83 | return x.signum() > 0 && x.getLowestSetBit() == x.bitLength() - 1; |
| 84 | } |
| 85 | |
| 86 | /** |
| 87 | * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode. |
| 88 | * |
| 89 | * @throws IllegalArgumentException if {@code x <= 0} |
| 90 | * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x} |
| 91 | * is not a power of two |
| 92 | */ |
| 93 | |
| 94 | @SuppressWarnings("fallthrough") |
| 95 | // TODO(kevinb): remove after this warning is disabled globally |
| 96 | public static int log2(BigInteger x, RoundingMode mode) { |
| 97 | checkPositive("x", checkNotNull(x)); |
| 98 | int logFloor = x.bitLength() - 1; |
| 99 | switch (mode) { |
| 100 | case UNNECESSARY: |
| 101 | checkRoundingUnnecessary(isPowerOfTwo(x)); // fall through |
| 102 | case DOWN: |
| 103 | case FLOOR: |
| 104 | return logFloor; |
| 105 | case UP: |
| 106 | case CEILING: |