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