1 package com.jme3.util;
2 
3 
4 /**
5  * The wrapper for the primitive type {@code int}.
6  * <p>
7  * As with the specification, this implementation relies on code laid out in <a
8  * href="http://www.hackersdelight.org/">Henry S. Warren, Jr.'s Hacker's
9  * Delight, (Addison Wesley, 2002)</a> as well as <a
10  * href="http://aggregate.org/MAGIC/">The Aggregate's Magic Algorithms</a>.
11  *
12  * @see java.lang.Number
13  * @since 1.1
14  */
15 public final class FastInteger {
16 
17     /**
18      * Constant for the maximum {@code int} value, 2<sup>31</sup>-1.
19      */
20     public static final int MAX_VALUE = 0x7FFFFFFF;
21 
22     /**
23      * Constant for the minimum {@code int} value, -2<sup>31</sup>.
24      */
25     public static final int MIN_VALUE = 0x80000000;
26 
27     /**
28      * Constant for the number of bits needed to represent an {@code int} in
29      * two's complement form.
30      *
31      * @since 1.5
32      */
33     public static final int SIZE = 32;
34 
35     /*
36      * Progressively smaller decimal order of magnitude that can be represented
37      * by an instance of Integer. Used to help compute the String
38      * representation.
39      */
40     private static final int[] decimalScale = new int[] { 1000000000, 100000000,
41             10000000, 1000000, 100000, 10000, 1000, 100, 10, 1 };
42 
43     /**
44      * Converts the specified integer into its decimal string representation.
45      * The returned string is a concatenation of a minus sign if the number is
46      * negative and characters from '0' to '9'.
47      *
48      * @param value
49      *            the integer to convert.
50      * @return the decimal string representation of {@code value}.
51      */
toCharArray(int value, char[] output)52     public static boolean toCharArray(int value, char[] output) {
53         if (value == 0)
54         {
55             output[0] = '0';
56             output[1] = 0;
57             return true;
58         }
59 
60         // Faster algorithm for smaller Integers
61         if (value < 1000 && value > -1000) {
62 
63             int positive_value = value < 0 ? -value : value;
64             int first_digit = 0;
65             if (value < 0) {
66                 output[0] = '-';
67                 first_digit++;
68             }
69             int last_digit = first_digit;
70             int quot = positive_value;
71             do {
72                 int res = quot / 10;
73                 int digit_value = quot - ((res << 3) + (res << 1));
74                 digit_value += '0';
75                 output[last_digit++] = (char) digit_value;
76                 quot = res;
77             } while (quot != 0);
78 
79             int count = last_digit--;
80             do {
81                 char tmp = output[last_digit];
82                 output[last_digit--] = output[first_digit];
83                 output[first_digit++] = tmp;
84             } while (first_digit < last_digit);
85             output[count] = 0;
86             return true;
87         }
88         if (value == MIN_VALUE) {
89             System.arraycopy("-2147483648".toCharArray(), 0, output, 0, 12);
90             output[12] = 0;
91             return true;
92         }
93 
94 
95         int positive_value = value < 0 ? -value : value;
96         byte first_digit = 0;
97         if (value < 0) {
98             output[0] = '-';
99             first_digit++;
100         }
101         byte last_digit = first_digit;
102         byte count;
103         int number;
104         boolean start = false;
105         for (int i = 0; i < 9; i++) {
106             count = 0;
107             if (positive_value < (number = decimalScale[i])) {
108                 if (start) {
109                     output[last_digit++] = '0';
110                 }
111                 continue;
112             }
113 
114             if (i > 0) {
115                 number = (decimalScale[i] << 3);
116                 if (positive_value >= number) {
117                     positive_value -= number;
118                     count += 8;
119                 }
120                 number = (decimalScale[i] << 2);
121                 if (positive_value >= number) {
122                     positive_value -= number;
123                     count += 4;
124                 }
125             }
126             number = (decimalScale[i] << 1);
127             if (positive_value >= number) {
128                 positive_value -= number;
129                 count += 2;
130             }
131             if (positive_value >= decimalScale[i]) {
132                 positive_value -= decimalScale[i];
133                 count++;
134             }
135             if (count > 0 && !start) {
136                 start = true;
137             }
138             if (start) {
139                 output[last_digit++] = (char) (count + '0');
140             }
141         }
142 
143         output[last_digit++] = (char) (positive_value + '0');
144         output[last_digit] = 0;
145         count = last_digit--;
146         return true;
147     }
148 
149 
150     /**
151      * Determines the highest (leftmost) bit of the specified integer that is 1
152      * and returns the bit mask value for that bit. This is also referred to as
153      * the Most Significant 1 Bit. Returns zero if the specified integer is
154      * zero.
155      *
156      * @param i
157      *            the integer to examine.
158      * @return the bit mask indicating the highest 1 bit in {@code i}.
159      * @since 1.5
160      */
161     public static int highestOneBit(int i) {
162         i |= (i >> 1);
163         i |= (i >> 2);
164         i |= (i >> 4);
165         i |= (i >> 8);
166         i |= (i >> 16);
167         return (i & ~(i >>> 1));
168     }
169 
170     /**
171      * Determines the lowest (rightmost) bit of the specified integer that is 1
172      * and returns the bit mask value for that bit. This is also referred
173      * to as the Least Significant 1 Bit. Returns zero if the specified integer
174      * is zero.
175      *
176      * @param i
177      *            the integer to examine.
178      * @return the bit mask indicating the lowest 1 bit in {@code i}.
179      * @since 1.5
180      */
lowestOneBit(int i)181     public static int lowestOneBit(int i) {
182         return (i & (-i));
183     }
184 
185     /**
186      * Determines the number of leading zeros in the specified integer prior to
187      * the {@link #highestOneBit(int) highest one bit}.
188      *
189      * @param i
190      *            the integer to examine.
191      * @return the number of leading zeros in {@code i}.
192      * @since 1.5
193      */
numberOfLeadingZeros(int i)194     public static int numberOfLeadingZeros(int i) {
195         i |= i >> 1;
196         i |= i >> 2;
197         i |= i >> 4;
198         i |= i >> 8;
199         i |= i >> 16;
200         return bitCount(~i);
201     }
202 
203     /**
204      * Determines the number of trailing zeros in the specified integer after
205      * the {@link #lowestOneBit(int) lowest one bit}.
206      *
207      * @param i
208      *            the integer to examine.
209      * @return the number of trailing zeros in {@code i}.
210      * @since 1.5
211      */
numberOfTrailingZeros(int i)212     public static int numberOfTrailingZeros(int i) {
213         return bitCount((i & -i) - 1);
214     }
215 
216     /**
217      * Counts the number of 1 bits in the specified integer; this is also
218      * referred to as population count.
219      *
220      * @param i
221      *            the integer to examine.
222      * @return the number of 1 bits in {@code i}.
223      * @since 1.5
224      */
bitCount(int i)225     public static int bitCount(int i) {
226         i -= ((i >> 1) & 0x55555555);
227         i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
228         i = (((i >> 4) + i) & 0x0F0F0F0F);
229         i += (i >> 8);
230         i += (i >> 16);
231         return (i & 0x0000003F);
232     }
233 
234     /**
235      * Rotates the bits of the specified integer to the left by the specified
236      * number of bits.
237      *
238      * @param i
239      *            the integer value to rotate left.
240      * @param distance
241      *            the number of bits to rotate.
242      * @return the rotated value.
243      * @since 1.5
244      */
rotateLeft(int i, int distance)245     public static int rotateLeft(int i, int distance) {
246         if (distance == 0) {
247             return i;
248         }
249         /*
250          * According to JLS3, 15.19, the right operand of a shift is always
251          * implicitly masked with 0x1F, which the negation of 'distance' is
252          * taking advantage of.
253          */
254         return ((i << distance) | (i >>> (-distance)));
255     }
256 
257     /**
258      * Rotates the bits of the specified integer to the right by the specified
259      * number of bits.
260      *
261      * @param i
262      *            the integer value to rotate right.
263      * @param distance
264      *            the number of bits to rotate.
265      * @return the rotated value.
266      * @since 1.5
267      */
rotateRight(int i, int distance)268     public static int rotateRight(int i, int distance) {
269         if (distance == 0) {
270             return i;
271         }
272         /*
273          * According to JLS3, 15.19, the right operand of a shift is always
274          * implicitly masked with 0x1F, which the negation of 'distance' is
275          * taking advantage of.
276          */
277         return ((i >>> distance) | (i << (-distance)));
278     }
279 
280     /**
281      * Reverses the order of the bytes of the specified integer.
282      *
283      * @param i
284      *            the integer value for which to reverse the byte order.
285      * @return the reversed value.
286      * @since 1.5
287      */
reverseBytes(int i)288     public static int reverseBytes(int i) {
289         int b3 = i >>> 24;
290         int b2 = (i >>> 8) & 0xFF00;
291         int b1 = (i & 0xFF00) << 8;
292         int b0 = i << 24;
293         return (b0 | b1 | b2 | b3);
294     }
295 
296     /**
297      * Reverses the order of the bits of the specified integer.
298      *
299      * @param i
300      *            the integer value for which to reverse the bit order.
301      * @return the reversed value.
302      * @since 1.5
303      */
reverse(int i)304     public static int reverse(int i) {
305         // From Hacker's Delight, 7-1, Figure 7-1
306         i = (i & 0x55555555) << 1 | (i >> 1) & 0x55555555;
307         i = (i & 0x33333333) << 2 | (i >> 2) & 0x33333333;
308         i = (i & 0x0F0F0F0F) << 4 | (i >> 4) & 0x0F0F0F0F;
309         return reverseBytes(i);
310     }
311 
312     /**
313      * Returns the value of the {@code signum} function for the specified
314      * integer.
315      *
316      * @param i
317      *            the integer value to check.
318      * @return -1 if {@code i} is negative, 1 if {@code i} is positive, 0 if
319      *         {@code i} is zero.
320      * @since 1.5
321      */
signum(int i)322     public static int signum(int i) {
323         return (i == 0 ? 0 : (i < 0 ? -1 : 1));
324     }
325 
326     /**
327      * Returns a {@code Integer} instance for the specified integer value.
328      * <p>
329      * If it is not necessary to get a new {@code Integer} instance, it is
330      * recommended to use this method instead of the constructor, since it
331      * maintains a cache of instances which may result in better performance.
332      *
333      * @param i
334      *            the integer value to store in the instance.
335      * @return a {@code Integer} instance containing {@code i}.
336      * @since 1.5
337      */
valueOf(int i)338     public static Integer valueOf(int i) {
339         if (i < -128 || i > 127) {
340             return new Integer(i);
341         }
342         return valueOfCache.CACHE [i+128];
343 
344     }
345 
346    static class valueOfCache {
347         /**
348          * <p>
349          * A cache of instances used by {@link Integer#valueOf(int)} and auto-boxing.
350          */
351         static final Integer[] CACHE = new Integer[256];
352 
353         static {
354             for(int i=-128; i<=127; i++) {
355                 CACHE[i+128] = new Integer(i);
356             }
357         }
358     }
359 }
360