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