BigInteger gemeinsame Prefix auf Basis b errechnen

[tyvan]

Hi Leutz,

ich habe hier recht schwerwiegende Perfomanzprobleme mit einem Programm von mir.

Dabei nutze ich den BigInteger um sehr grosse Nummern (128-160 Bit) zu speichern.
Wichtig ist dabei der Prozess der gemeinsamen Prefixlänge von zwei Nummern A und B.
Ich möchte immer zu einer gegebenen Basis b die gemeinsame Prefixlänge errechnen.

Beispiel:
A ist 3D5A10
B ist 3DA201
Beiden Nummern sind offensichtlich in der Basis 16, also HEX.
Wie man sieht sind die ersten beiden Zeichen 3 und D gleich, also ist die gemeinsame Prefixlänge gleich 2.

Wie kann ich nun effizient mit BigInteger dies errechnen?

Ein Weg wäre die toString(int radix) Methode von BigInteger. Aber die soll angeblich sehr schlecht sein.
BigInteger bietet ja Bitoperationen.

Weiss einer wie man die Prefixlänge in einer gegebenen Basis b zwischen zwei Nummern errechnet.
Wäre sehr dankbar.

 

[zeja]

Musst du mal testen ob sowas immer das richtige Ergebnis liefert:

	public static void main(String[] args) {
		// 4 bit in binär entsprechen einer hexzahl
		final int grpBits = 4;

		BigInteger bint1 = new BigInteger("3D5A10", 16);
		BigInteger bint2 = new BigInteger("3DA201", 16);

		System.out.println(bint1.bitLength( ) + " " + bint1.toString(2));
		System.out.println(bint2.bitLength( ) + " " + bint2.toString(2));

		if (bint1.bitLength( ) != bint2.bitLength( )) {
			System.out.println("No common prefix.");
			return;
		}

		int cnt = bint1.bitLength( );

		int falseBit = -1;
		for (int i = cnt; i >= 0; i--) {
			if (!bint1.testBit(i) == bint2.testBit(i)) {
				falseBit = i;
				break;
			}
		}

		if (cnt % grpBits != 0) {
			cnt = ((cnt / grpBits) + 1) * grpBits;
		}

		if (falseBit == -1) {
			System.out.println("Prefix = " + cnt / grpBits);
		}
		else {

			System.out.println("Prefix = " + (cnt - falseBit - 1) / grpBits);
		}
	}

 

[Anime-Otaku]

Ich bin zwar kein Mathematiker, aber wenn man nur testen muss wie viel Zeichen am Anfang gleich sind, wäre da nicht ein Charweiser-Vergleich des Hexes als char[] bzw. String schneller?