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.GwtCompatible; 022import com.google.errorprone.annotations.CanIgnoreReturnValue; 023import java.util.Arrays; 024import java.util.Comparator; 025 026/** 027 * Static utility methods pertaining to {@code int} primitives that interpret values as 028 * <i>unsigned</i> (that is, any negative value {@code x} is treated as the positive value {@code 029 * 2^32 + x}). The methods for which signedness is not an issue are in {@link Ints}, as well as 030 * signed versions of methods for which signedness is an issue. 031 * 032 * <p>In addition, this class provides several static methods for converting an {@code int} to a 033 * {@code String} and a {@code String} to an {@code int} that treat the {@code int} as an unsigned 034 * number. 035 * 036 * <p>Users of these utilities must be <i>extremely careful</i> not to mix up signed and unsigned 037 * {@code int} values. When possible, it is recommended that the {@link UnsignedInteger} wrapper 038 * class be used, at a small efficiency penalty, to enforce the distinction in the type system. 039 * 040 * <p>See the Guava User Guide article on <a 041 * href="https://github.com/google/guava/wiki/PrimitivesExplained#unsigned-support">unsigned 042 * primitive utilities</a>. 043 * 044 * @author Louis Wasserman 045 * @since 11.0 046 */ 047@GwtCompatible 048@ElementTypesAreNonnullByDefault 049public final class UnsignedInts { 050 static final long INT_MASK = 0xffffffffL; 051 052 private UnsignedInts() {} 053 054 static int flip(int value) { 055 return value ^ Integer.MIN_VALUE; 056 } 057 058 /** 059 * Compares the two specified {@code int} values, treating them as unsigned values between {@code 060 * 0} and {@code 2^32 - 1} inclusive. 061 * 062 * <p><b>Java 8+ users:</b> use {@link Integer#compareUnsigned(int, int)} instead. 063 * 064 * @param a the first unsigned {@code int} to compare 065 * @param b the second unsigned {@code int} to compare 066 * @return a negative value if {@code a} is less than {@code b}; a positive value if {@code a} is 067 * greater than {@code b}; or zero if they are equal 068 */ 069 public static int compare(int a, int b) { 070 return Ints.compare(flip(a), flip(b)); 071 } 072 073 /** 074 * Returns the value of the given {@code int} as a {@code long}, when treated as unsigned. 075 * 076 * <p><b>Java 8+ users:</b> use {@link Integer#toUnsignedLong(int)} instead. 077 */ 078 public static long toLong(int value) { 079 return value & INT_MASK; 080 } 081 082 /** 083 * Returns the {@code int} value that, when treated as unsigned, is equal to {@code value}, if 084 * possible. 085 * 086 * @param value a value between 0 and 2<sup>32</sup>-1 inclusive 087 * @return the {@code int} value that, when treated as unsigned, equals {@code value} 088 * @throws IllegalArgumentException if {@code value} is negative or greater than or equal to 089 * 2<sup>32</sup> 090 * @since 21.0 091 */ 092 public static int checkedCast(long value) { 093 checkArgument((value >> Integer.SIZE) == 0, "out of range: %s", value); 094 return (int) value; 095 } 096 097 /** 098 * Returns the {@code int} value that, when treated as unsigned, is nearest in value to {@code 099 * value}. 100 * 101 * @param value any {@code long} value 102 * @return {@code 2^32 - 1} if {@code value >= 2^32}, {@code 0} if {@code value <= 0}, and {@code 103 * value} cast to {@code int} otherwise 104 * @since 21.0 105 */ 106 public static int saturatedCast(long value) { 107 if (value <= 0) { 108 return 0; 109 } else if (value >= (1L << 32)) { 110 return -1; 111 } else { 112 return (int) value; 113 } 114 } 115 116 /** 117 * Returns the least value present in {@code array}, treating values as unsigned. 118 * 119 * @param array a <i>nonempty</i> array of unsigned {@code int} values 120 * @return the value present in {@code array} that is less than or equal to every other value in 121 * the array according to {@link #compare} 122 * @throws IllegalArgumentException if {@code array} is empty 123 */ 124 public static int min(int... array) { 125 checkArgument(array.length > 0); 126 int min = flip(array[0]); 127 for (int i = 1; i < array.length; i++) { 128 int next = flip(array[i]); 129 if (next < min) { 130 min = next; 131 } 132 } 133 return flip(min); 134 } 135 136 /** 137 * Returns the greatest value present in {@code array}, treating values as unsigned. 138 * 139 * @param array a <i>nonempty</i> array of unsigned {@code int} values 140 * @return the value present in {@code array} that is greater than or equal to every other value 141 * in the array according to {@link #compare} 142 * @throws IllegalArgumentException if {@code array} is empty 143 */ 144 public static int max(int... array) { 145 checkArgument(array.length > 0); 146 int max = flip(array[0]); 147 for (int i = 1; i < array.length; i++) { 148 int next = flip(array[i]); 149 if (next > max) { 150 max = next; 151 } 152 } 153 return flip(max); 154 } 155 156 /** 157 * Returns a string containing the supplied unsigned {@code int} values separated by {@code 158 * separator}. For example, {@code join("-", 1, 2, 3)} returns the string {@code "1-2-3"}. 159 * 160 * @param separator the text that should appear between consecutive values in the resulting string 161 * (but not at the start or end) 162 * @param array an array of unsigned {@code int} values, possibly empty 163 */ 164 public static String join(String separator, int... array) { 165 checkNotNull(separator); 166 if (array.length == 0) { 167 return ""; 168 } 169 170 // For pre-sizing a builder, just get the right order of magnitude 171 StringBuilder builder = new StringBuilder(array.length * 5); 172 builder.append(toString(array[0])); 173 for (int i = 1; i < array.length; i++) { 174 builder.append(separator).append(toString(array[i])); 175 } 176 return builder.toString(); 177 } 178 179 /** 180 * Returns a comparator that compares two arrays of unsigned {@code int} values <a 181 * href="http://en.wikipedia.org/wiki/Lexicographical_order">lexicographically</a>. That is, it 182 * compares, using {@link #compare(int, int)}), the first pair of values that follow any common 183 * prefix, or when one array is a prefix of the other, treats the shorter array as the lesser. For 184 * example, {@code [] < [1] < [1, 2] < [2] < [1 << 31]}. 185 * 186 * <p>The returned comparator is inconsistent with {@link Object#equals(Object)} (since arrays 187 * support only identity equality), but it is consistent with {@link Arrays#equals(int[], int[])}. 188 */ 189 public static Comparator<int[]> lexicographicalComparator() { 190 return LexicographicalComparator.INSTANCE; 191 } 192 193 enum LexicographicalComparator implements Comparator<int[]> { 194 INSTANCE; 195 196 @Override 197 public int compare(int[] left, int[] right) { 198 int minLength = Math.min(left.length, right.length); 199 for (int i = 0; i < minLength; i++) { 200 if (left[i] != right[i]) { 201 return UnsignedInts.compare(left[i], right[i]); 202 } 203 } 204 return left.length - right.length; 205 } 206 207 @Override 208 public String toString() { 209 return "UnsignedInts.lexicographicalComparator()"; 210 } 211 } 212 213 /** 214 * Sorts the array, treating its elements as unsigned 32-bit integers. 215 * 216 * @since 23.1 217 */ 218 public static void sort(int[] array) { 219 checkNotNull(array); 220 sort(array, 0, array.length); 221 } 222 223 /** 224 * Sorts the array between {@code fromIndex} inclusive and {@code toIndex} exclusive, treating its 225 * elements as unsigned 32-bit integers. 226 * 227 * @since 23.1 228 */ 229 public static void sort(int[] array, int fromIndex, int toIndex) { 230 checkNotNull(array); 231 checkPositionIndexes(fromIndex, toIndex, array.length); 232 for (int i = fromIndex; i < toIndex; i++) { 233 array[i] = flip(array[i]); 234 } 235 Arrays.sort(array, fromIndex, toIndex); 236 for (int i = fromIndex; i < toIndex; i++) { 237 array[i] = flip(array[i]); 238 } 239 } 240 241 /** 242 * Sorts the elements of {@code array} in descending order, interpreting them as unsigned 32-bit 243 * integers. 244 * 245 * @since 23.1 246 */ 247 public static void sortDescending(int[] array) { 248 checkNotNull(array); 249 sortDescending(array, 0, array.length); 250 } 251 252 /** 253 * Sorts the elements of {@code array} between {@code fromIndex} inclusive and {@code toIndex} 254 * exclusive in descending order, interpreting them as unsigned 32-bit integers. 255 * 256 * @since 23.1 257 */ 258 public static void sortDescending(int[] array, int fromIndex, int toIndex) { 259 checkNotNull(array); 260 checkPositionIndexes(fromIndex, toIndex, array.length); 261 for (int i = fromIndex; i < toIndex; i++) { 262 array[i] ^= Integer.MAX_VALUE; 263 } 264 Arrays.sort(array, fromIndex, toIndex); 265 for (int i = fromIndex; i < toIndex; i++) { 266 array[i] ^= Integer.MAX_VALUE; 267 } 268 } 269 270 /** 271 * Returns dividend / divisor, where the dividend and divisor are treated as unsigned 32-bit 272 * quantities. 273 * 274 * <p><b>Java 8+ users:</b> use {@link Integer#divideUnsigned(int, int)} instead. 275 * 276 * @param dividend the dividend (numerator) 277 * @param divisor the divisor (denominator) 278 * @throws ArithmeticException if divisor is 0 279 */ 280 public static int divide(int dividend, int divisor) { 281 return (int) (toLong(dividend) / toLong(divisor)); 282 } 283 284 /** 285 * Returns dividend % divisor, where the dividend and divisor are treated as unsigned 32-bit 286 * quantities. 287 * 288 * <p><b>Java 8+ users:</b> use {@link Integer#remainderUnsigned(int, int)} instead. 289 * 290 * @param dividend the dividend (numerator) 291 * @param divisor the divisor (denominator) 292 * @throws ArithmeticException if divisor is 0 293 */ 294 public static int remainder(int dividend, int divisor) { 295 return (int) (toLong(dividend) % toLong(divisor)); 296 } 297 298 /** 299 * Returns the unsigned {@code int} value represented by the given string. 300 * 301 * <p>Accepts a decimal, hexadecimal, or octal number given by specifying the following prefix: 302 * 303 * <ul> 304 * <li>{@code 0x}<i>HexDigits</i> 305 * <li>{@code 0X}<i>HexDigits</i> 306 * <li>{@code #}<i>HexDigits</i> 307 * <li>{@code 0}<i>OctalDigits</i> 308 * </ul> 309 * 310 * @throws NumberFormatException if the string does not contain a valid unsigned {@code int} value 311 * @since 13.0 312 */ 313 @CanIgnoreReturnValue 314 public static int decode(String stringValue) { 315 ParseRequest request = ParseRequest.fromString(stringValue); 316 317 try { 318 return parseUnsignedInt(request.rawValue, request.radix); 319 } catch (NumberFormatException e) { 320 NumberFormatException decodeException = 321 new NumberFormatException("Error parsing value: " + stringValue); 322 decodeException.initCause(e); 323 throw decodeException; 324 } 325 } 326 327 /** 328 * Returns the unsigned {@code int} value represented by the given decimal string. 329 * 330 * <p><b>Java 8+ users:</b> use {@link Integer#parseUnsignedInt(String)} instead. 331 * 332 * @throws NumberFormatException if the string does not contain a valid unsigned {@code int} value 333 * @throws NullPointerException if {@code s} is null (in contrast to {@link 334 * Integer#parseInt(String)}) 335 */ 336 @CanIgnoreReturnValue 337 public static int parseUnsignedInt(String s) { 338 return parseUnsignedInt(s, 10); 339 } 340 341 /** 342 * Returns the unsigned {@code int} value represented by a string with the given radix. 343 * 344 * <p><b>Java 8+ users:</b> use {@link Integer#parseUnsignedInt(String, int)} instead. 345 * 346 * @param string the string containing the unsigned integer representation to be parsed. 347 * @param radix the radix to use while parsing {@code s}; must be between {@link 348 * Character#MIN_RADIX} and {@link Character#MAX_RADIX}. 349 * @throws NumberFormatException if the string does not contain a valid unsigned {@code int}, or 350 * if supplied radix is invalid. 351 * @throws NullPointerException if {@code s} is null (in contrast to {@link 352 * Integer#parseInt(String)}) 353 */ 354 @CanIgnoreReturnValue 355 public static int parseUnsignedInt(String string, int radix) { 356 checkNotNull(string); 357 long result = Long.parseLong(string, radix); 358 if ((result & INT_MASK) != result) { 359 throw new NumberFormatException( 360 "Input " + string + " in base " + radix + " is not in the range of an unsigned integer"); 361 } 362 return (int) result; 363 } 364 365 /** 366 * Returns a string representation of x, where x is treated as unsigned. 367 * 368 * <p><b>Java 8+ users:</b> use {@link Integer#toUnsignedString(int)} instead. 369 */ 370 public static String toString(int x) { 371 return toString(x, 10); 372 } 373 374 /** 375 * Returns a string representation of {@code x} for the given radix, where {@code x} is treated as 376 * unsigned. 377 * 378 * <p><b>Java 8+ users:</b> use {@link Integer#toUnsignedString(int, int)} instead. 379 * 380 * @param x the value to convert to a string. 381 * @param radix the radix to use while working with {@code x} 382 * @throws IllegalArgumentException if {@code radix} is not between {@link Character#MIN_RADIX} 383 * and {@link Character#MAX_RADIX}. 384 */ 385 public static String toString(int x, int radix) { 386 long asLong = x & INT_MASK; 387 return Long.toString(asLong, radix); 388 } 389}