getChar函數如何工作？

Question

private static char[] getChars(int i) { 
    char buf[] = new char[32]; 
    int q; 
    for (int j = 31; j >= 0; j--) { 
     q = (i * 52429) >>> (19); 
     int r = i - ((q << 3) + (q << 1)); 
     buf[j] = (char) (r + '0'); 
     i = q; 
     if (i == 0) 
      break; 
    } 

return buf; 
} 

上述代碼基於java.lang.Integer.getChars（int）的一部分。開發者是如何拿出這個「神奇」數字52429的。它背後的數學是什麼？在81920作爲輸入後，此功能不起作用。爲什麼這個幻數只適用於一定範圍的輸入？

Answer 1

如果你搜索的源代碼，你會發現這個數字的第二個實例：

// I use the "invariant division by multiplication" trick to 
// accelerate Integer.toString. In particular we want to 
// avoid division by 10. 
// 
// The "trick" has roughly the same performance characteristics 
// as the "classic" Integer.toString code on a non-JIT VM. 
// The trick avoids .rem and .div calls but has a longer code 
// path and is thus dominated by dispatch overhead. In the 
// JIT case the dispatch overhead doesn't exist and the 
// "trick" is considerably faster than the classic code. 
// 
// TODO-FIXME: convert (x * 52429) into the equiv shift-add 
// sequence. 
// 
// RE: Division by Invariant Integers using Multiplication 
//  T Gralund, P Montgomery 
//  ACM PLDI 1994 
// 

所以，回答你的問題可以在書Division by Invariant Integers using Multiplication用T Gralund，P蒙哥馬利發現。