Probleme mit den Shift-Operatoren

[buddahbrot]

Hallo,

hier ist mal wieder ein Java-Anfänger der Hilfe sucht

Also, folgende Aufgabenstellung:

Es geht um das "schnelle Potenzieren", siehe auch Binäre Exponentiation ? Wikipedia
Im Grunde geht man dabei folgendermaßen vor:
1. den Exponenten als Binärzahl hinschreiben
2. die Variable result gleich x (der Basis der zu berechnenden Potenz) setzen
3. ab der ersten Eins an Bit für Bit auslesen
a) falls das Bit = 1 ist, result = result*result (also result quadriert)
b) falls das Bit = 0 ist, result = result*x

Man soll nun eine Methode erstellen, die die Potenz berechnet. Problem dabei: es dürfen innerhalb der Methode keine weiteren Methoden aufgerufen werden.

Soweit bin ich bis jetzt gekommen:

public class Potenzieren {
	
	public static long potenziere(int x, int n, int k) {
		long result = x;  // entspricht zu diesem Zeitpunkt dem x_0 (siehe Angabe)
		int verschiebung = 32-k;
		n = n << verschiebung;
		//System.out.println(n);
		for (int i=0; i<k; i++) {
			if (n>0) {
				result = result * result;
			}
			else {
				result = result * x;
			}

			n = n << 1;
			//System.out.println(n);
			//System.out.println(result);
		}
		
		return result;   // soll hier dem Endergebnis x_k (siehe Angabe) entsprechen
	}
	
	public static void main(String[] args) {
		int x = Integer.parseInt(args[0]);
		int n = Integer.parseInt(args[1]);
		int k = Integer.SIZE - Integer.numberOfLeadingZeros(n) - 1;
		System.out.println(x + " hoch " + n + " ergibt " + potenziere(x, n, k));
	}
	
}

Mein Ansatz wäre, dass man die Binärzahl soweit verschiebt, dass die erste Eins auf Bit 1 von 32 liegt. Dann wird angefangen auszulesen, ob die Zahl positiv oder negativ ist, da das erste Bit ja das Vorzeichen der Zahl angibt.

In der jetzigen Form wirft mir das Programm recht schnell n=0 hin, obwohl die Binärzahl noch nicht komplett durchgeschoben wurde.

Sieht jemand einen groben Fehler oder hat jemand Tips für mich?

Viele Grüße,

 

[Marco13]

Was soll denn das k da? Das ganze bezieht sich wohl nur auf positive Exponenten, negative machen da nicht viel sinn. Und selbst wenn, wäre ein if (n<0) doch auch einfacher...

 

[buddahbrot]

Die Main-Methode wurde vorgegeben, das k ist die Anzahl der Stellen, die n in der Binärdarstellung lang ist.

Und ja, das ganze bezieht sich nur auf pos. Exponenten

 

[Marco13]

Aber... man braucht das k doch nicht? Ich kapier's nicht ???:L

 

[buddahbrot]

Es ist so:

die int-Zahlen sind in Java doch 32-Bit lang, wovon das Erste Bit das Vorzeichen (+ oder -) ist.
Innerhalb der Methode verschiebe ich zuerst die Bits nach links, sodass die erste Eins der Binärdarstellung von n auf dem Bit des Vorzeichens steht. Dann wird in der For-Schleife immer erst geprüft ob das erste Bit und damit die ganze Zahl positiv oder negativ ist und am Ende n nochmals um 1 Bit nach links geschoben.

 

[Marco13]

Ahhh... äh... so halb hab' ich's glaubich verstanden: Du machst das andersrum (und falschrum!?). Man kann mit
if ((n&1)==1) { ... }
testen, ob das linkeste Bit gesetzt ist...

 

[SlaterB]

einfach an die korrekte Formel von Wikipedia halten, quadriert wird immer, multlipliziert nur im negativen Fall,
dein else enthielt auch 0

        for (int i = 0; i < k; i++)
        {
            result = result * result;
            if (n < 0)
            {
                result = result * x;
            }

 

[buddahbrot]

Super, jetzt passt, vielen Dank dafür

Wen es interessiert, hier der richtige Code:

public class Potenzieren {
	
	public static long potenziere(int x, int n, int k) {
		long result = x;  // entspricht zu diesem Zeitpunkt dem x_0 (siehe Angabe)
		int verschiebung = 32-k;
		if (n==0) {
			result = 1;
			return result;
		}
		else {n = n << verschiebung;
		//System.out.println(n);
        for (int i = 0; i < k; i++)
        {
            result = result * result;
            if (n < 0)
            {
                result = result * x;
            }

			n = n << 1;
			//System.out.println(n);
			//System.out.println(result);
		}
		
		return result;   // soll hier dem Endergebnis x_k (siehe Angabe) entsprechen
	}
	}
	
	public static void main(String[] args) {
		int x = Integer.parseInt(args[0]);
		int n = Integer.parseInt(args[1]);
		int k = Integer.SIZE - Integer.numberOfLeadingZeros(n) - 1;
		System.out.println(x + " hoch " + n + " ergibt " + potenziere(x, n, k));
	}
	
}