bit_power(0,[]).
bit_power(Num,[2^Exp|Res]):- Exp is msb(Num),             %hier etwas gecheatet
                             NewNum is Num >< (1<<Exp),   %performanter Weg wäre
                             bit_power(NewNum,Res),!.     %aber aufwendiger umzusetzen

%zusammenfassen, da bei der "Multiplikation" auch
%[2^4, 2^2, 2^3, 2^1, 2^2, 2^0] als Ergebnis auftreten kann
trans([],[]).
trans([X],[X]).
trans([2^X,2^X|T],[2^Y|Res]):-Y is X+1,trans(T,Res),!.
trans([X,Y|T],[X|Res]):- X\=Y,trans([Y|T],Res),!.

transform(ExpList,Result):-msort(ExpList,Sorted),
                           trans(Sorted,Trans),
                           Sorted\=Trans,
                           transform(Trans,Result),!.
transform(Result,Result).
%'Kreuzaddition'
mul_exps(ExpList1,ExpList2,Res):-
        findall(2^ExpSum,(
                           member(2^Exp1,ExpList1),
                           member(2^Exp2,ExpList2),
                           ExpSum is Exp1+Exp2
                         ),Sums),
        transform(Sums,Trans),
        sort(Trans,Sorted),reverse(Sorted,Res).

cmp_pow([2^Exp1|_],[2^Exp2|_]):- Exp1<Exp2,!.             %ist ein Exponent kleiner =>fertig
cmp_pow([2^Exp1],[2^Exp2|T]):- T\=[],Exp1=:=Exp2,!.       %mehr Exponenten vorhanden =>eher größer
cmp_pow([2^Exp1|List1],[2^Exp2|List2]):- Exp1=:=Exp2,
                  cmp_pow(List1,List2),!.

compare(X*Y<Z):- bit_power(X,XBit),write(X=XBit),nl,
                 bit_power(Y,YBit),write(Y=YBit),nl,
                 bit_power(Z,ZBit),write(Z=ZBit),nl,
                 mul_exps(XBit,YBit,Mul),write(X*Y=Mul),nl,
                 cmp_pow(Mul,ZBit).

7 ?- compare(7*5<35).
7=[2^2, 2^1, 2^0]
5=[2^2, 2^0]
35=[2^5, 2^1, 2^0]
7*5=[2^5, 2^1, 2^0]
false.

8 ?- compare(7*5<36).
7=[2^2, 2^1, 2^0]
5=[2^2, 2^0]
36=[2^5, 2^2]
7*5=[2^5, 2^1, 2^0]
true.

9 ?- compare(71*35<36).
71=[2^6, 2^2, 2^1, 2^0]
35=[2^5, 2^1, 2^0]
36=[2^5, 2^2]
71*35=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^0]
false.

10 ?- X is 71*35.
X = 2485.

11 ?- compare(71*35<2485).
71=[2^6, 2^2, 2^1, 2^0]
35=[2^5, 2^1, 2^0]
2485=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^0]
71*35=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^0]
false.

12 ?- compare(71*35<2486).
71=[2^6, 2^2, 2^1, 2^0]
35=[2^5, 2^1, 2^0]
2486=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^1]
71*35=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^0]
true.