Implementation der <= Relation
-
warum nicht
return x<=y;
Was überseeh ich da?
-
v schrieb:
warum nicht
return x<=y;
Was überseeh ich da?
User1291 schrieb:
[*]nur folgende Operationen: ! ~ & ^ | + << >>
-
gelöscht
-
x <= y genau dann, wenn x - y <= 0
x - y kannst Du schreiben als x + (-y)
Und -y kannst Du mit ~ und + implementieren.
-
Ok, jetzt komm ich mir doof vor:
int isLessOrEqual(int x, int y) { int xSgn, ySgn, diffSgn; xSgn = (x >> 31) & 0x1; ySgn = (y >> 31) & 0x1; diffSgn = !(((y+(~x+1)) >> 31) & 0x1); return !!( (!(x ^ y)) + (xSgn & !ySgn) + ((!(xSgn | ySgn)) & diffSgn) + ((xSgn & ySgn) & diffSgn) ); }Funktioniert. Hab ein ! beim
+ ((!(xSgn | ySgn)) & !diffSgn)vergessen. -.-
Na ja, wenn jemand von euch die Herausvorderung sucht, versucht's mal in 11 oder weniger Operationen.
Ich, jedenfalls, werd mich damit zufrieden geben, dass das hier läuft.
-
SG1 schrieb:
x <= y genau dann, wenn x - y <= 0
x - y kannst Du schreiben als x + (-y)
Und -y kannst Du mit ~ und + implementieren.
Dem stimme ich nicht zu.
Was passiert bspw., wenn ich
x = INT_MIN
y = 0x1wähle?
-
User1291 schrieb:
Ich hatte eigentlich gehofft, dies wäre nicht nötig, aber...
Ich soll eine Funktion implementieren, welche entscheidet, ob für zwei 32bit 2's complement Integer x,y gilt: x <= y und 1 zurückgibt, falls dies der Fall ist, und 0, wenn dem nicht so ist.Klingt simpel, oder?
Allerdings wird das ganze an ein paar Auflagen geknüpft:- keine Konstanten kleiner 0 oder grösser 0xFF
- keine globale Variabeln
- keine Funktionsaufrufe
- keine Macros
- keine Kontrollstruktionen (if, do, while, for, switch, ...)
- kein Casting irgendwelcher Form
- nur folgende Operationen: ! ~ & ^ | + << >>
- höchstens 24 solche Operationen
Wir dürfen annehmen, dass die Maschine arithmetisch schiftet.
Mein Versuch sieht momentan folgendermassen aus:
int isLessOrEqual(int x, int y){ int xSgn, ySgn, diffNeg; xSgn = (x >> 31) & 0x1; ySgn = (y >> 31) & 0x1; diffSgn = (((y+(~x+1)) >> 31) & 0x1); return !!( (!(x ^ y)) + ((!(xSgn ^ 0x1)) & !ySgn) + ((!(xSgn | ySgn)) & diffSgn) + ((xSgn & ySgn) & !diffSgn) ); }Das braucht nicht nur zuviele Operationen (26), es ist auch noch falsch (oder zumindest nicht richtig genug).
Die Schwierigkeit liegt offensichtlich beim Berücksichtigen des Overflows.Was ich mir dabei gedacht hab ist, dass ich ja im Prinzip folgende Funktionalität will:
if(x == y) return 1; else if(xSgn = 1 && ySgn = 0) return 1; else if((xSgn == 0 && ySgn == 0) return ((y-x) >> 31) & 0x1; else if(xSgn == 1 && ySgn == 1); return !(((y-x) >> 31) & 0x1); else return 0;Aber anscheindend bin ich nicht fähig, das akkurat zu übersetzen.
Seh den Fehler beim besten Willen nicht. Könnt mir wohl bitte wer sagen, was ich falsch mache?
Sitze jetzt drei Tage an der bescheuerten Aufgabe und alles, was ich bisher versucht hab, hat entweder nicht funktioniert oder zuviele Operationen benötigt.
Mir reichts langsam.EDIT
Hab das ganze auf 24 OPs runter gebracht. (Was an der (Nicht-)Korrektheit noch nichts ändert.)int isLessOrEqual(int x, int y) { int xSgn, ySgn, diffSgn; xSgn = (x >> 31) & 0x1; ySgn = (y >> 31) & 0x1; diffSgn = (((y+(~x+1)) >> 31) & 0x1); return !!( (!(x ^ y)) + (xSgn & !ySgn) + ((!(xSgn | ySgn)) & diffSgn) + ((xSgn & ySgn) & !diffSgn) ); }Ein paar Testcases, wo es zum Beispiel nicht funktioniert:
x = 0x1, y = 0x0, output: 1, sollte: 0
x = 0x0, y = 0x1, output: 0, sollte: 1
x = 0x4c6690e6, y = 0x1, output: 1, sollte: 0
x = 0x7ffffffe, y = 0xdd0f99a, output 1, sollte: 0Wenn ihr mehr solche falsche Ausgaben braucht, kein Problem, hab noch derer 88 weitere. -.-
EDIT
Ok, jetzt komm ich mir doof vor:int isLessOrEqual(int x, int y) { int xSgn, ySgn, diffSgn; xSgn = (x >> 31) & 0x1; ySgn = (y >> 31) & 0x1; diffSgn = !(((y+(~x+1)) >> 31) & 0x1); return !!( (!(x ^ y)) + (xSgn & !ySgn) + ((!(xSgn | ySgn)) & diffSgn) + ((xSgn & ySgn) & diffSgn) ); }Funktioniert. Hab ein ! beim
+ ((!(xSgn | ySgn)) & !diffSgn)vergessen. -.-
Na ja, wenn jemand von euch die Herausvorderung sucht, versucht's mal in 11 oder weniger Operationen.
Ich, jedenfalls, werd mich damit zufrieden geben, dass das hier läuft.was sollen eigentlich die bitschubs-spielchen?
-
User1291 schrieb:
SG1 schrieb:
x <= y genau dann, wenn x - y <= 0
x - y kannst Du schreiben als x + (-y)
Und -y kannst Du mit ~ und + implementieren.
Dem stimme ich nicht zu.
Was passiert bspw., wenn ich
x = INT_MIN
y = 0x1wähle?
Achso, solche Späße sollen auch berücksichtigt werden? Stimmt, dann wird's komplizierter. Aber Du scheinst ja eine funktionierende Lösung zu haben
-
Hier mit 14 Operationen:
int loe(unsigned x, unsigned y) { int hx = x >> 16, hy = y >> 16, h = !(hx ^ hy); return (!h & ((hx + ~hy)>>31)) | (h & (x + ~ y)>>31); }Idee ist, den Trick von SG1 auf die höchsten 16 Bit und die tiefsten 16 Bit anzuwenden um den Over-/Underflow zu vermeiden.
-
bitschuppser schrieb:
Hier mit 14 Operationen:
int loe(unsigned x, unsigned y) { int hx = x >> 16, hy = y >> 16, h = !(hx ^ hy); return (!h & ((hx + ~hy)>>31)) | (h & (x + ~ y)>>31); }Idee ist, den Trick von SG1 auf die höchsten 16 Bit und die tiefsten 16 Bit anzuwenden um den Over-/Underflow zu vermeiden.
Ich hab das mal durch unsere Testcases gejagt und entweder hab ich den Algorithmus falsch abgetippt oder aber er ist nicht ganz korrekt.
Das hier hab ich eingetippt:int isLessOrEqual(int x, int y) { unsigned int ux, uy; int hx, hy, h; ux = x; uy = y; hx = ux >> 16; hy = uy >> 16; h = !(hx ^hy); return ((!h) & ((hx + ~hy)>>31)) | (h & ((x + ~y)>>31)); }Ein paar Beispiele, wo das nicht zu funktionieren scheint:
(1[0x1],-2[0xfffffffe]) , (output 1, sollte 0) ([0x7ffffffb],[0x7ffffffb]), (output 0, sollte 1) ([0x6961b8a2],[0x80000004]), (output 1, sollte 0) ([0x80000004],[0x7fffffff]), (output 0, sollte 1)Magst du vielleicht deine Idee etwas ausführlicher erläutern?