Kleiner Coding-Contest
-
Was ist die effizienteste Methode um zu prüfen ob zwei 32-Bit words jeweils genau ein Bit gesetzt haben, und diese Bits verschieden sind?
-
Wie können zwei gesetzte Bits verschieden sein?
Ansonsten Google "c++ bit vergleich"
-
Helmut.Jakoby schrieb:
Wie können zwei gesetzte Bits verschieden sein?
001000 010000Siehst du den Unterschied?
Damit wird dein Tip auch wertlos.
-
in 4 bytes teilen, da kann man viel schneller drüber checken. und den bit vergleich musst du dann nur noch auf den 8 bit des bytes machen und in vielen situationen weisst du ja anhand der bytes schon dass nicht das gleiche bit oder mehr als 1 bit gesetzt ist.
-
Helmut.Jakoby schrieb:
Wie können zwei gesetzte Bits verschieden sein?
4 und 8 haben je nur ein Bit gesetzt, aber nicht das selbe Bit.
EDIT: OK, zu langsam.
-
Mit
a!=0 && (a & (a-1))==0muesste man schnell ueberpruefen koennen, ob genau ein bit gesetzt ist (nur kurze Ueberlegung, bitte um Bestaetigung).
Dann muss man noch ueberpruefen, ob die integer verschieden sind. Da es bitwise gemacht wird, kann, koennte man es mit (a & b)==0 schneller machen. Ich bin mir nicht sicher, ob die Compileroptimierer das selber koennen.
-
bitte um Bestaetigung
Ja, das funktioniert.
Die erste funktionierende Lösung die mir eingefallen ist:
unsigned u = 0b00000000000000000000000000000000, v = 0b00000000000000010000000000000000; bool B = !(u & (u - 1)) && !(v & (v - 1)) && u != v && u && v;Ist das aber wirklich schon die effizienteste Lösung? Kann ich gar nicht fassen.
-
Durch die Wahl geeigneter Befehle, kann der compiler noch viele der Berechnungen in einem Schritt erledigen. Z.B. kann er statt expliziter ueberpruefung, ob die Zahl 0 ist, auch nachschauen, ob es in der Subtraktion einen ueberlauf gab.
Ich komme auf 16 Assemblerbefehle, die meisten davon auch nur sehr schnelle Bitvergleiche.
; parameter1: eax, parameter2: ebx mov ecx, eax sub eax, 1 jo RET_FALSE ; jump if overflow test eax, ecx ; bitwise compare jnz RET_FALSE ; jump if not zero mov ecx, ebx sub ecx, 1 jo RET_FALSE ; jump if overflow test ebx, ecx jnz RET_FALSE ; jump if not zero test eax, ebx ; bitwise and jnz RET_FALSE mov eax, 1 retn RET_FALSE: mov eax, 0 retnmacht 38 bytes binary
Vielleicht bekommt man es durch anderen Befehl, andere Registerwahl oder andere Reihenfolge noch ein bisschen schneller, aber ich bezweifel, dass man wirklich weniger schafft.
Nur die vielen Spruenge stoeren vielleicht, wenn die Branch-Prediction falsch liegt.
-
Und wie kann man damit jetzt was hacken?
-
Und wie kann man damit jetzt was hacken?
In die Eingabeaufforderung eingeben.
-
@Marthog
Ich denke das erstesub eax, 1solltesub ecx, 1heissen -- so wie im 2. Block halt auch.
Sonst vergleicht dastest eax, ebxzum Schluss die falschen Werte.Und wieso
test eax, ebxzum Schluss und nichtcmpbzw.sub? Isttestin so einem Fall schneller?EDIT: Grammatik + Tippfehler.
-
ps: Compiler sind schlauer als Menschen
bool foo(unsigned u, unsigned v) { return !(u & (u - 1)) && !(v & (v - 1)) && u != v && u && v; } // EDIT: Unsinn. Mein misglückter Versuch den Trick den Marthog in seinem Assembler-Beispiel verwendet hat in C++ nachzubilden. // Mit dem Hintergedanken dass ein C++ Compiler dadurch vielleicht besseren Code erzeugen könnte. // Funktioniert aber eben nur wenn u und v beide >= 0 sind, d.h. das MSB nicht verwendet wird. // => Nicht weiter beachten. bool bar(int u, int v) { int temp1 = u - 1; int temp2 = v - 1; return temp1 >= 0 && !(temp1 & u) //EDIT: (temp1 & u) => !(temp1 & u) && temp2 >= 0 && !(temp2 & v) //EDIT: (temp2 & v) => !(temp2 & v) && u != v; }GCC 4.9:
foo(unsigned int, unsigned int): leal -1(%rdi), %edx xorl %eax, %eax testl %edi, %edx jne .L2 leal -1(%rsi), %edx testl %esi, %edx jne .L2 cmpl %esi, %edi setne %dl testl %edi, %edi setne %al andl %edx, %eax testl %esi, %esi setne %dl andl %edx, %eax .L2: rep ret bar(int, int): movl %edi, %edx xorl %eax, %eax subl $1, %edx js .L7 leal -1(%rsi), %ecx testl %edi, %edx sete %dl movl %ecx, %eax notl %eax shrl $31, %eax andb %dl, %al je .L7 testl %esi, %ecx sete %dl cmpl %esi, %edi setne %al andl %edx, %eax .L7: rep retNur zwei bedingte Sprünge, booyah!
Clang 3.4.1
foo(unsigned int, unsigned int): # @foo(unsigned int, unsigned int) leal -1(%rdi), %eax testl %edi, %eax jne .LBB0_3 leal -1(%rsi), %eax testl %esi, %eax je .LBB0_2 .LBB0_3: xorl %eax, %eax ret .LBB0_2: cmpl %esi, %edi setne %al testl %edi, %edi setne %cl andb %al, %cl testl %esi, %esi setne %al andb %cl, %al ret bar(int, int): # @bar(int, int) testl %edi, %edi jle .LBB1_2 leal -1(%rsi), %eax leal -1(%rdi), %ecx testl %edi, %ecx sete %cl testl %esi, %esi setg %dl andb %cl, %dl testl %esi, %eax sete %cl andb %dl, %cl cmpl %esi, %edi setne %al andb %cl, %al ret .LBB1_2: xorl %eax, %eax retNur zwei bedingte Sprünge bzw. bei bar sogar nur einer. BOOYAH!
ICC 13.0.1
L__routine_start__Z3foojj_0: foo(unsigned int, unsigned int): lea -1(%rdi), %eax #2.23 testl %eax, %edi #2.23 jne ..B1.6 # Prob 50% #2.23 lea -1(%rsi), %eax #3.17 testl %eax, %esi #3.17 jne ..B1.6 # Prob 50% #3.17 cmpl %esi, %edi #4.11 je ..B1.6 # Prob 50% #4.11 testl %edi, %edi #5.6 je ..B1.6 # Prob 50% #5.6 movl $1, %eax #2.23 testl %esi, %esi #2.23 cmove %esi, %eax #2.23 ret #2.23 ..B1.6: # Preds ..B1.4 ..B1.1 ..B1.2 ..B1.3 xorl %eax, %eax #2.23 ret #2.23 L__routine_start__Z3barii_1: bar(int, int): movl %edi, %eax #9.18 decl %eax #9.18 lea -1(%rsi), %edx #10.18 js ..B2.6 # Prob 16% #12.18 testl %eax, %edi #12.33 jne ..B2.6 # Prob 50% #12.33 testl %edx, %edx #13.15 js ..B2.6 # Prob 16% #13.15 testl %edx, %esi #13.30 jne ..B2.6 # Prob 50% #13.30 movl $1, %edx #12.18 xorl %eax, %eax #12.18 cmpl %esi, %edi #12.18 cmovne %edx, %eax #12.18 ret #12.18 ..B2.6: # Preds ..B2.4 ..B2.1 ..B2.2 ..B2.3 xorl %eax, %eax #12.18 ret #12.184 bedingte Sprünge. Hmpf.
ps: Wer die Seite nicht kennt: http://gcc.godbolt.org/
Sehr cooles Tool wenn man schnell mal den ASM Output verschiedener Compiler vergleichen will.EDIT: Fehler in "bar" korrigiert, ASM Output entsprechend upgedated (die Anzahl der jcc hat sich dadurch nicht verändert).
ps2:
barfunktioniert natürlich nur wenn das MSB Bit immer 0 ist. Fällt mir auch jetzt erst auf, manchmal steh ich ganz schön aufm Schlauch
EDIT: Kommentar über die (nicht vorhandene) Sinnhaftigkeit von "bar" hinzugefügt.
-
hustbaer schrieb:
Ich denke das erste
sub eax, 1solltesub ecx, 1heissen -- so wie im 1. Block halt auch.
Sonst vergleicht dastest eax, ebxzum Schluss die falschen Werte.Und wieso
test eax, ebxzum Schluss und nichtcmpbzw.sub? Isttestschneller in so einem Fall schneller?Beim ersten hast du recht.
cmp subtrahiert ja die Werte, verwirft das Ergebnis und setzt die flags. Test macht ein bitand, verwirft das Ergebnis und setzt die flags. Bitwise-and ist deutlich einfacher zu implementieren. Ich weiss nicht, ob test heute noch schneller ist, aber frueher hat man das immer so gemacht und Compiler uebersetzen heutzutage auch x==0 meistens mit test eax, eax statt mit cmp eax, 0.
In diesem Fall hat man nur zwei Moeglichkeiten, naemlich das bit ist an der gleichen Stelle (bitand ergibt nicht 0) und das bit ist verschoben (bitand ergibt 0) und man kann test problemlos einsetzen.EDIT: Achja, der gute lea-Befehl. Mit dem uebertrumpfen mich die Compiler jedes Mal.
-
@Marthog
Dass man es verwenden kann hab ich schon gecheckt, bin ja ein Schlauer
Ich hätte dort halt vermutlich einfachcmpverwendet, weil ich es mitcmpeinfacher zu verstehen finde was abgeht. Und daher hab' ich nachgefragt.
-
Und ich meinte natürlich "so wie im 2. Block halt auch". Aber du bist ja auch ein Schlauer und hast es trotzdem verstanden
-
Toller Hacker Contest.
Und morgen kommt der Wettbewerb "Wer schreibt zuerst ein kompilierbares Program".
WinAPI Forum lässt grüßen.
-
Der Threadtitel bezieht sich nicht aufs Hacken, sondern auf den alten Forumsnamen von Arcoth. Und klein wahrscheinlich weil er noch ein Schüler ist/war.
-
Mechanics schrieb:
Der Threadtitel bezieht sich nicht aufs Hacken, sondern auf den alten Forumsnamen von Arcoth.
Völlig falsch.
Und klein wahrscheinlich weil er noch ein Schüler ist/war.
Ebenfalls völliger Unsinn.
Ich habe den Titel entsprechend angepasst... hier muss man wirklich das niedrigste Niveau voraussehen.
Edit: @Mehanics: Ich nehme an, dass du das nicht ernst gemeint hast?
-
Ich verstehe denn code nicht kann ihn mir jemand kurz erklären?
bool foo(unsigned u, unsigned v) { return !(u & (u - 1)) // bitweise UND sagt einen doch ob u und u-1 beide ein bit an der gleiche position auf 1 gesetzt haben? && !(v & (v - 1)) // gleiche && u != v // u ist nicht gleich v && u && v; // das hier verstehe ich nicht :/ } bool bar(int u, int v) { int temp1 = u - 1; int temp2 = v - 1; return temp1 >= 0 && !(temp1 & u) //EDIT: (temp1 & u) => !(temp1 & u) && temp2 >= 0 && !(temp2 & v) //EDIT: (temp2 & v) => !(temp2 & v) && u != v; }
-
Ach, Leute...
-
Arcoth schrieb:
Edit: @Mehanics: Ich nehme an, dass du das nicht ernst gemeint hast?
Natürlich nicht. Sorry, ich konnte einfach nicht widerstehen.
