Sicher geht das einfacher. Aber daraus lernt man ja nichts.
So wie ich den Algorithmus verstanden habe, wird der Exponent n als Dualzahl interpretiert. Die Prüfung auf ungerade ist der Test, ob an der gerade verarbeiteten Dualstelle des Exponenten eine 1 oder eine 0 steht. Die Division durch zwei wechselt dann zur nächsten Dualstelle. k wird sozusagen bitweise bearbeitet, vom niederwertigsten Bit angefangen.
Ist k zu Anfang ungerade, enthält die Potenz den Fakter x hoch 1, also wird der reinmultipliziert. k wird eventuell vermindert und halbiert, und der Stellenwert der Potenz durch Quadrierung verdoppelt auf x hoch 2. Ob dieser Faktor im Ergebnis enthalten ist, hängt davon ab, ob k jetzt wieder ungerade ist. Beim Beispiel 5 ist k nach dem ersten Durchgang (5-1)/2 = 2, also gerade, damit ist x hoch 2 nicht enthalten. Der "Stellenwert-Faktor" wird wieder quadriert, also x hoch 4, und jetzt ist k wieder ungerade (nämlich 1), also ist x hoch 4 enthalten, und wird reinmultipliziert. Danach ist k Null, und wir sind fertig. Das Ergebnis ist also x hoch 1 mal x hoch 4 gleich x hoch 5.