103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta/* 203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Copyright (C) 2013 The Android Open Source Project 303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * 403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Licensed under the Apache License, Version 2.0 (the "License"); 503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * you may not use this file except in compliance with the License. 603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * You may obtain a copy of the License at 703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * 803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * http://www.apache.org/licenses/LICENSE-2.0 903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * 1003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Unless required by applicable law or agreed to in writing, software 1103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * distributed under the License is distributed on an "AS IS" BASIS, 1203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * See the License for the specific language governing permissions and 1403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * limitations under the License. 1503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 1603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 1703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Guptapackage com.android.tools.layoutlib.java; 1803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 1903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta/** 2003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Defines the same class as the java.lang.IntegralToString which was added in 2103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Dalvik VM. This hack, provides a replacement for that class which can't be 2203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * loaded in the standard JVM since it's in the java package and standard JVM 2303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * doesn't have it. Since it's no longer in java.lang, access to package 2403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * private methods and classes has been replaced by the closes matching public 2503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * implementation. 2603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * <p/> 2703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Extracted from API level 18, file: 2803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * platform/libcore/luni/src/main/java/java/lang/IntegralToString.java 2903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 3003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Guptapublic final class IntegralToString { 3103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 3203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * When appending to an AbstractStringBuilder, this thread-local char[] lets us avoid 3303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * allocation of a temporary array. (We can't write straight into the AbstractStringBuilder 3403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * because it's almost as expensive to work out the exact length of the result as it is to 3503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * do the formatting. We could try being conservative and "delete"-ing the unused space 3603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * afterwards, but then we'd need to duplicate convertInt and convertLong rather than share 3703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * the code.) 3803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 3903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static final ThreadLocal<char[]> BUFFER = new ThreadLocal<char[]>() { 4003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta @Override protected char[] initialValue() { 4103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new char[20]; // Maximum length of a base-10 long. 4203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 4303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta }; 4403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 4503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 4603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * These tables are used to special-case toString computation for 4703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * small values. This serves three purposes: it reduces memory usage; 4803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * it increases performance for small values; and it decreases the 4903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * number of comparisons required to do the length computation. 5003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Elements of this table are lazily initialized on first use. 5103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * No locking is necessary, i.e., we use the non-volatile, racy 5203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * single-check idiom. 5303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 5403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static final String[] SMALL_NONNEGATIVE_VALUES = new String[100]; 5503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static final String[] SMALL_NEGATIVE_VALUES = new String[100]; 5603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 5703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** TENS[i] contains the tens digit of the number i, 0 <= i <= 99. */ 5803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static final char[] TENS = { 5903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', 6003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', 6103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', 6203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '3', '3', '3', '3', '3', '3', '3', '3', '3', '3', 6303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '4', '4', '4', '4', '4', '4', '4', '4', '4', '4', 6403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '5', '5', '5', '5', '5', '5', '5', '5', '5', '5', 6503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '6', '6', '6', '6', '6', '6', '6', '6', '6', '6', 6603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '7', '7', '7', '7', '7', '7', '7', '7', '7', '7', 6703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '8', '8', '8', '8', '8', '8', '8', '8', '8', '8', 6803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '9', '9', '9', '9', '9', '9', '9', '9', '9', '9' 6903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta }; 7003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 7103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** Ones [i] contains the tens digit of the number i, 0 <= i <= 99. */ 7203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static final char[] ONES = { 7303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 7403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 7503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 7603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 7703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 7803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 7903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 8003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 8103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 8203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 8303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta }; 8403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 8503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 8603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Table for MOD / DIV 10 computation described in Section 10-21 8703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * of Hank Warren's "Hacker's Delight" online addendum. 8803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * http://www.hackersdelight.org/divcMore.pdf 8903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 9003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static final char[] MOD_10_TABLE = { 9103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 0 9203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta }; 9303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 9403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 9503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * The digits for every supported radix. 9603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 9703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static final char[] DIGITS = { 9803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 9903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 10003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 10103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 'u', 'v', 'w', 'x', 'y', 'z' 10203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta }; 10303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 10403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static final char[] UPPER_CASE_DIGITS = { 10503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 10603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 10703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 10803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 'U', 'V', 'W', 'X', 'Y', 'Z' 10903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta }; 11003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 11103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private IntegralToString() { 11203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 11303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 11403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 11503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Equivalent to Integer.toString(i, radix). 11603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 11703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String intToString(int i, int radix) { 11803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { 11903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta radix = 10; 12003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 12103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (radix == 10) { 12203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return intToString(i); 12303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 12403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 12503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /* 12603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * If i is positive, negate it. This is the opposite of what one might 12703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * expect. It is necessary because the range of the negative values is 12803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * strictly larger than that of the positive values: there is no 12903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * positive value corresponding to Integer.MIN_VALUE. 13003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 13103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta boolean negative = false; 13203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (i < 0) { 13303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta negative = true; 13403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } else { 13503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta i = -i; 13603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 13703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 13803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = radix < 8 ? 33 : 12; // Max chars in result (conservative) 13903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[bufLen]; 14003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = bufLen; 14103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 14203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta do { 14303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int q = i / radix; 14403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[radix * q - i]; 14503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta i = q; 14603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } while (i != 0); 14703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 14803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (negative) { 14903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = '-'; 15003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 15103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 15203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 15303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 15403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 15503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 15603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Equivalent to Integer.toString(i). 15703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 15803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String intToString(int i) { 15903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return convertInt(null, i); 16003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 16103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 16203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 16303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Equivalent to sb.append(Integer.toString(i)). 16403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 16503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static void appendInt(StringBuilder sb, int i) { 16603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta convertInt(sb, i); 16703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 16803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 16903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 17003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Returns the string representation of i and leaves sb alone if sb is null. 17103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Returns null and appends the string representation of i to sb if sb is non-null. 17203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 17303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static String convertInt(StringBuilder sb, int i) { 17403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta boolean negative = false; 17503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta String quickResult = null; 17603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (i < 0) { 17703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta negative = true; 17803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta i = -i; 17903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (i < 100) { 18003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (i < 0) { 18103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // If -n is still negative, n is Integer.MIN_VALUE 18203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta quickResult = "-2147483648"; 18303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } else { 18403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta quickResult = SMALL_NEGATIVE_VALUES[i]; 18503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (quickResult == null) { 18603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta SMALL_NEGATIVE_VALUES[i] = quickResult = 18703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta i < 10 ? stringOf('-', ONES[i]) : stringOf('-', TENS[i], ONES[i]); 18803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 18903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 19003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 19103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } else { 19203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (i < 100) { 19303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta quickResult = SMALL_NONNEGATIVE_VALUES[i]; 19403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (quickResult == null) { 19503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta SMALL_NONNEGATIVE_VALUES[i] = quickResult = 19603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta i < 10 ? stringOf(ONES[i]) : stringOf(TENS[i], ONES[i]); 19703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 19803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 19903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 20003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (quickResult != null) { 20103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (sb != null) { 20203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta sb.append(quickResult); 20303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return null; 20403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 20503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return quickResult; 20603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 20703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 20803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = 11; // Max number of chars in result 20903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = (sb != null) ? BUFFER.get() : new char[bufLen]; 21003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = bufLen; 21103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 21203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Calculate digits two-at-a-time till remaining digits fit in 16 bits 21303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta while (i >= (1 << 16)) { 21403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8 21503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int q = (int) ((0x51EB851FL * i) >>> 37); 21603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int r = i - 100*q; 21703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = ONES[r]; 21803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = TENS[r]; 21903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta i = q; 22003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 22103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 22203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Calculate remaining digits one-at-a-time for performance 22303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta while (i != 0) { 22403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Compute q = n/10 and r = n % 10 as per "Hacker's Delight" 10-8 22503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int q = (0xCCCD * i) >>> 19; 22603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int r = i - 10*q; 22703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[r]; 22803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta i = q; 22903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 23003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 23103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (negative) { 23203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = '-'; 23303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 23403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 23503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (sb != null) { 23603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta sb.append(buf, cursor, bufLen - cursor); 23703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return null; 23803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } else { 23903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 24003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 24103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 24203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 24303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 24403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Equivalent to Long.toString(v, radix). 24503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 24603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String longToString(long v, int radix) { 24703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int i = (int) v; 24803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (i == v) { 24903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return intToString(i, radix); 25003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 25103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 25203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { 25303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta radix = 10; 25403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 25503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (radix == 10) { 25603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return longToString(v); 25703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 25803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 25903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /* 26003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * If v is positive, negate it. This is the opposite of what one might 26103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * expect. It is necessary because the range of the negative values is 26203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * strictly larger than that of the positive values: there is no 26303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * positive value corresponding to Integer.MIN_VALUE. 26403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 26503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta boolean negative = false; 26603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (v < 0) { 26703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta negative = true; 26803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } else { 26903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta v = -v; 27003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 27103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 27203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = radix < 8 ? 65 : 23; // Max chars in result (conservative) 27303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[bufLen]; 27403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = bufLen; 27503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 27603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta do { 27703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta long q = v / radix; 27803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[(int) (radix * q - v)]; 27903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta v = q; 28003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } while (v != 0); 28103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 28203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (negative) { 28303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = '-'; 28403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 28503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 28603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 28703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 28803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 28903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 29003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Equivalent to Long.toString(l). 29103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 29203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String longToString(long l) { 29303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return convertLong(null, l); 29403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 29503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 29603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 29703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Equivalent to sb.append(Long.toString(l)). 29803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 29903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static void appendLong(StringBuilder sb, long l) { 30003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta convertLong(sb, l); 30103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 30203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 30303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 30403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Returns the string representation of n and leaves sb alone if sb is null. 30503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Returns null and appends the string representation of n to sb if sb is non-null. 30603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 30703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static String convertLong(StringBuilder sb, long n) { 30803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int i = (int) n; 30903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (i == n) { 31003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return convertInt(sb, i); 31103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 31203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 31303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta boolean negative = (n < 0); 31403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (negative) { 31503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta n = -n; 31603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (n < 0) { 31703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // If -n is still negative, n is Long.MIN_VALUE 31803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta String quickResult = "-9223372036854775808"; 31903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (sb != null) { 32003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta sb.append(quickResult); 32103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return null; 32203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 32303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return quickResult; 32403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 32503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 32603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 32703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = 20; // Maximum number of chars in result 32803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = (sb != null) ? BUFFER.get() : new char[bufLen]; 32903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 33003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int low = (int) (n % 1000000000); // Extract low-order 9 digits 33103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = intIntoCharArray(buf, bufLen, low); 33203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 33303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Zero-pad Low order part to 9 digits 33403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta while (cursor != (bufLen - 9)) { 33503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = '0'; 33603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 33703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 33803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /* 33903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * The remaining digits are (n - low) / 1,000,000,000. This 34003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * "exact division" is done as per the online addendum to Hank Warren's 34103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * "Hacker's Delight" 10-20, http://www.hackersdelight.org/divcMore.pdf 34203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 34303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta n = ((n - low) >>> 9) * 0x8E47CE423A2E9C6DL; 34403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 34503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /* 34603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * If the remaining digits fit in an int, emit them using a 34703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * single call to intIntoCharArray. Otherwise, strip off the 34803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * low-order digit, put it in buf, and then call intIntoCharArray 34903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * on the remaining digits (which now fit in an int). 35003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 35103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if ((n & (-1L << 32)) == 0) { 35203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta cursor = intIntoCharArray(buf, cursor, (int) n); 35303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } else { 35403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /* 35503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Set midDigit to n % 10 35603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 35703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int lo32 = (int) n; 35803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int hi32 = (int) (n >>> 32); 35903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 36003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // midDigit = ((unsigned) low32) % 10, per "Hacker's Delight" 10-21 36103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int midDigit = MOD_10_TABLE[(0x19999999 * lo32 + (lo32 >>> 1) + (lo32 >>> 3)) >>> 28]; 36203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 36303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Adjust midDigit for hi32. (assert hi32 == 1 || hi32 == 2) 36403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta midDigit -= hi32 << 2; // 1L << 32 == -4 MOD 10 36503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (midDigit < 0) { 36603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta midDigit += 10; 36703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 36803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[midDigit]; 36903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 37003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Exact division as per Warren 10-20 37103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int rest = ((int) ((n - midDigit) >>> 1)) * 0xCCCCCCCD; 37203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta cursor = intIntoCharArray(buf, cursor, rest); 37303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 37403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 37503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (negative) { 37603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = '-'; 37703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 37803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (sb != null) { 37903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta sb.append(buf, cursor, bufLen - cursor); 38003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return null; 38103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } else { 38203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 38303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 38403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 38503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 38603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /** 38703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Inserts the unsigned decimal integer represented by n into the specified 38803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * character array starting at position cursor. Returns the index after 38903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * the last character inserted (i.e., the value to pass in as cursor the 39003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * next time this method is called). Note that n is interpreted as a large 39103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * positive integer (not a negative integer) if its sign bit is set. 39203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 39303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static int intIntoCharArray(char[] buf, int cursor, int n) { 39403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Calculate digits two-at-a-time till remaining digits fit in 16 bits 39503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta while ((n & 0xffff0000) != 0) { 39603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta /* 39703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8. 39803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * This computation is slightly different from the corresponding 39903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * computation in intToString: the shifts before and after 40003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * multiply can't be combined, as that would yield the wrong result 40103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta * if n's sign bit were set. 40203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta */ 40303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int q = (int) ((0x51EB851FL * (n >>> 2)) >>> 35); 40403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int r = n - 100*q; 40503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = ONES[r]; 40603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = TENS[r]; 40703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta n = q; 40803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 40903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 41003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Calculate remaining digits one-at-a-time for performance 41103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta while (n != 0) { 41203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta // Compute q = n / 10 and r = n % 10 as per "Hacker's Delight" 10-8 41303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int q = (0xCCCD * n) >>> 19; 41403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int r = n - 10*q; 41503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[r]; 41603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta n = q; 41703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 41803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return cursor; 41903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 42003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 42103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String intToBinaryString(int i) { 42203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = 32; // Max number of binary digits in an int 42303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[bufLen]; 42403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = bufLen; 42503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 42603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta do { 42703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[i & 1]; 42803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } while ((i >>>= 1) != 0); 42903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 43003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 43103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 43203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 43303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String longToBinaryString(long v) { 43403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int i = (int) v; 43503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (v >= 0 && i == v) { 43603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return intToBinaryString(i); 43703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 43803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 43903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = 64; // Max number of binary digits in a long 44003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[bufLen]; 44103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = bufLen; 44203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 44303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta do { 44403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[((int) v) & 1]; 44503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } while ((v >>>= 1) != 0); 44603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 44703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 44803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 44903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 45003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static StringBuilder appendByteAsHex(StringBuilder sb, byte b, boolean upperCase) { 45103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] digits = upperCase ? UPPER_CASE_DIGITS : DIGITS; 45203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta sb.append(digits[(b >> 4) & 0xf]); 45303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta sb.append(digits[b & 0xf]); 45403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return sb; 45503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 45603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 45703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String byteToHexString(byte b, boolean upperCase) { 45803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] digits = upperCase ? UPPER_CASE_DIGITS : DIGITS; 45903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[2]; // We always want two digits. 46003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[0] = digits[(b >> 4) & 0xf]; 46103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[1] = digits[b & 0xf]; 46203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, 0, 2); 46303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 46403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 46503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String bytesToHexString(byte[] bytes, boolean upperCase) { 46603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] digits = upperCase ? UPPER_CASE_DIGITS : DIGITS; 46703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[bytes.length * 2]; 46803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int c = 0; 46903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta for (byte b : bytes) { 47003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[c++] = digits[(b >> 4) & 0xf]; 47103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[c++] = digits[b & 0xf]; 47203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 47303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf); 47403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 47503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 47603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String intToHexString(int i, boolean upperCase, int minWidth) { 47703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = 8; // Max number of hex digits in an int 47803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[bufLen]; 47903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = bufLen; 48003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 48103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] digits = upperCase ? UPPER_CASE_DIGITS : DIGITS; 48203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta do { 48303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = digits[i & 0xf]; 48403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } while ((i >>>= 4) != 0 || (bufLen - cursor < minWidth)); 48503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 48603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 48703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 48803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 48903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String longToHexString(long v) { 49003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int i = (int) v; 49103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (v >= 0 && i == v) { 49203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return intToHexString(i, false, 0); 49303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 49403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 49503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = 16; // Max number of hex digits in a long 49603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[bufLen]; 49703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = bufLen; 49803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 49903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta do { 50003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[((int) v) & 0xF]; 50103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } while ((v >>>= 4) != 0); 50203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 50303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 50403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 50503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 50603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String intToOctalString(int i) { 50703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = 11; // Max number of octal digits in an int 50803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[bufLen]; 50903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = bufLen; 51003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 51103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta do { 51203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[i & 7]; 51303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } while ((i >>>= 3) != 0); 51403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 51503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 51603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 51703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 51803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta public static String longToOctalString(long v) { 51903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int i = (int) v; 52003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta if (v >= 0 && i == v) { 52103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return intToOctalString(i); 52203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 52303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int bufLen = 22; // Max number of octal digits in a long 52403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta char[] buf = new char[bufLen]; 52503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta int cursor = bufLen; 52603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 52703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta do { 52803a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta buf[--cursor] = DIGITS[((int) v) & 7]; 52903a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } while ((v >>>= 3) != 0); 53003a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 53103a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(buf, cursor, bufLen - cursor); 53203a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 53303a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta 53403a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta private static String stringOf(char... args) { 53503a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta return new String(args, 0, args.length); 53603a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta } 53703a057c1af9ca3f125c7924bf0b78da52223d8d3Deepanshu Gupta} 538