1 /*
   2  * Copyright (c) 1994, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.lang;
  27 
  28 import java.lang.annotation.Native;
  29 import java.math.*;
  30 
  31 /**
  32  * The {@code Long} class wraps a value of the primitive type {@code
  33  * long} in an object. An object of type {@code Long} contains a
  34  * single field whose type is {@code long}.
  35  *
  36  * <p> In addition, this class provides several methods for converting
  37  * a {@code long} to a {@code String} and a {@code String} to a {@code
  38  * long}, as well as other constants and methods useful when dealing
  39  * with a {@code long}.
  40  *
  41  * <p>Implementation note: The implementations of the "bit twiddling"
  42  * methods (such as {@link #highestOneBit(long) highestOneBit} and
  43  * {@link #numberOfTrailingZeros(long) numberOfTrailingZeros}) are
  44  * based on material from Henry S. Warren, Jr.'s <i>Hacker's
  45  * Delight</i>, (Addison Wesley, 2002).
  46  *
  47  * @author  Lee Boynton
  48  * @author  Arthur van Hoff
  49  * @author  Josh Bloch
  50  * @author  Joseph D. Darcy
  51  * @since   JDK1.0
  52  */
  53 public final class Long extends Number implements Comparable<Long> {
  54     /**
  55      * A constant holding the minimum value a {@code long} can
  56      * have, -2<sup>63</sup>.
  57      */
  58     @Native public static final long MIN_VALUE = 0x8000000000000000L;
  59 
  60     /**
  61      * A constant holding the maximum value a {@code long} can
  62      * have, 2<sup>63</sup>-1.
  63      */
  64     @Native public static final long MAX_VALUE = 0x7fffffffffffffffL;
  65 
  66     /**
  67      * The {@code Class} instance representing the primitive type
  68      * {@code long}.
  69      *
  70      * @since   JDK1.1
  71      */
  72     @SuppressWarnings("unchecked")
  73     public static final Class<Long>     TYPE = (Class<Long>) Class.getPrimitiveClass("long");
  74 
  75     /**
  76      * Returns a string representation of the first argument in the
  77      * radix specified by the second argument.
  78      *
  79      * <p>If the radix is smaller than {@code Character.MIN_RADIX}
  80      * or larger than {@code Character.MAX_RADIX}, then the radix
  81      * {@code 10} is used instead.
  82      *
  83      * <p>If the first argument is negative, the first element of the
  84      * result is the ASCII minus sign {@code '-'}
  85      * ({@code '\u005Cu002d'}). If the first argument is not
  86      * negative, no sign character appears in the result.
  87      *
  88      * <p>The remaining characters of the result represent the magnitude
  89      * of the first argument. If the magnitude is zero, it is
  90      * represented by a single zero character {@code '0'}
  91      * ({@code '\u005Cu0030'}); otherwise, the first character of
  92      * the representation of the magnitude will not be the zero
  93      * character.  The following ASCII characters are used as digits:
  94      *
  95      * <blockquote>
  96      *   {@code 0123456789abcdefghijklmnopqrstuvwxyz}
  97      * </blockquote>
  98      *
  99      * These are {@code '\u005Cu0030'} through
 100      * {@code '\u005Cu0039'} and {@code '\u005Cu0061'} through
 101      * {@code '\u005Cu007a'}. If {@code radix} is
 102      * <var>N</var>, then the first <var>N</var> of these characters
 103      * are used as radix-<var>N</var> digits in the order shown. Thus,
 104      * the digits for hexadecimal (radix 16) are
 105      * {@code 0123456789abcdef}. If uppercase letters are
 106      * desired, the {@link java.lang.String#toUpperCase()} method may
 107      * be called on the result:
 108      *
 109      * <blockquote>
 110      *  {@code Long.toString(n, 16).toUpperCase()}
 111      * </blockquote>
 112      *
 113      * @param   i       a {@code long} to be converted to a string.
 114      * @param   radix   the radix to use in the string representation.
 115      * @return  a string representation of the argument in the specified radix.
 116      * @see     java.lang.Character#MAX_RADIX
 117      * @see     java.lang.Character#MIN_RADIX
 118      */
 119     public static String toString(long i, int radix) {
 120         if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
 121             radix = 10;
 122         if (radix == 10)
 123             return toString(i);
 124         char[] buf = new char[65];
 125         int charPos = 64;
 126         boolean negative = (i < 0);
 127 
 128         if (!negative) {
 129             i = -i;
 130         }
 131 
 132         while (i <= -radix) {
 133             buf[charPos--] = Integer.digits[(int)(-(i % radix))];
 134             i = i / radix;
 135         }
 136         buf[charPos] = Integer.digits[(int)(-i)];
 137 
 138         if (negative) {
 139             buf[--charPos] = '-';
 140         }
 141 
 142         return new String(buf, charPos, (65 - charPos));
 143     }
 144 
 145     /**
 146      * Returns a string representation of the first argument as an
 147      * unsigned integer value in the radix specified by the second
 148      * argument.
 149      *
 150      * <p>If the radix is smaller than {@code Character.MIN_RADIX}
 151      * or larger than {@code Character.MAX_RADIX}, then the radix
 152      * {@code 10} is used instead.
 153      *
 154      * <p>Note that since the first argument is treated as an unsigned
 155      * value, no leading sign character is printed.
 156      *
 157      * <p>If the magnitude is zero, it is represented by a single zero
 158      * character {@code '0'} ({@code '\u005Cu0030'}); otherwise,
 159      * the first character of the representation of the magnitude will
 160      * not be the zero character.
 161      *
 162      * <p>The behavior of radixes and the characters used as digits
 163      * are the same as {@link #toString(long, int) toString}.
 164      *
 165      * @param   i       an integer to be converted to an unsigned string.
 166      * @param   radix   the radix to use in the string representation.
 167      * @return  an unsigned string representation of the argument in the specified radix.
 168      * @see     #toString(long, int)
 169      * @since 1.8
 170      */
 171     public static String toUnsignedString(long i, int radix) {
 172         if (i >= 0)
 173             return toString(i, radix);
 174         else {
 175             switch (radix) {
 176             case 2:
 177                 return toBinaryString(i);
 178 
 179             case 4:
 180                 return toUnsignedString0(i, 2);
 181 
 182             case 8:
 183                 return toOctalString(i);
 184 
 185             case 10:
 186                 /*
 187                  * We can get the effect of an unsigned division by 10
 188                  * on a long value by first shifting right, yielding a
 189                  * positive value, and then dividing by 5.  This
 190                  * allows the last digit and preceding digits to be
 191                  * isolated more quickly than by an initial conversion
 192                  * to BigInteger.
 193                  */
 194                 long quot = (i >>> 1) / 5;
 195                 long rem = i - quot * 10;
 196                 return toString(quot) + rem;
 197 
 198             case 16:
 199                 return toHexString(i);
 200 
 201             case 32:
 202                 return toUnsignedString0(i, 5);
 203 
 204             default:
 205                 return toUnsignedBigInteger(i).toString(radix);
 206             }
 207         }
 208     }
 209 
 210     /**
 211      * Return a BigInteger equal to the unsigned value of the
 212      * argument.
 213      */
 214     private static BigInteger toUnsignedBigInteger(long i) {
 215         if (i >= 0L)
 216             return BigInteger.valueOf(i);
 217         else {
 218             int upper = (int) (i >>> 32);
 219             int lower = (int) i;
 220 
 221             // return (upper << 32) + lower
 222             return (BigInteger.valueOf(Integer.toUnsignedLong(upper))).shiftLeft(32).
 223                 add(BigInteger.valueOf(Integer.toUnsignedLong(lower)));
 224         }
 225     }
 226 
 227     /**
 228      * Returns a string representation of the {@code long}
 229      * argument as an unsigned integer in base&nbsp;16.
 230      *
 231      * <p>The unsigned {@code long} value is the argument plus
 232      * 2<sup>64</sup> if the argument is negative; otherwise, it is
 233      * equal to the argument.  This value is converted to a string of
 234      * ASCII digits in hexadecimal (base&nbsp;16) with no extra
 235      * leading {@code 0}s.
 236      *
 237      * <p>The value of the argument can be recovered from the returned
 238      * string {@code s} by calling {@link
 239      * Long#parseUnsignedLong(String, int) Long.parseUnsignedLong(s,
 240      * 16)}.
 241      *
 242      * <p>If the unsigned magnitude is zero, it is represented by a
 243      * single zero character {@code '0'} ({@code '\u005Cu0030'});
 244      * otherwise, the first character of the representation of the
 245      * unsigned magnitude will not be the zero character. The
 246      * following characters are used as hexadecimal digits:
 247      *
 248      * <blockquote>
 249      *  {@code 0123456789abcdef}
 250      * </blockquote>
 251      *
 252      * These are the characters {@code '\u005Cu0030'} through
 253      * {@code '\u005Cu0039'} and  {@code '\u005Cu0061'} through
 254      * {@code '\u005Cu0066'}.  If uppercase letters are desired,
 255      * the {@link java.lang.String#toUpperCase()} method may be called
 256      * on the result:
 257      *
 258      * <blockquote>
 259      *  {@code Long.toHexString(n).toUpperCase()}
 260      * </blockquote>
 261      *
 262      * @param   i   a {@code long} to be converted to a string.
 263      * @return  the string representation of the unsigned {@code long}
 264      *          value represented by the argument in hexadecimal
 265      *          (base&nbsp;16).
 266      * @see #parseUnsignedLong(String, int)
 267      * @see #toUnsignedString(long, int)
 268      * @since   JDK 1.0.2
 269      */
 270     public static String toHexString(long i) {
 271         return toUnsignedString0(i, 4);
 272     }
 273 
 274     /**
 275      * Returns a string representation of the {@code long}
 276      * argument as an unsigned integer in base&nbsp;8.
 277      *
 278      * <p>The unsigned {@code long} value is the argument plus
 279      * 2<sup>64</sup> if the argument is negative; otherwise, it is
 280      * equal to the argument.  This value is converted to a string of
 281      * ASCII digits in octal (base&nbsp;8) with no extra leading
 282      * {@code 0}s.
 283      *
 284      * <p>The value of the argument can be recovered from the returned
 285      * string {@code s} by calling {@link
 286      * Long#parseUnsignedLong(String, int) Long.parseUnsignedLong(s,
 287      * 8)}.
 288      *
 289      * <p>If the unsigned magnitude is zero, it is represented by a
 290      * single zero character {@code '0'} ({@code '\u005Cu0030'});
 291      * otherwise, the first character of the representation of the
 292      * unsigned magnitude will not be the zero character. The
 293      * following characters are used as octal digits:
 294      *
 295      * <blockquote>
 296      *  {@code 01234567}
 297      * </blockquote>
 298      *
 299      * These are the characters {@code '\u005Cu0030'} through
 300      * {@code '\u005Cu0037'}.
 301      *
 302      * @param   i   a {@code long} to be converted to a string.
 303      * @return  the string representation of the unsigned {@code long}
 304      *          value represented by the argument in octal (base&nbsp;8).
 305      * @see #parseUnsignedLong(String, int)
 306      * @see #toUnsignedString(long, int)
 307      * @since   JDK 1.0.2
 308      */
 309     public static String toOctalString(long i) {
 310         return toUnsignedString0(i, 3);
 311     }
 312 
 313     /**
 314      * Returns a string representation of the {@code long}
 315      * argument as an unsigned integer in base&nbsp;2.
 316      *
 317      * <p>The unsigned {@code long} value is the argument plus
 318      * 2<sup>64</sup> if the argument is negative; otherwise, it is
 319      * equal to the argument.  This value is converted to a string of
 320      * ASCII digits in binary (base&nbsp;2) with no extra leading
 321      * {@code 0}s.
 322      *
 323      * <p>The value of the argument can be recovered from the returned
 324      * string {@code s} by calling {@link
 325      * Long#parseUnsignedLong(String, int) Long.parseUnsignedLong(s,
 326      * 2)}.
 327      *
 328      * <p>If the unsigned magnitude is zero, it is represented by a
 329      * single zero character {@code '0'} ({@code '\u005Cu0030'});
 330      * otherwise, the first character of the representation of the
 331      * unsigned magnitude will not be the zero character. The
 332      * characters {@code '0'} ({@code '\u005Cu0030'}) and {@code
 333      * '1'} ({@code '\u005Cu0031'}) are used as binary digits.
 334      *
 335      * @param   i   a {@code long} to be converted to a string.
 336      * @return  the string representation of the unsigned {@code long}
 337      *          value represented by the argument in binary (base&nbsp;2).
 338      * @see #parseUnsignedLong(String, int)
 339      * @see #toUnsignedString(long, int)
 340      * @since   JDK 1.0.2
 341      */
 342     public static String toBinaryString(long i) {
 343         return toUnsignedString0(i, 1);
 344     }
 345 
 346     /**
 347      * Convert the integer to an unsigned number.
 348      */
 349     private static String toUnsignedString0(long i, int shift) {
 350         char[] buf = new char[64];
 351         int charPos = 64;
 352         int radix = 1 << shift;
 353         long mask = radix - 1;
 354         do {
 355             buf[--charPos] = Integer.digits[(int)(i & mask)];
 356             i >>>= shift;
 357         } while (i != 0);
 358         return new String(buf, charPos, (64 - charPos));
 359     }
 360 
 361     /**
 362      * Returns a {@code String} object representing the specified
 363      * {@code long}.  The argument is converted to signed decimal
 364      * representation and returned as a string, exactly as if the
 365      * argument and the radix 10 were given as arguments to the {@link
 366      * #toString(long, int)} method.
 367      *
 368      * @param   i   a {@code long} to be converted.
 369      * @return  a string representation of the argument in base&nbsp;10.
 370      */
 371     public static String toString(long i) {
 372         if (i == Long.MIN_VALUE)
 373             return "-9223372036854775808";
 374         int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
 375         char[] buf = new char[size];
 376         getChars(i, size, buf);
 377         return new String(buf, true);
 378     }
 379 
 380     /**
 381      * Returns a string representation of the argument as an unsigned
 382      * decimal value.
 383      *
 384      * The argument is converted to unsigned decimal representation
 385      * and returned as a string exactly as if the argument and radix
 386      * 10 were given as arguments to the {@link #toUnsignedString(long,
 387      * int)} method.
 388      *
 389      * @param   i  an integer to be converted to an unsigned string.
 390      * @return  an unsigned string representation of the argument.
 391      * @see     #toUnsignedString(long, int)
 392      * @since 1.8
 393      */
 394     public static String toUnsignedString(long i) {
 395         return toUnsignedString(i, 10);
 396     }
 397 
 398     /**
 399      * Places characters representing the integer i into the
 400      * character array buf. The characters are placed into
 401      * the buffer backwards starting with the least significant
 402      * digit at the specified index (exclusive), and working
 403      * backwards from there.
 404      *
 405      * Will fail if i == Long.MIN_VALUE
 406      */
 407     static void getChars(long i, int index, char[] buf) {
 408         long q;
 409         int r;
 410         int charPos = index;
 411         char sign = 0;
 412 
 413         if (i < 0) {
 414             sign = '-';
 415             i = -i;
 416         }
 417 
 418         // Get 2 digits/iteration using longs until quotient fits into an int
 419         while (i > Integer.MAX_VALUE) {
 420             q = i / 100;
 421             // really: r = i - (q * 100);
 422             r = (int)(i - ((q << 6) + (q << 5) + (q << 2)));
 423             i = q;
 424             buf[--charPos] = Integer.DigitOnes[r];
 425             buf[--charPos] = Integer.DigitTens[r];
 426         }
 427 
 428         // Get 2 digits/iteration using ints
 429         int q2;
 430         int i2 = (int)i;
 431         while (i2 >= 65536) {
 432             q2 = i2 / 100;
 433             // really: r = i2 - (q * 100);
 434             r = i2 - ((q2 << 6) + (q2 << 5) + (q2 << 2));
 435             i2 = q2;
 436             buf[--charPos] = Integer.DigitOnes[r];
 437             buf[--charPos] = Integer.DigitTens[r];
 438         }
 439 
 440         // Fall thru to fast mode for smaller numbers
 441         // assert(i2 <= 65536, i2);
 442         for (;;) {
 443             q2 = (i2 * 52429) >>> (16+3);
 444             r = i2 - ((q2 << 3) + (q2 << 1));  // r = i2-(q2*10) ...
 445             buf[--charPos] = Integer.digits[r];
 446             i2 = q2;
 447             if (i2 == 0) break;
 448         }
 449         if (sign != 0) {
 450             buf[--charPos] = sign;
 451         }
 452     }
 453 
 454     // Requires positive x
 455     static int stringSize(long x) {
 456         long p = 10;
 457         for (int i=1; i<19; i++) {
 458             if (x < p)
 459                 return i;
 460             p = 10*p;
 461         }
 462         return 19;
 463     }
 464 
 465     /**
 466      * Parses the string argument as a signed {@code long} in the
 467      * radix specified by the second argument. The characters in the
 468      * string must all be digits of the specified radix (as determined
 469      * by whether {@link java.lang.Character#digit(char, int)} returns
 470      * a nonnegative value), except that the first character may be an
 471      * ASCII minus sign {@code '-'} ({@code '\u005Cu002D'}) to
 472      * indicate a negative value or an ASCII plus sign {@code '+'}
 473      * ({@code '\u005Cu002B'}) to indicate a positive value. The
 474      * resulting {@code long} value is returned.
 475      *
 476      * <p>Note that neither the character {@code L}
 477      * ({@code '\u005Cu004C'}) nor {@code l}
 478      * ({@code '\u005Cu006C'}) is permitted to appear at the end
 479      * of the string as a type indicator, as would be permitted in
 480      * Java programming language source code - except that either
 481      * {@code L} or {@code l} may appear as a digit for a
 482      * radix greater than 22.
 483      *
 484      * <p>An exception of type {@code NumberFormatException} is
 485      * thrown if any of the following situations occurs:
 486      * <ul>
 487      *
 488      * <li>The first argument is {@code null} or is a string of
 489      * length zero.
 490      *
 491      * <li>The {@code radix} is either smaller than {@link
 492      * java.lang.Character#MIN_RADIX} or larger than {@link
 493      * java.lang.Character#MAX_RADIX}.
 494      *
 495      * <li>Any character of the string is not a digit of the specified
 496      * radix, except that the first character may be a minus sign
 497      * {@code '-'} ({@code '\u005Cu002d'}) or plus sign {@code
 498      * '+'} ({@code '\u005Cu002B'}) provided that the string is
 499      * longer than length 1.
 500      *
 501      * <li>The value represented by the string is not a value of type
 502      *      {@code long}.
 503      * </ul>
 504      *
 505      * <p>Examples:
 506      * <blockquote><pre>
 507      * parseLong("0", 10) returns 0L
 508      * parseLong("473", 10) returns 473L
 509      * parseLong("+42", 10) returns 42L
 510      * parseLong("-0", 10) returns 0L
 511      * parseLong("-FF", 16) returns -255L
 512      * parseLong("1100110", 2) returns 102L
 513      * parseLong("99", 8) throws a NumberFormatException
 514      * parseLong("Hazelnut", 10) throws a NumberFormatException
 515      * parseLong("Hazelnut", 36) returns 1356099454469L
 516      * </pre></blockquote>
 517      *
 518      * @param      s       the {@code String} containing the
 519      *                     {@code long} representation to be parsed.
 520      * @param      radix   the radix to be used while parsing {@code s}.
 521      * @return     the {@code long} represented by the string argument in
 522      *             the specified radix.
 523      * @throws     NumberFormatException  if the string does not contain a
 524      *             parsable {@code long}.
 525      */
 526     public static long parseLong(String s, int radix)
 527               throws NumberFormatException
 528     {
 529         if (s == null) {
 530             throw new NumberFormatException("null");
 531         }
 532 
 533         if (radix < Character.MIN_RADIX) {
 534             throw new NumberFormatException("radix " + radix +
 535                                             " less than Character.MIN_RADIX");
 536         }
 537         if (radix > Character.MAX_RADIX) {
 538             throw new NumberFormatException("radix " + radix +
 539                                             " greater than Character.MAX_RADIX");
 540         }
 541 
 542         long result = 0;
 543         boolean negative = false;
 544         int i = 0, len = s.length();
 545         long limit = -Long.MAX_VALUE;
 546         long multmin;
 547         int digit;
 548 
 549         if (len > 0) {
 550             char firstChar = s.charAt(0);
 551             if (firstChar < '0') { // Possible leading "+" or "-"
 552                 if (firstChar == '-') {
 553                     negative = true;
 554                     limit = Long.MIN_VALUE;
 555                 } else if (firstChar != '+')
 556                     throw NumberFormatException.forInputString(s);
 557 
 558                 if (len == 1) // Cannot have lone "+" or "-"
 559                     throw NumberFormatException.forInputString(s);
 560                 i++;
 561             }
 562             multmin = limit / radix;
 563             while (i < len) {
 564                 // Accumulating negatively avoids surprises near MAX_VALUE
 565                 digit = Character.digit(s.charAt(i++),radix);
 566                 if (digit < 0) {
 567                     throw NumberFormatException.forInputString(s);
 568                 }
 569                 if (result < multmin) {
 570                     throw NumberFormatException.forInputString(s);
 571                 }
 572                 result *= radix;
 573                 if (result < limit + digit) {
 574                     throw NumberFormatException.forInputString(s);
 575                 }
 576                 result -= digit;
 577             }
 578         } else {
 579             throw NumberFormatException.forInputString(s);
 580         }
 581         return negative ? result : -result;
 582     }
 583 
 584     /**
 585      * Parses the string argument as a signed decimal {@code long}.
 586      * The characters in the string must all be decimal digits, except
 587      * that the first character may be an ASCII minus sign {@code '-'}
 588      * ({@code \u005Cu002D'}) to indicate a negative value or an
 589      * ASCII plus sign {@code '+'} ({@code '\u005Cu002B'}) to
 590      * indicate a positive value. The resulting {@code long} value is
 591      * returned, exactly as if the argument and the radix {@code 10}
 592      * were given as arguments to the {@link
 593      * #parseLong(java.lang.String, int)} method.
 594      *
 595      * <p>Note that neither the character {@code L}
 596      * ({@code '\u005Cu004C'}) nor {@code l}
 597      * ({@code '\u005Cu006C'}) is permitted to appear at the end
 598      * of the string as a type indicator, as would be permitted in
 599      * Java programming language source code.
 600      *
 601      * @param      s   a {@code String} containing the {@code long}
 602      *             representation to be parsed
 603      * @return     the {@code long} represented by the argument in
 604      *             decimal.
 605      * @throws     NumberFormatException  if the string does not contain a
 606      *             parsable {@code long}.
 607      */
 608     public static long parseLong(String s) throws NumberFormatException {
 609         return parseLong(s, 10);
 610     }
 611 
 612     /**
 613      * Parses the string argument as an unsigned {@code long} in the
 614      * radix specified by the second argument.  An unsigned integer
 615      * maps the values usually associated with negative numbers to
 616      * positive numbers larger than {@code MAX_VALUE}.
 617      *
 618      * The characters in the string must all be digits of the
 619      * specified radix (as determined by whether {@link
 620      * java.lang.Character#digit(char, int)} returns a nonnegative
 621      * value), except that the first character may be an ASCII plus
 622      * sign {@code '+'} ({@code '\u005Cu002B'}). The resulting
 623      * integer value is returned.
 624      *
 625      * <p>An exception of type {@code NumberFormatException} is
 626      * thrown if any of the following situations occurs:
 627      * <ul>
 628      * <li>The first argument is {@code null} or is a string of
 629      * length zero.
 630      *
 631      * <li>The radix is either smaller than
 632      * {@link java.lang.Character#MIN_RADIX} or
 633      * larger than {@link java.lang.Character#MAX_RADIX}.
 634      *
 635      * <li>Any character of the string is not a digit of the specified
 636      * radix, except that the first character may be a plus sign
 637      * {@code '+'} ({@code '\u005Cu002B'}) provided that the
 638      * string is longer than length 1.
 639      *
 640      * <li>The value represented by the string is larger than the
 641      * largest unsigned {@code long}, 2<sup>64</sup>-1.
 642      *
 643      * </ul>
 644      *
 645      *
 646      * @param      s   the {@code String} containing the unsigned integer
 647      *                  representation to be parsed
 648      * @param      radix   the radix to be used while parsing {@code s}.
 649      * @return     the unsigned {@code long} represented by the string
 650      *             argument in the specified radix.
 651      * @throws     NumberFormatException if the {@code String}
 652      *             does not contain a parsable {@code long}.
 653      * @since 1.8
 654      */
 655     public static long parseUnsignedLong(String s, int radix)
 656                 throws NumberFormatException {
 657         if (s == null)  {
 658             throw new NumberFormatException("null");
 659         }
 660 
 661         int len = s.length();
 662         if (len > 0) {
 663             char firstChar = s.charAt(0);
 664             if (firstChar == '-') {
 665                 throw new
 666                     NumberFormatException(String.format("Illegal leading minus sign " +
 667                                                        "on unsigned string %s.", s));
 668             } else {
 669                 if (len <= 12 || // Long.MAX_VALUE in Character.MAX_RADIX is 13 digits
 670                     (radix == 10 && len <= 18) ) { // Long.MAX_VALUE in base 10 is 19 digits
 671                     return parseLong(s, radix);
 672                 }
 673 
 674                 // No need for range checks on len due to testing above.
 675                 long first = parseLong(s.substring(0, len - 1), radix);
 676                 int second = Character.digit(s.charAt(len - 1), radix);
 677                 if (second < 0) {
 678                     throw new NumberFormatException("Bad digit at end of " + s);
 679                 }
 680                 long result = first * radix + second;
 681                 if (compareUnsigned(result, first) < 0) {
 682                     /*
 683                      * The maximum unsigned value, (2^64)-1, takes at
 684                      * most one more digit to represent than the
 685                      * maximum signed value, (2^63)-1.  Therefore,
 686                      * parsing (len - 1) digits will be appropriately
 687                      * in-range of the signed parsing.  In other
 688                      * words, if parsing (len -1) digits overflows
 689                      * signed parsing, parsing len digits will
 690                      * certainly overflow unsigned parsing.
 691                      *
 692                      * The compareUnsigned check above catches
 693                      * situations where an unsigned overflow occurs
 694                      * incorporating the contribution of the final
 695                      * digit.
 696                      */
 697                     throw new NumberFormatException(String.format("String value %s exceeds " +
 698                                                                   "range of unsigned long.", s));
 699                 }
 700                 return result;
 701             }
 702         } else {
 703             throw NumberFormatException.forInputString(s);
 704         }
 705     }
 706 
 707     /**
 708      * Parses the string argument as an unsigned decimal {@code long}. The
 709      * characters in the string must all be decimal digits, except
 710      * that the first character may be an an ASCII plus sign {@code
 711      * '+'} ({@code '\u005Cu002B'}). The resulting integer value
 712      * is returned, exactly as if the argument and the radix 10 were
 713      * given as arguments to the {@link
 714      * #parseUnsignedLong(java.lang.String, int)} method.
 715      *
 716      * @param s   a {@code String} containing the unsigned {@code long}
 717      *            representation to be parsed
 718      * @return    the unsigned {@code long} value represented by the decimal string argument
 719      * @throws    NumberFormatException  if the string does not contain a
 720      *            parsable unsigned integer.
 721      * @since 1.8
 722      */
 723     public static long parseUnsignedLong(String s) throws NumberFormatException {
 724         return parseUnsignedLong(s, 10);
 725     }
 726 
 727     /**
 728      * Returns a {@code Long} object holding the value
 729      * extracted from the specified {@code String} when parsed
 730      * with the radix given by the second argument.  The first
 731      * argument is interpreted as representing a signed
 732      * {@code long} in the radix specified by the second
 733      * argument, exactly as if the arguments were given to the {@link
 734      * #parseLong(java.lang.String, int)} method. The result is a
 735      * {@code Long} object that represents the {@code long}
 736      * value specified by the string.
 737      *
 738      * <p>In other words, this method returns a {@code Long} object equal
 739      * to the value of:
 740      *
 741      * <blockquote>
 742      *  {@code new Long(Long.parseLong(s, radix))}
 743      * </blockquote>
 744      *
 745      * @param      s       the string to be parsed
 746      * @param      radix   the radix to be used in interpreting {@code s}
 747      * @return     a {@code Long} object holding the value
 748      *             represented by the string argument in the specified
 749      *             radix.
 750      * @throws     NumberFormatException  If the {@code String} does not
 751      *             contain a parsable {@code long}.
 752      */
 753     public static Long valueOf(String s, int radix) throws NumberFormatException {
 754         return Long.valueOf(parseLong(s, radix));
 755     }
 756 
 757     /**
 758      * Returns a {@code Long} object holding the value
 759      * of the specified {@code String}. The argument is
 760      * interpreted as representing a signed decimal {@code long},
 761      * exactly as if the argument were given to the {@link
 762      * #parseLong(java.lang.String)} method. The result is a
 763      * {@code Long} object that represents the integer value
 764      * specified by the string.
 765      *
 766      * <p>In other words, this method returns a {@code Long} object
 767      * equal to the value of:
 768      *
 769      * <blockquote>
 770      *  {@code new Long(Long.parseLong(s))}
 771      * </blockquote>
 772      *
 773      * @param      s   the string to be parsed.
 774      * @return     a {@code Long} object holding the value
 775      *             represented by the string argument.
 776      * @throws     NumberFormatException  If the string cannot be parsed
 777      *             as a {@code long}.
 778      */
 779     public static Long valueOf(String s) throws NumberFormatException
 780     {
 781         return Long.valueOf(parseLong(s, 10));
 782     }
 783 
 784     private static class LongCache {
 785         private LongCache(){}
 786 
 787         static final Long cache[] = new Long[-(-128) + 127 + 1];
 788 
 789         static {
 790             for(int i = 0; i < cache.length; i++)
 791                 cache[i] = new Long(i - 128);
 792         }
 793     }
 794 
 795     /**
 796      * Returns a {@code Long} instance representing the specified
 797      * {@code long} value.
 798      * If a new {@code Long} instance is not required, this method
 799      * should generally be used in preference to the constructor
 800      * {@link #Long(long)}, as this method is likely to yield
 801      * significantly better space and time performance by caching
 802      * frequently requested values.
 803      *
 804      * Note that unlike the {@linkplain Integer#valueOf(int)
 805      * corresponding method} in the {@code Integer} class, this method
 806      * is <em>not</em> required to cache values within a particular
 807      * range.
 808      *
 809      * @param  l a long value.
 810      * @return a {@code Long} instance representing {@code l}.
 811      * @since  1.5
 812      */
 813     public static Long valueOf(long l) {
 814         final int offset = 128;
 815         if (l >= -128 && l <= 127) { // will cache
 816             return LongCache.cache[(int)l + offset];
 817         }
 818         return new Long(l);
 819     }
 820 
 821     /**
 822      * Decodes a {@code String} into a {@code Long}.
 823      * Accepts decimal, hexadecimal, and octal numbers given by the
 824      * following grammar:
 825      *
 826      * <blockquote>
 827      * <dl>
 828      * <dt><i>DecodableString:</i>
 829      * <dd><i>Sign<sub>opt</sub> DecimalNumeral</i>
 830      * <dd><i>Sign<sub>opt</sub></i> {@code 0x} <i>HexDigits</i>
 831      * <dd><i>Sign<sub>opt</sub></i> {@code 0X} <i>HexDigits</i>
 832      * <dd><i>Sign<sub>opt</sub></i> {@code #} <i>HexDigits</i>
 833      * <dd><i>Sign<sub>opt</sub></i> {@code 0} <i>OctalDigits</i>
 834      * <p>
 835      * <dt><i>Sign:</i>
 836      * <dd>{@code -}
 837      * <dd>{@code +}
 838      * </dl>
 839      * </blockquote>
 840      *
 841      * <i>DecimalNumeral</i>, <i>HexDigits</i>, and <i>OctalDigits</i>
 842      * are as defined in section 3.10.1 of
 843      * <cite>The Java&trade; Language Specification</cite>,
 844      * except that underscores are not accepted between digits.
 845      *
 846      * <p>The sequence of characters following an optional
 847      * sign and/or radix specifier ("{@code 0x}", "{@code 0X}",
 848      * "{@code #}", or leading zero) is parsed as by the {@code
 849      * Long.parseLong} method with the indicated radix (10, 16, or 8).
 850      * This sequence of characters must represent a positive value or
 851      * a {@link NumberFormatException} will be thrown.  The result is
 852      * negated if first character of the specified {@code String} is
 853      * the minus sign.  No whitespace characters are permitted in the
 854      * {@code String}.
 855      *
 856      * @param     nm the {@code String} to decode.
 857      * @return    a {@code Long} object holding the {@code long}
 858      *            value represented by {@code nm}
 859      * @throws    NumberFormatException  if the {@code String} does not
 860      *            contain a parsable {@code long}.
 861      * @see java.lang.Long#parseLong(String, int)
 862      * @since 1.2
 863      */
 864     public static Long decode(String nm) throws NumberFormatException {
 865         int radix = 10;
 866         int index = 0;
 867         boolean negative = false;
 868         Long result;
 869 
 870         if (nm.length() == 0)
 871             throw new NumberFormatException("Zero length string");
 872         char firstChar = nm.charAt(0);
 873         // Handle sign, if present
 874         if (firstChar == '-') {
 875             negative = true;
 876             index++;
 877         } else if (firstChar == '+')
 878             index++;
 879 
 880         // Handle radix specifier, if present
 881         if (nm.startsWith("0x", index) || nm.startsWith("0X", index)) {
 882             index += 2;
 883             radix = 16;
 884         }
 885         else if (nm.startsWith("#", index)) {
 886             index ++;
 887             radix = 16;
 888         }
 889         else if (nm.startsWith("0", index) && nm.length() > 1 + index) {
 890             index ++;
 891             radix = 8;
 892         }
 893 
 894         if (nm.startsWith("-", index) || nm.startsWith("+", index))
 895             throw new NumberFormatException("Sign character in wrong position");
 896 
 897         try {
 898             result = Long.valueOf(nm.substring(index), radix);
 899             result = negative ? Long.valueOf(-result.longValue()) : result;
 900         } catch (NumberFormatException e) {
 901             // If number is Long.MIN_VALUE, we'll end up here. The next line
 902             // handles this case, and causes any genuine format error to be
 903             // rethrown.
 904             String constant = negative ? ("-" + nm.substring(index))
 905                                        : nm.substring(index);
 906             result = Long.valueOf(constant, radix);
 907         }
 908         return result;
 909     }
 910 
 911     /**
 912      * The value of the {@code Long}.
 913      *
 914      * @serial
 915      */
 916     private final long value;
 917 
 918     /**
 919      * Constructs a newly allocated {@code Long} object that
 920      * represents the specified {@code long} argument.
 921      *
 922      * @param   value   the value to be represented by the
 923      *          {@code Long} object.
 924      */
 925     public Long(long value) {
 926         this.value = value;
 927     }
 928 
 929     /**
 930      * Constructs a newly allocated {@code Long} object that
 931      * represents the {@code long} value indicated by the
 932      * {@code String} parameter. The string is converted to a
 933      * {@code long} value in exactly the manner used by the
 934      * {@code parseLong} method for radix 10.
 935      *
 936      * @param      s   the {@code String} to be converted to a
 937      *             {@code Long}.
 938      * @throws     NumberFormatException  if the {@code String} does not
 939      *             contain a parsable {@code long}.
 940      * @see        java.lang.Long#parseLong(java.lang.String, int)
 941      */
 942     public Long(String s) throws NumberFormatException {
 943         this.value = parseLong(s, 10);
 944     }
 945 
 946     /**
 947      * Returns the value of this {@code Long} as a {@code byte} after
 948      * a narrowing primitive conversion.
 949      * @jls 5.1.3 Narrowing Primitive Conversions
 950      */
 951     public byte byteValue() {
 952         return (byte)value;
 953     }
 954 
 955     /**
 956      * Returns the value of this {@code Long} as a {@code short} after
 957      * a narrowing primitive conversion.
 958      * @jls 5.1.3 Narrowing Primitive Conversions
 959      */
 960     public short shortValue() {
 961         return (short)value;
 962     }
 963 
 964     /**
 965      * Returns the value of this {@code Long} as an {@code int} after
 966      * a narrowing primitive conversion.
 967      * @jls 5.1.3 Narrowing Primitive Conversions
 968      */
 969     public int intValue() {
 970         return (int)value;
 971     }
 972 
 973     /**
 974      * Returns the value of this {@code Long} as a
 975      * {@code long} value.
 976      */
 977     public long longValue() {
 978         return value;
 979     }
 980 
 981     /**
 982      * Returns the value of this {@code Long} as a {@code float} after
 983      * a widening primitive conversion.
 984      * @jls 5.1.2 Widening Primitive Conversions
 985      */
 986     public float floatValue() {
 987         return (float)value;
 988     }
 989 
 990     /**
 991      * Returns the value of this {@code Long} as a {@code double}
 992      * after a widening primitive conversion.
 993      * @jls 5.1.2 Widening Primitive Conversions
 994      */
 995     public double doubleValue() {
 996         return (double)value;
 997     }
 998 
 999     /**
1000      * Returns a {@code String} object representing this
1001      * {@code Long}'s value.  The value is converted to signed
1002      * decimal representation and returned as a string, exactly as if
1003      * the {@code long} value were given as an argument to the
1004      * {@link java.lang.Long#toString(long)} method.
1005      *
1006      * @return  a string representation of the value of this object in
1007      *          base&nbsp;10.
1008      */
1009     public String toString() {
1010         return toString(value);
1011     }
1012 
1013     /**
1014      * Returns a hash code for this {@code Long}. The result is
1015      * the exclusive OR of the two halves of the primitive
1016      * {@code long} value held by this {@code Long}
1017      * object. That is, the hashcode is the value of the expression:
1018      *
1019      * <blockquote>
1020      *  {@code (int)(this.longValue()^(this.longValue()>>>32))}
1021      * </blockquote>
1022      *
1023      * @return  a hash code value for this object.
1024      */
1025     @Override
1026     public int hashCode() {
1027         return Long.hashCode(value);
1028     }
1029 
1030     /**
1031      * Returns a hash code for a {@code long} value; compatible with
1032      * {@code Long.hashCode()}.
1033      *
1034      * @since 1.8
1035      *
1036      * @return a hash code value for a {@code long} value.
1037      */
1038     public static int hashCode(long value) {
1039         return (int)(value ^ (value >>> 32));
1040     }
1041 
1042     /**
1043      * Compares this object to the specified object.  The result is
1044      * {@code true} if and only if the argument is not
1045      * {@code null} and is a {@code Long} object that
1046      * contains the same {@code long} value as this object.
1047      *
1048      * @param   obj   the object to compare with.
1049      * @return  {@code true} if the objects are the same;
1050      *          {@code false} otherwise.
1051      */
1052     public boolean equals(Object obj) {
1053         if (obj instanceof Long) {
1054             return value == ((Long)obj).longValue();
1055         }
1056         return false;
1057     }
1058 
1059     /**
1060      * Determines the {@code long} value of the system property
1061      * with the specified name.
1062      *
1063      * <p>The first argument is treated as the name of a system
1064      * property.  System properties are accessible through the {@link
1065      * java.lang.System#getProperty(java.lang.String)} method. The
1066      * string value of this property is then interpreted as a {@code
1067      * long} value using the grammar supported by {@link Long#decode decode}
1068      * and a {@code Long} object representing this value is returned.
1069      *
1070      * <p>If there is no property with the specified name, if the
1071      * specified name is empty or {@code null}, or if the property
1072      * does not have the correct numeric format, then {@code null} is
1073      * returned.
1074      *
1075      * <p>In other words, this method returns a {@code Long} object
1076      * equal to the value of:
1077      *
1078      * <blockquote>
1079      *  {@code getLong(nm, null)}
1080      * </blockquote>
1081      *
1082      * @param   nm   property name.
1083      * @return  the {@code Long} value of the property.
1084      * @throws  SecurityException for the same reasons as
1085      *          {@link System#getProperty(String) System.getProperty}
1086      * @see     java.lang.System#getProperty(java.lang.String)
1087      * @see     java.lang.System#getProperty(java.lang.String, java.lang.String)
1088      */
1089     public static Long getLong(String nm) {
1090         return getLong(nm, null);
1091     }
1092 
1093     /**
1094      * Determines the {@code long} value of the system property
1095      * with the specified name.
1096      *
1097      * <p>The first argument is treated as the name of a system
1098      * property.  System properties are accessible through the {@link
1099      * java.lang.System#getProperty(java.lang.String)} method. The
1100      * string value of this property is then interpreted as a {@code
1101      * long} value using the grammar supported by {@link Long#decode decode}
1102      * and a {@code Long} object representing this value is returned.
1103      *
1104      * <p>The second argument is the default value. A {@code Long} object
1105      * that represents the value of the second argument is returned if there
1106      * is no property of the specified name, if the property does not have
1107      * the correct numeric format, or if the specified name is empty or null.
1108      *
1109      * <p>In other words, this method returns a {@code Long} object equal
1110      * to the value of:
1111      *
1112      * <blockquote>
1113      *  {@code getLong(nm, new Long(val))}
1114      * </blockquote>
1115      *
1116      * but in practice it may be implemented in a manner such as:
1117      *
1118      * <blockquote><pre>
1119      * Long result = getLong(nm, null);
1120      * return (result == null) ? new Long(val) : result;
1121      * </pre></blockquote>
1122      *
1123      * to avoid the unnecessary allocation of a {@code Long} object when
1124      * the default value is not needed.
1125      *
1126      * @param   nm    property name.
1127      * @param   val   default value.
1128      * @return  the {@code Long} value of the property.
1129      * @throws  SecurityException for the same reasons as
1130      *          {@link System#getProperty(String) System.getProperty}
1131      * @see     java.lang.System#getProperty(java.lang.String)
1132      * @see     java.lang.System#getProperty(java.lang.String, java.lang.String)
1133      */
1134     public static Long getLong(String nm, long val) {
1135         Long result = Long.getLong(nm, null);
1136         return (result == null) ? Long.valueOf(val) : result;
1137     }
1138 
1139     /**
1140      * Returns the {@code long} value of the system property with
1141      * the specified name.  The first argument is treated as the name
1142      * of a system property.  System properties are accessible through
1143      * the {@link java.lang.System#getProperty(java.lang.String)}
1144      * method. The string value of this property is then interpreted
1145      * as a {@code long} value, as per the
1146      * {@link Long#decode decode} method, and a {@code Long} object
1147      * representing this value is returned; in summary:
1148      *
1149      * <ul>
1150      * <li>If the property value begins with the two ASCII characters
1151      * {@code 0x} or the ASCII character {@code #}, not followed by
1152      * a minus sign, then the rest of it is parsed as a hexadecimal integer
1153      * exactly as for the method {@link #valueOf(java.lang.String, int)}
1154      * with radix 16.
1155      * <li>If the property value begins with the ASCII character
1156      * {@code 0} followed by another character, it is parsed as
1157      * an octal integer exactly as by the method {@link
1158      * #valueOf(java.lang.String, int)} with radix 8.
1159      * <li>Otherwise the property value is parsed as a decimal
1160      * integer exactly as by the method
1161      * {@link #valueOf(java.lang.String, int)} with radix 10.
1162      * </ul>
1163      *
1164      * <p>Note that, in every case, neither {@code L}
1165      * ({@code '\u005Cu004C'}) nor {@code l}
1166      * ({@code '\u005Cu006C'}) is permitted to appear at the end
1167      * of the property value as a type indicator, as would be
1168      * permitted in Java programming language source code.
1169      *
1170      * <p>The second argument is the default value. The default value is
1171      * returned if there is no property of the specified name, if the
1172      * property does not have the correct numeric format, or if the
1173      * specified name is empty or {@code null}.
1174      *
1175      * @param   nm   property name.
1176      * @param   val   default value.
1177      * @return  the {@code Long} value of the property.
1178      * @throws  SecurityException for the same reasons as
1179      *          {@link System#getProperty(String) System.getProperty}
1180      * @see     System#getProperty(java.lang.String)
1181      * @see     System#getProperty(java.lang.String, java.lang.String)
1182      */
1183     public static Long getLong(String nm, Long val) {
1184         String v = null;
1185         try {
1186             v = System.getProperty(nm);
1187         } catch (IllegalArgumentException | NullPointerException e) {
1188         }
1189         if (v != null) {
1190             try {
1191                 return Long.decode(v);
1192             } catch (NumberFormatException e) {
1193             }
1194         }
1195         return val;
1196     }
1197 
1198     /**
1199      * Compares two {@code Long} objects numerically.
1200      *
1201      * @param   anotherLong   the {@code Long} to be compared.
1202      * @return  the value {@code 0} if this {@code Long} is
1203      *          equal to the argument {@code Long}; a value less than
1204      *          {@code 0} if this {@code Long} is numerically less
1205      *          than the argument {@code Long}; and a value greater
1206      *          than {@code 0} if this {@code Long} is numerically
1207      *           greater than the argument {@code Long} (signed
1208      *           comparison).
1209      * @since   1.2
1210      */
1211     public int compareTo(Long anotherLong) {
1212         return compare(this.value, anotherLong.value);
1213     }
1214 
1215     /**
1216      * Compares two {@code long} values numerically.
1217      * The value returned is identical to what would be returned by:
1218      * <pre>
1219      *    Long.valueOf(x).compareTo(Long.valueOf(y))
1220      * </pre>
1221      *
1222      * @param  x the first {@code long} to compare
1223      * @param  y the second {@code long} to compare
1224      * @return the value {@code 0} if {@code x == y};
1225      *         a value less than {@code 0} if {@code x < y}; and
1226      *         a value greater than {@code 0} if {@code x > y}
1227      * @since 1.7
1228      */
1229     public static int compare(long x, long y) {
1230         return (x < y) ? -1 : ((x == y) ? 0 : 1);
1231     }
1232 
1233     /**
1234      * Compares two {@code long} values numerically treating the values
1235      * as unsigned.
1236      *
1237      * @param  x the first {@code long} to compare
1238      * @param  y the second {@code long} to compare
1239      * @return the value {@code 0} if {@code x == y}; a value less
1240      *         than {@code 0} if {@code x < y} as unsigned values; and
1241      *         a value greater than {@code 0} if {@code x > y} as
1242      *         unsigned values
1243      * @since 1.8
1244      */
1245     public static int compareUnsigned(long x, long y) {
1246         return compare(x + MIN_VALUE, y + MIN_VALUE);
1247     }
1248 
1249 
1250     /**
1251      * Returns the unsigned quotient of dividing the first argument by
1252      * the second where each argument and the result is interpreted as
1253      * an unsigned value.
1254      *
1255      * <p>Note that in two's complement arithmetic, the three other
1256      * basic arithmetic operations of add, subtract, and multiply are
1257      * bit-wise identical if the two operands are regarded as both
1258      * being signed or both being unsigned.  Therefore separate {@code
1259      * addUnsigned}, etc. methods are not provided.
1260      *
1261      * @param dividend the value to be divided
1262      * @param divisor the value doing the dividing
1263      * @return the unsigned quotient of the first argument divided by
1264      * the second argument
1265      * @see #remainderUnsigned
1266      * @since 1.8
1267      */
1268     public static long divideUnsigned(long dividend, long divisor) {
1269         if (divisor < 0L) { // signed comparison
1270             // Answer must be 0 or 1 depending on relative magnitude
1271             // of dividend and divisor.
1272             return (compareUnsigned(dividend, divisor)) < 0 ? 0L :1L;
1273         }
1274 
1275         if (dividend > 0) //  Both inputs non-negative
1276             return dividend/divisor;
1277         else {
1278             /*
1279              * For simple code, leveraging BigInteger.  Longer and faster
1280              * code written directly in terms of operations on longs is
1281              * possible; see "Hacker's Delight" for divide and remainder
1282              * algorithms.
1283              */
1284             return toUnsignedBigInteger(dividend).
1285                 divide(toUnsignedBigInteger(divisor)).longValue();
1286         }
1287     }
1288 
1289     /**
1290      * Returns the unsigned remainder from dividing the first argument
1291      * by the second where each argument and the result is interpreted
1292      * as an unsigned value.
1293      *
1294      * @param dividend the value to be divided
1295      * @param divisor the value doing the dividing
1296      * @return the unsigned remainder of the first argument divided by
1297      * the second argument
1298      * @see #divideUnsigned
1299      * @since 1.8
1300      */
1301     public static long remainderUnsigned(long dividend, long divisor) {
1302         if (dividend > 0 && divisor > 0) { // signed comparisons
1303             return dividend % divisor;
1304         } else {
1305             if (compareUnsigned(dividend, divisor) < 0) // Avoid explicit check for 0 divisor
1306                 return dividend;
1307             else
1308                 return toUnsignedBigInteger(dividend).
1309                     remainder(toUnsignedBigInteger(divisor)).longValue();
1310         }
1311     }
1312 
1313     // Bit Twiddling
1314 
1315     /**
1316      * The number of bits used to represent a {@code long} value in two's
1317      * complement binary form.
1318      *
1319      * @since 1.5
1320      */
1321     @Native public static final int SIZE = 64;
1322 
1323     /**
1324      * The number of bytes used to represent a {@code long} value in two's
1325      * complement binary form.
1326      *
1327      * @since 1.8
1328      */
1329     public static final int BYTES = SIZE / Byte.SIZE;
1330 
1331     /**
1332      * Returns a {@code long} value with at most a single one-bit, in the
1333      * position of the highest-order ("leftmost") one-bit in the specified
1334      * {@code long} value.  Returns zero if the specified value has no
1335      * one-bits in its two's complement binary representation, that is, if it
1336      * is equal to zero.
1337      *
1338      * @return a {@code long} value with a single one-bit, in the position
1339      *     of the highest-order one-bit in the specified value, or zero if
1340      *     the specified value is itself equal to zero.
1341      * @since 1.5
1342      */
1343     public static long highestOneBit(long i) {
1344         // HD, Figure 3-1
1345         i |= (i >>  1);
1346         i |= (i >>  2);
1347         i |= (i >>  4);
1348         i |= (i >>  8);
1349         i |= (i >> 16);
1350         i |= (i >> 32);
1351         return i - (i >>> 1);
1352     }
1353 
1354     /**
1355      * Returns a {@code long} value with at most a single one-bit, in the
1356      * position of the lowest-order ("rightmost") one-bit in the specified
1357      * {@code long} value.  Returns zero if the specified value has no
1358      * one-bits in its two's complement binary representation, that is, if it
1359      * is equal to zero.
1360      *
1361      * @return a {@code long} value with a single one-bit, in the position
1362      *     of the lowest-order one-bit in the specified value, or zero if
1363      *     the specified value is itself equal to zero.
1364      * @since 1.5
1365      */
1366     public static long lowestOneBit(long i) {
1367         // HD, Section 2-1
1368         return i & -i;
1369     }
1370 
1371     /**
1372      * Returns the number of zero bits preceding the highest-order
1373      * ("leftmost") one-bit in the two's complement binary representation
1374      * of the specified {@code long} value.  Returns 64 if the
1375      * specified value has no one-bits in its two's complement representation,
1376      * in other words if it is equal to zero.
1377      *
1378      * <p>Note that this method is closely related to the logarithm base 2.
1379      * For all positive {@code long} values x:
1380      * <ul>
1381      * <li>floor(log<sub>2</sub>(x)) = {@code 63 - numberOfLeadingZeros(x)}
1382      * <li>ceil(log<sub>2</sub>(x)) = {@code 64 - numberOfLeadingZeros(x - 1)}
1383      * </ul>
1384      *
1385      * @return the number of zero bits preceding the highest-order
1386      *     ("leftmost") one-bit in the two's complement binary representation
1387      *     of the specified {@code long} value, or 64 if the value
1388      *     is equal to zero.
1389      * @since 1.5
1390      */
1391     public static int numberOfLeadingZeros(long i) {
1392         // HD, Figure 5-6
1393          if (i == 0)
1394             return 64;
1395         int n = 1;
1396         int x = (int)(i >>> 32);
1397         if (x == 0) { n += 32; x = (int)i; }
1398         if (x >>> 16 == 0) { n += 16; x <<= 16; }
1399         if (x >>> 24 == 0) { n +=  8; x <<=  8; }
1400         if (x >>> 28 == 0) { n +=  4; x <<=  4; }
1401         if (x >>> 30 == 0) { n +=  2; x <<=  2; }
1402         n -= x >>> 31;
1403         return n;
1404     }
1405 
1406     /**
1407      * Returns the number of zero bits following the lowest-order ("rightmost")
1408      * one-bit in the two's complement binary representation of the specified
1409      * {@code long} value.  Returns 64 if the specified value has no
1410      * one-bits in its two's complement representation, in other words if it is
1411      * equal to zero.
1412      *
1413      * @return the number of zero bits following the lowest-order ("rightmost")
1414      *     one-bit in the two's complement binary representation of the
1415      *     specified {@code long} value, or 64 if the value is equal
1416      *     to zero.
1417      * @since 1.5
1418      */
1419     public static int numberOfTrailingZeros(long i) {
1420         // HD, Figure 5-14
1421         int x, y;
1422         if (i == 0) return 64;
1423         int n = 63;
1424         y = (int)i; if (y != 0) { n = n -32; x = y; } else x = (int)(i>>>32);
1425         y = x <<16; if (y != 0) { n = n -16; x = y; }
1426         y = x << 8; if (y != 0) { n = n - 8; x = y; }
1427         y = x << 4; if (y != 0) { n = n - 4; x = y; }
1428         y = x << 2; if (y != 0) { n = n - 2; x = y; }
1429         return n - ((x << 1) >>> 31);
1430     }
1431 
1432     /**
1433      * Returns the number of one-bits in the two's complement binary
1434      * representation of the specified {@code long} value.  This function is
1435      * sometimes referred to as the <i>population count</i>.
1436      *
1437      * @return the number of one-bits in the two's complement binary
1438      *     representation of the specified {@code long} value.
1439      * @since 1.5
1440      */
1441      public static int bitCount(long i) {
1442         // HD, Figure 5-14
1443         i = i - ((i >>> 1) & 0x5555555555555555L);
1444         i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
1445         i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
1446         i = i + (i >>> 8);
1447         i = i + (i >>> 16);
1448         i = i + (i >>> 32);
1449         return (int)i & 0x7f;
1450      }
1451 
1452     /**
1453      * Returns the value obtained by rotating the two's complement binary
1454      * representation of the specified {@code long} value left by the
1455      * specified number of bits.  (Bits shifted out of the left hand, or
1456      * high-order, side reenter on the right, or low-order.)
1457      *
1458      * <p>Note that left rotation with a negative distance is equivalent to
1459      * right rotation: {@code rotateLeft(val, -distance) == rotateRight(val,
1460      * distance)}.  Note also that rotation by any multiple of 64 is a
1461      * no-op, so all but the last six bits of the rotation distance can be
1462      * ignored, even if the distance is negative: {@code rotateLeft(val,
1463      * distance) == rotateLeft(val, distance & 0x3F)}.
1464      *
1465      * @return the value obtained by rotating the two's complement binary
1466      *     representation of the specified {@code long} value left by the
1467      *     specified number of bits.
1468      * @since 1.5
1469      */
1470     public static long rotateLeft(long i, int distance) {
1471         return (i << distance) | (i >>> -distance);
1472     }
1473 
1474     /**
1475      * Returns the value obtained by rotating the two's complement binary
1476      * representation of the specified {@code long} value right by the
1477      * specified number of bits.  (Bits shifted out of the right hand, or
1478      * low-order, side reenter on the left, or high-order.)
1479      *
1480      * <p>Note that right rotation with a negative distance is equivalent to
1481      * left rotation: {@code rotateRight(val, -distance) == rotateLeft(val,
1482      * distance)}.  Note also that rotation by any multiple of 64 is a
1483      * no-op, so all but the last six bits of the rotation distance can be
1484      * ignored, even if the distance is negative: {@code rotateRight(val,
1485      * distance) == rotateRight(val, distance & 0x3F)}.
1486      *
1487      * @return the value obtained by rotating the two's complement binary
1488      *     representation of the specified {@code long} value right by the
1489      *     specified number of bits.
1490      * @since 1.5
1491      */
1492     public static long rotateRight(long i, int distance) {
1493         return (i >>> distance) | (i << -distance);
1494     }
1495 
1496     /**
1497      * Returns the value obtained by reversing the order of the bits in the
1498      * two's complement binary representation of the specified {@code long}
1499      * value.
1500      *
1501      * @return the value obtained by reversing order of the bits in the
1502      *     specified {@code long} value.
1503      * @since 1.5
1504      */
1505     public static long reverse(long i) {
1506         // HD, Figure 7-1
1507         i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;
1508         i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;
1509         i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;
1510         i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;
1511         i = (i << 48) | ((i & 0xffff0000L) << 16) |
1512             ((i >>> 16) & 0xffff0000L) | (i >>> 48);
1513         return i;
1514     }
1515 
1516     /**
1517      * Returns the signum function of the specified {@code long} value.  (The
1518      * return value is -1 if the specified value is negative; 0 if the
1519      * specified value is zero; and 1 if the specified value is positive.)
1520      *
1521      * @return the signum function of the specified {@code long} value.
1522      * @since 1.5
1523      */
1524     public static int signum(long i) {
1525         // HD, Section 2-7
1526         return (int) ((i >> 63) | (-i >>> 63));
1527     }
1528 
1529     /**
1530      * Returns the value obtained by reversing the order of the bytes in the
1531      * two's complement representation of the specified {@code long} value.
1532      *
1533      * @return the value obtained by reversing the bytes in the specified
1534      *     {@code long} value.
1535      * @since 1.5
1536      */
1537     public static long reverseBytes(long i) {
1538         i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;
1539         return (i << 48) | ((i & 0xffff0000L) << 16) |
1540             ((i >>> 16) & 0xffff0000L) | (i >>> 48);
1541     }
1542 
1543     /** use serialVersionUID from JDK 1.0.2 for interoperability */
1544     @Native private static final long serialVersionUID = 4290774380558885855L;
1545 }