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.primitives; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkNotNull; 019import static com.google.common.base.Preconditions.checkPositionIndexes; 020 021import com.google.common.annotations.Beta; 022import com.google.common.annotations.GwtCompatible; 023import com.google.errorprone.annotations.CanIgnoreReturnValue; 024import java.math.BigInteger; 025import java.util.Arrays; 026import java.util.Comparator; 027 028/** 029 * Static utility methods pertaining to {@code long} primitives that interpret values as 030 * <i>unsigned</i> (that is, any negative value {@code x} is treated as the positive value {@code 031 * 2^64 + x}). The methods for which signedness is not an issue are in {@link Longs}, as well as 032 * signed versions of methods for which signedness is an issue. 033 * 034 * <p>In addition, this class provides several static methods for converting a {@code long} to a 035 * {@code String} and a {@code String} to a {@code long} that treat the {@code long} as an unsigned 036 * number. 037 * 038 * <p>Users of these utilities must be <i>extremely careful</i> not to mix up signed and unsigned 039 * {@code long} values. When possible, it is recommended that the {@link UnsignedLong} wrapper class 040 * be used, at a small efficiency penalty, to enforce the distinction in the type system. 041 * 042 * <p>See the Guava User Guide article on <a 043 * href="https://github.com/google/guava/wiki/PrimitivesExplained#unsigned-support">unsigned 044 * primitive utilities</a>. 045 * 046 * @author Louis Wasserman 047 * @author Brian Milch 048 * @author Colin Evans 049 * @since 10.0 050 */ 051@Beta 052@GwtCompatible 053@ElementTypesAreNonnullByDefault 054public final class UnsignedLongs { 055 private UnsignedLongs() {} 056 057 public static final long MAX_VALUE = -1L; // Equivalent to 2^64 - 1 058 059 /** 060 * A (self-inverse) bijection which converts the ordering on unsigned longs to the ordering on 061 * longs, that is, {@code a <= b} as unsigned longs if and only if {@code flip(a) <= flip(b)} as 062 * signed longs. 063 */ 064 private static long flip(long a) { 065 return a ^ Long.MIN_VALUE; 066 } 067 068 /** 069 * Compares the two specified {@code long} values, treating them as unsigned values between {@code 070 * 0} and {@code 2^64 - 1} inclusive. 071 * 072 * <p><b>Java 8 users:</b> use {@link Long#compareUnsigned(long, long)} instead. 073 * 074 * @param a the first unsigned {@code long} to compare 075 * @param b the second unsigned {@code long} to compare 076 * @return a negative value if {@code a} is less than {@code b}; a positive value if {@code a} is 077 * greater than {@code b}; or zero if they are equal 078 */ 079 public static int compare(long a, long b) { 080 return Longs.compare(flip(a), flip(b)); 081 } 082 083 /** 084 * Returns the least value present in {@code array}, treating values as unsigned. 085 * 086 * @param array a <i>nonempty</i> array of unsigned {@code long} values 087 * @return the value present in {@code array} that is less than or equal to every other value in 088 * the array according to {@link #compare} 089 * @throws IllegalArgumentException if {@code array} is empty 090 */ 091 public static long min(long... array) { 092 checkArgument(array.length > 0); 093 long min = flip(array[0]); 094 for (int i = 1; i < array.length; i++) { 095 long next = flip(array[i]); 096 if (next < min) { 097 min = next; 098 } 099 } 100 return flip(min); 101 } 102 103 /** 104 * Returns the greatest value present in {@code array}, treating values as unsigned. 105 * 106 * @param array a <i>nonempty</i> array of unsigned {@code long} values 107 * @return the value present in {@code array} that is greater than or equal to every other value 108 * in the array according to {@link #compare} 109 * @throws IllegalArgumentException if {@code array} is empty 110 */ 111 public static long max(long... array) { 112 checkArgument(array.length > 0); 113 long max = flip(array[0]); 114 for (int i = 1; i < array.length; i++) { 115 long next = flip(array[i]); 116 if (next > max) { 117 max = next; 118 } 119 } 120 return flip(max); 121 } 122 123 /** 124 * Returns a string containing the supplied unsigned {@code long} values separated by {@code 125 * separator}. For example, {@code join("-", 1, 2, 3)} returns the string {@code "1-2-3"}. 126 * 127 * @param separator the text that should appear between consecutive values in the resulting string 128 * (but not at the start or end) 129 * @param array an array of unsigned {@code long} values, possibly empty 130 */ 131 public static String join(String separator, long... array) { 132 checkNotNull(separator); 133 if (array.length == 0) { 134 return ""; 135 } 136 137 // For pre-sizing a builder, just get the right order of magnitude 138 StringBuilder builder = new StringBuilder(array.length * 5); 139 builder.append(toString(array[0])); 140 for (int i = 1; i < array.length; i++) { 141 builder.append(separator).append(toString(array[i])); 142 } 143 return builder.toString(); 144 } 145 146 /** 147 * Returns a comparator that compares two arrays of unsigned {@code long} values <a 148 * href="http://en.wikipedia.org/wiki/Lexicographical_order">lexicographically</a>. That is, it 149 * compares, using {@link #compare(long, long)}), the first pair of values that follow any common 150 * prefix, or when one array is a prefix of the other, treats the shorter array as the lesser. For 151 * example, {@code [] < [1L] < [1L, 2L] < [2L] < [1L << 63]}. 152 * 153 * <p>The returned comparator is inconsistent with {@link Object#equals(Object)} (since arrays 154 * support only identity equality), but it is consistent with {@link Arrays#equals(long[], 155 * long[])}. 156 */ 157 public static Comparator<long[]> lexicographicalComparator() { 158 return LexicographicalComparator.INSTANCE; 159 } 160 161 enum LexicographicalComparator implements Comparator<long[]> { 162 INSTANCE; 163 164 @Override 165 public int compare(long[] left, long[] right) { 166 int minLength = Math.min(left.length, right.length); 167 for (int i = 0; i < minLength; i++) { 168 if (left[i] != right[i]) { 169 return UnsignedLongs.compare(left[i], right[i]); 170 } 171 } 172 return left.length - right.length; 173 } 174 175 @Override 176 public String toString() { 177 return "UnsignedLongs.lexicographicalComparator()"; 178 } 179 } 180 181 /** 182 * Sorts the array, treating its elements as unsigned 64-bit integers. 183 * 184 * @since 23.1 185 */ 186 public static void sort(long[] array) { 187 checkNotNull(array); 188 sort(array, 0, array.length); 189 } 190 191 /** 192 * Sorts the array between {@code fromIndex} inclusive and {@code toIndex} exclusive, treating its 193 * elements as unsigned 64-bit integers. 194 * 195 * @since 23.1 196 */ 197 public static void sort(long[] array, int fromIndex, int toIndex) { 198 checkNotNull(array); 199 checkPositionIndexes(fromIndex, toIndex, array.length); 200 for (int i = fromIndex; i < toIndex; i++) { 201 array[i] = flip(array[i]); 202 } 203 Arrays.sort(array, fromIndex, toIndex); 204 for (int i = fromIndex; i < toIndex; i++) { 205 array[i] = flip(array[i]); 206 } 207 } 208 209 /** 210 * Sorts the elements of {@code array} in descending order, interpreting them as unsigned 64-bit 211 * integers. 212 * 213 * @since 23.1 214 */ 215 public static void sortDescending(long[] array) { 216 checkNotNull(array); 217 sortDescending(array, 0, array.length); 218 } 219 220 /** 221 * Sorts the elements of {@code array} between {@code fromIndex} inclusive and {@code toIndex} 222 * exclusive in descending order, interpreting them as unsigned 64-bit integers. 223 * 224 * @since 23.1 225 */ 226 public static void sortDescending(long[] array, int fromIndex, int toIndex) { 227 checkNotNull(array); 228 checkPositionIndexes(fromIndex, toIndex, array.length); 229 for (int i = fromIndex; i < toIndex; i++) { 230 array[i] ^= Long.MAX_VALUE; 231 } 232 Arrays.sort(array, fromIndex, toIndex); 233 for (int i = fromIndex; i < toIndex; i++) { 234 array[i] ^= Long.MAX_VALUE; 235 } 236 } 237 238 /** 239 * Returns dividend / divisor, where the dividend and divisor are treated as unsigned 64-bit 240 * quantities. 241 * 242 * <p><b>Java 8 users:</b> use {@link Long#divideUnsigned(long, long)} instead. 243 * 244 * @param dividend the dividend (numerator) 245 * @param divisor the divisor (denominator) 246 * @throws ArithmeticException if divisor is 0 247 */ 248 public static long divide(long dividend, long divisor) { 249 if (divisor < 0) { // i.e., divisor >= 2^63: 250 if (compare(dividend, divisor) < 0) { 251 return 0; // dividend < divisor 252 } else { 253 return 1; // dividend >= divisor 254 } 255 } 256 257 // Optimization - use signed division if dividend < 2^63 258 if (dividend >= 0) { 259 return dividend / divisor; 260 } 261 262 /* 263 * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is 264 * guaranteed to be either exact or one less than the correct value. This follows from fact that 265 * floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not quite 266 * trivial. 267 */ 268 long quotient = ((dividend >>> 1) / divisor) << 1; 269 long rem = dividend - quotient * divisor; 270 return quotient + (compare(rem, divisor) >= 0 ? 1 : 0); 271 } 272 273 /** 274 * Returns dividend % divisor, where the dividend and divisor are treated as unsigned 64-bit 275 * quantities. 276 * 277 * <p><b>Java 8 users:</b> use {@link Long#remainderUnsigned(long, long)} instead. 278 * 279 * @param dividend the dividend (numerator) 280 * @param divisor the divisor (denominator) 281 * @throws ArithmeticException if divisor is 0 282 * @since 11.0 283 */ 284 public static long remainder(long dividend, long divisor) { 285 if (divisor < 0) { // i.e., divisor >= 2^63: 286 if (compare(dividend, divisor) < 0) { 287 return dividend; // dividend < divisor 288 } else { 289 return dividend - divisor; // dividend >= divisor 290 } 291 } 292 293 // Optimization - use signed modulus if dividend < 2^63 294 if (dividend >= 0) { 295 return dividend % divisor; 296 } 297 298 /* 299 * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is 300 * guaranteed to be either exact or one less than the correct value. This follows from the fact 301 * that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not 302 * quite trivial. 303 */ 304 long quotient = ((dividend >>> 1) / divisor) << 1; 305 long rem = dividend - quotient * divisor; 306 return rem - (compare(rem, divisor) >= 0 ? divisor : 0); 307 } 308 309 /** 310 * Returns the unsigned {@code long} value represented by the given decimal string. 311 * 312 * <p><b>Java 8 users:</b> use {@link Long#parseUnsignedLong(String)} instead. 313 * 314 * @throws NumberFormatException if the string does not contain a valid unsigned {@code long} 315 * value 316 * @throws NullPointerException if {@code string} is null (in contrast to {@link 317 * Long#parseLong(String)}) 318 */ 319 @CanIgnoreReturnValue 320 public static long parseUnsignedLong(String string) { 321 return parseUnsignedLong(string, 10); 322 } 323 324 /** 325 * Returns the unsigned {@code long} value represented by a string with the given radix. 326 * 327 * <p><b>Java 8 users:</b> use {@link Long#parseUnsignedLong(String, int)} instead. 328 * 329 * @param string the string containing the unsigned {@code long} representation to be parsed. 330 * @param radix the radix to use while parsing {@code string} 331 * @throws NumberFormatException if the string does not contain a valid unsigned {@code long} with 332 * the given radix, or if {@code radix} is not between {@link Character#MIN_RADIX} and {@link 333 * Character#MAX_RADIX}. 334 * @throws NullPointerException if {@code string} is null (in contrast to {@link 335 * Long#parseLong(String)}) 336 */ 337 @CanIgnoreReturnValue 338 public static long parseUnsignedLong(String string, int radix) { 339 checkNotNull(string); 340 if (string.length() == 0) { 341 throw new NumberFormatException("empty string"); 342 } 343 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { 344 throw new NumberFormatException("illegal radix: " + radix); 345 } 346 347 int maxSafePos = ParseOverflowDetection.maxSafeDigits[radix] - 1; 348 long value = 0; 349 for (int pos = 0; pos < string.length(); pos++) { 350 int digit = Character.digit(string.charAt(pos), radix); 351 if (digit == -1) { 352 throw new NumberFormatException(string); 353 } 354 if (pos > maxSafePos && ParseOverflowDetection.overflowInParse(value, digit, radix)) { 355 throw new NumberFormatException("Too large for unsigned long: " + string); 356 } 357 value = (value * radix) + digit; 358 } 359 360 return value; 361 } 362 363 /** 364 * Returns the unsigned {@code long} value represented by the given string. 365 * 366 * <p>Accepts a decimal, hexadecimal, or octal number given by specifying the following prefix: 367 * 368 * <ul> 369 * <li>{@code 0x}<i>HexDigits</i> 370 * <li>{@code 0X}<i>HexDigits</i> 371 * <li>{@code #}<i>HexDigits</i> 372 * <li>{@code 0}<i>OctalDigits</i> 373 * </ul> 374 * 375 * @throws NumberFormatException if the string does not contain a valid unsigned {@code long} 376 * value 377 * @since 13.0 378 */ 379 @CanIgnoreReturnValue 380 public static long decode(String stringValue) { 381 ParseRequest request = ParseRequest.fromString(stringValue); 382 383 try { 384 return parseUnsignedLong(request.rawValue, request.radix); 385 } catch (NumberFormatException e) { 386 NumberFormatException decodeException = 387 new NumberFormatException("Error parsing value: " + stringValue); 388 decodeException.initCause(e); 389 throw decodeException; 390 } 391 } 392 393 /* 394 * We move the static constants into this class so ProGuard can inline UnsignedLongs entirely 395 * unless the user is actually calling a parse method. 396 */ 397 private static final class ParseOverflowDetection { 398 private ParseOverflowDetection() {} 399 400 // calculated as 0xffffffffffffffff / radix 401 static final long[] maxValueDivs = new long[Character.MAX_RADIX + 1]; 402 static final int[] maxValueMods = new int[Character.MAX_RADIX + 1]; 403 static final int[] maxSafeDigits = new int[Character.MAX_RADIX + 1]; 404 405 static { 406 BigInteger overflow = new BigInteger("10000000000000000", 16); 407 for (int i = Character.MIN_RADIX; i <= Character.MAX_RADIX; i++) { 408 maxValueDivs[i] = divide(MAX_VALUE, i); 409 maxValueMods[i] = (int) remainder(MAX_VALUE, i); 410 maxSafeDigits[i] = overflow.toString(i).length() - 1; 411 } 412 } 413 414 /** 415 * Returns true if (current * radix) + digit is a number too large to be represented by an 416 * unsigned long. This is useful for detecting overflow while parsing a string representation of 417 * a number. Does not verify whether supplied radix is valid, passing an invalid radix will give 418 * undefined results or an ArrayIndexOutOfBoundsException. 419 */ 420 static boolean overflowInParse(long current, int digit, int radix) { 421 if (current >= 0) { 422 if (current < maxValueDivs[radix]) { 423 return false; 424 } 425 if (current > maxValueDivs[radix]) { 426 return true; 427 } 428 // current == maxValueDivs[radix] 429 return (digit > maxValueMods[radix]); 430 } 431 432 // current < 0: high bit is set 433 return true; 434 } 435 } 436 437 /** 438 * Returns a string representation of x, where x is treated as unsigned. 439 * 440 * <p><b>Java 8 users:</b> use {@link Long#toUnsignedString(long)} instead. 441 */ 442 public static String toString(long x) { 443 return toString(x, 10); 444 } 445 446 /** 447 * Returns a string representation of {@code x} for the given radix, where {@code x} is treated as 448 * unsigned. 449 * 450 * <p><b>Java 8 users:</b> use {@link Long#toUnsignedString(long, int)} instead. 451 * 452 * @param x the value to convert to a string. 453 * @param radix the radix to use while working with {@code x} 454 * @throws IllegalArgumentException if {@code radix} is not between {@link Character#MIN_RADIX} 455 * and {@link Character#MAX_RADIX}. 456 */ 457 public static String toString(long x, int radix) { 458 checkArgument( 459 radix >= Character.MIN_RADIX && radix <= Character.MAX_RADIX, 460 "radix (%s) must be between Character.MIN_RADIX and Character.MAX_RADIX", 461 radix); 462 if (x == 0) { 463 // Simply return "0" 464 return "0"; 465 } else if (x > 0) { 466 return Long.toString(x, radix); 467 } else { 468 char[] buf = new char[64]; 469 int i = buf.length; 470 if ((radix & (radix - 1)) == 0) { 471 // Radix is a power of two so we can avoid division. 472 int shift = Integer.numberOfTrailingZeros(radix); 473 int mask = radix - 1; 474 do { 475 buf[--i] = Character.forDigit(((int) x) & mask, radix); 476 x >>>= shift; 477 } while (x != 0); 478 } else { 479 // Separate off the last digit using unsigned division. That will leave 480 // a number that is nonnegative as a signed integer. 481 long quotient; 482 if ((radix & 1) == 0) { 483 // Fast path for the usual case where the radix is even. 484 quotient = (x >>> 1) / (radix >>> 1); 485 } else { 486 quotient = divide(x, radix); 487 } 488 long rem = x - quotient * radix; 489 buf[--i] = Character.forDigit((int) rem, radix); 490 x = quotient; 491 // Simple modulo/division approach 492 while (x > 0) { 493 buf[--i] = Character.forDigit((int) (x % radix), radix); 494 x /= radix; 495 } 496 } 497 // Generate string 498 return new String(buf, i, buf.length - i); 499 } 500 } 501}