Berechnen der Anzahl der Bits und der Anzahl der Wörter BigInteger

Question

Beim Konvertieren einer String in BigInteger berechnet Java intern die Anzahl der Bits und dann die Anzahl der Wörter (jedes Wort ist eine Gruppe von 9 ganzen Zahlen, denke ich) in einem BigInteger gesehen here von der Linie 325 zur Linie 327. numWords verwendet wird dann ein Array zu erstellen, empfangen kann, dass BigInteger.

ich nicht die Logik verstehen verwendet für numBits in Zeile 325 zu berechnen und dann die Logik für numWords in Zeile 326.

Logisch denke ich, dass für die Zeichenfolge "123456 789 ", numWords sollte 1 sein und für" 12345678912 ", sollte 2 sein, aber das ist nicht immer der Fall. Zum Beispiel für "12345678912345678912", numWords sollte 3 sein, aber es kommt heraus, um 2 zu sein.

Kann jemand bitte die in Zeile 325 und 326 verwendete Logik erklären?

Answer 1

Um Dezimalzahl von numDigits als binäre Zahl darstellen, bedarf es

numDigits * Math.log(10)/Math.log(2) 

Bits.

int numBits = (int)(((numDigits * bitsPerDigit[radix]) >>> 10) + 1); 

Bei der Berechnung oben bitsPerDigit[10] ist 3402.

Math.log(10)/Math.log(2) * Math.pow(2, 10) = 3401.6543691646593 

Answer 2

Wörter beziehen sich nicht auf Wörter, wie Sie es kennen - es bezieht sich auf Wörter als Speicherblöcke.

https://en.wikipedia.org/wiki/Word_(computer_architecture)

Answer 3

In Java werden BigIntegers nicht als Strings oder Bytes mit jeweils einer Ziffer gespeichert. Sie werden als ein Array von 32-Bit-Ganzzahlen gespeichert, die zusammen die sogenannte Größe des BigIntegers bilden. Es kann keine führenden ganzen Zahlen (*) geben, daher wird der BigInteger so kompakt wie möglich gespeichert.

Die "Wörter" sind diese 32-Bit-Ganzzahlen. Sie sind keine Gruppen von 9 Ziffern, sie werden vollständig verwendet, also zählt jedes Bit.

Also müssen Sie nur wissen, wie viele 32-Bit-Integer gespeichert sind, das ist die Länge des internen Arrays mal 32. Aber die obere ganze Zahl kann noch führende Nullen haben, also müssen Sie die Anzahl der führenden Nullen erhalten dass Spitzen integer und subtrahieren sie von dem erhaltenen Produkt, in Pseudo-Code:

numBits = internalArray.length * 32 - numberOfLeadingZeroBits(internalArray[0]); 

Hinweis, dass die interne Anordnung wird mit der Oberseite integer an der niedrigsten Adresse (I keine Ahnung, warum das so ist) gespeichert, so dass die Die oberste Ganzzahl befindet sich im Index 0 des Arrays.

---

(*) In Wirklichkeit ist die oben etwas komplizierter ist, da das oberste Element aus dem Anfang des Arrays versetzt an einem gespeichert werden (wahrscheinlich bestimmte Berechnungen einfacher zu machen), sondern zu verstehen, die Mechanismus können Sie so tun, als gäbe es keine zusätzlichen ganzen Zahlen.