How to understand the math formula of mod calculation which cause ArrayIndexOutOfBoundsException?

Question

[add] This is not an issue about ArrayIndexOutOfBoundsException purely, it's about the reminder calculation algorithms, please don't marked it as duplicated.

The phone throws ArrayIndexOutOfBoundsException, here is the log:

java.lang.ArrayIndexOutOfBoundsException: length=36; index=120 at java.lang.IntegralToString.convertInt(IntegralToString.java:234) at java.lang.IntegralToString.appendInt(IntegralToString.java:173) at java.lang.StringBuilder.append(StringBuilder.java:139) at android.telephony.SignalStrength.toString(SignalStrength.java:1123) at com.android.internal.telephony.ServiceStateTracker.onSignalStrengthResult(ServiceStateTracker.java:958) at

The exception occurs at

buf[--cursor] = DIGITS[r];

My question is how to understand the code such as

int q = (int) ((0x51EB851FL * i) >>> 37);

and

int q = (0xCCCD * i) >>> 19;

[delete]Why not int q = i / 10; int r = i - 10*q;

[add]why int q = (0xCCCD * i) >>> 19; is equivalent to int q = i / 10;

How r can be 120 according to the comments about the algorithms above if they are correct.

below are the relevant codes:

private static final char[] TENS = {
    '0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
    '1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
    '2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
    '3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
    '4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
    '5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
    '6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
    '7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
    '8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
    '9', '9', '9', '9', '9', '9', '9', '9', '9', '9'
};

/** Ones [i] contains the tens digit of the number i, 0 <= i <= 99. */
private static final char[] ONES = {
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
};
/**
 * The digits for every supported radix.
 */
private static final char[] DIGITS = {
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
    'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
    'u', 'v', 'w', 'x', 'y', 'z'
};

/**
     * Returns the string representation of i and leaves sb alone if sb is null.
     * Returns null and appends the string representation of i to sb if sb is non-null.
     */
    private static String convertInt(AbstractStringBuilder sb, int i) {
        boolean negative = false;
        String quickResult = null;
        if (i < 0) {
            negative = true;
            i = -i;
            if (i < 100) {
                if (i < 0) {
                    // If -n is still negative, n is Integer.MIN_VALUE
                    quickResult = "-2147483648";
                } else {
                    quickResult = SMALL_NEGATIVE_VALUES[i];
                    if (quickResult == null) {
                        SMALL_NEGATIVE_VALUES[i] = quickResult =
                                i < 10 ? stringOf('-', ONES[i]) : stringOf('-', TENS[i], ONES[i]);
                    }
                }
            }
        } else {
            if (i < 100) {
                quickResult = SMALL_NONNEGATIVE_VALUES[i];
                if (quickResult == null) {
                    SMALL_NONNEGATIVE_VALUES[i] = quickResult =
                            i < 10 ? stringOf(ONES[i]) : stringOf(TENS[i], ONES[i]);
                }
            }
        }
        if (quickResult != null) {
            if (sb != null) {
                sb.append0(quickResult);
                return null;
            }
            return quickResult;
        }

        int bufLen = 11; // Max number of chars in result
        char[] buf = (sb != null) ? BUFFER.get() : new char[bufLen];
        int cursor = bufLen;

        // Calculate digits two-at-a-time till remaining digits fit in 16 bits
        while (i >= (1 << 16)) {
            // Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8
            int q = (int) ((0x51EB851FL * i) >>> 37);
            int r = i - 100*q;
            buf[--cursor] = ONES[r];
            buf[--cursor] = TENS[r];
            i = q;
        }

        // Calculate remaining digits one-at-a-time for performance
        while (i != 0) {
            // Compute q = n/10 and r = n % 10 as per "Hacker's Delight" 10-8
            int q = (0xCCCD * i) >>> 19;
            int r = i - 10*q;
            buf[--cursor] = DIGITS[r];
            i = q;
        }

        if (negative) {
            buf[--cursor] = '-';
        }

        if (sb != null) {
            sb.append0(buf, cursor, bufLen - cursor);
            return null;
        } else {
            return new String(cursor, bufLen - cursor, buf);
        }
    }

As for your other question: **Why not int q = i / 10; int r = i - 10*q;**, bit shift operations are usually (?) faster. But the compiler knows better if it should do a multiplication in bit shifts or do something else. So, it's best to leave it on the compiler the assembly implementation. Therefore, if you need to multiply then use multiplication, if you need to divide then use division, and not do bit shifts — denvercoder9, Dec 21 '16 at 08:18
I really dont get your question. Are you asking why **your** mod computations lead to that exception? Or are you asking **two** completely independent things here?! — GhostCat, Dec 21 '16 at 08:21
I just can understand why use such kind of formula "int q = (0xCCCD * i) >>> 19;" which it is not intuitive and hard to understand what it does and whether it does correctly. — Saint, Dec 21 '16 at 11:14
The comment on the code indicates is been lifted from the book "Hackers Delight". This is a book mainly about very low level arithmetic optimisation the kind of thing only assembly language programmers should read - I love it! One of the tricks is to save the cost of doing an expensive integer division by using multiplication and shift operations. This is black magic and should be avoided. It makes opaque code and the only place it should ever appear is in a known bottleneck in high-performance code, like Doom's rendering engine. — Salix alba, Dec 22 '16 at 12:36
To understand the code int q = (int) ((0x51EB851FL * i) >>> 37) first note that 0x51EB851FL = 1374389535 in decimal and >>> 37 is equivalent to dividing by 2^37 = 137438953472. So the combined operation is the same as multiplying by 0.010000000002037268, very roughly 1/100. The error is in the order of 10^10 and for reasonable size numbers will be equivalent. If we do the calculation using long the first error occurs at i = 4908534099 which > 2^32. So it works for all positive ints. — Salix alba, Dec 22 '16 at 15:29
Thanks, get it. Really magic. Why not post in answer, I can accept your answer. — Saint, Dec 23 '16 at 06:21

score 1 · Answer 1 · answered Dec 21 '16 at 08:37

int q = (int) ((0x51EB851FL * i) >>> 37);

0x at the beginning of number means that the number is written in a hexadecimal representation

L at the end of number means that the number is Long-typed. Thats why (int) cast used.

>>>37 means that the binary representation of the number at the left side from this expression should be shifted to the right 37 times. For example:

16 >>> 2
16 in binary is 10000.
shift it to the right 2 times, we got 100.00
100 in decimal system is equal to 4.
16 >>> 2 = 4.

Same about int q = (0xCCCD * i) >>> 19;
Why not int q = i / 10; int r = i - 10q;

IMO shifting of hexademical numbers is much more quickly and more precisely than dividing.

How r can be 120 according to the comments about the algorithms above if they are correct.

I'm pretty sure you could simply debug it in your IDE in order to get the answer.

1. I just can't understand why they are equivalent that int q = (0xCCCD * i) >>> 19; and int q = i / 10; 2. This issue can't replicated at present, and I have written a demo to invoke the algorithm, the reminder less 10 always. So I am so confused. — Saint, Dec 21 '16 at 09:01

How to understand the math formula of mod calculation which cause ArrayIndexOutOfBoundsException?

1 Answers1