VB6: Anzahl binärer Stellen eines Integer-Wertes
lima-city → Forum → Programmiersprachen → Basic
anzahl
befehl
bit
code
compiler
frage
funktion
helfen
integer zahl
konstante ersetzen
log
methode
nutzen
problem
sagen
schleife
schleifen
stellen
test
zeile
-
Guten Tag,
folgendes: Ich suche eine Möglichkeit, möglichst mit einer Zeile Code die Anzahl der binären Stellen eines Integer-Wertes unter VB6 zu ermitteln. Nun kam ich dank kochmarkus auf die Lösung
wobei es da das Problem gibt, dass er mir für x = 1 die Anzahl 0 ausgibt. Scheinbar rundet er bei x.5 noch ab. Wenn ich nuniAnz = Round((Log(x) / Log(2)) + 0.5)
verwende, gibt er mir für x = 255 die Anzahl 9 aus. Wobei er halt durchgängig für x = 1 die Anzahl 1 und für x = 255 die Anzahl 8 ausspucken sollte.iAnz = Round((Log(x) / Log(2)) + 0.51)
Nun stellt sich die Frage: Gibt es eine Möglichkeit, das ganze so zu verpacken, dass er mit einer Zeile Code ausgibt, wie viele Stellen der Binärwert hätte? Also wirklich nur mit mathematischen Operationen? Ich bin gespannt, ob jemanden da etwas einfällt. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Ich würde es mit einer Schleife machen... Jedes Bit vom
MSB zum LSB durchgehen. Wenn eine "1" entdeckt wurde, dann
weiß man: "hier" fängt die Zahl erst wirklich an. Wenn man
die Anzahl Schleifendurchläufe bis dahin kennt und die Anzahl
der Bit, die für eine Integer-Zahl in VB bereitgestellt wird (wohl 32-Bit
auf den meisten Systemen heute), dann kann man auf die
Anzahl der binären Stellen schließen, die diese Integer-Zahl
wirklich hat.
Ich bin mir nicht sicher, ob es mit deiner Methode wirklich geht.
Prinzipiell kann man sagen, dass etwa 3,32 binäre Stellen benötigt
werden, um eine weitere Zehnerpotenz darstellen zu können... aber
da fängt es mit dem Runden ja erst richtig an... :-)
Wenn du es wirklich genau haben willst, dann machs mit ner Schleife.
-
tangoal schrieb:
Ich würde es mit einer Schleife machen... Jedes Bit vom
MSB zum LSB durchgehen. Wenn eine "1" entdeckt wurde, dann
weiß man: "hier" fängt die Zahl erst wirklich an. Wenn man
die Anzahl Schleifendurchläufe bis dahin kennt und die Anzahl
der Bit, die für eine Integer-Zahl in VB bereitgestellt wird (wohl 32-Bit
auf den meisten Systemen heute), dann kann man auf die
Anzahl der binären Stellen schließen, die diese Integer-Zahl
wirklich hat.
Ich bin mir nicht sicher, ob es mit deiner Methode wirklich geht.
Prinzipiell kann man sagen, dass etwa 3,32 binäre Stellen benötigt
werden, um eine weitere Zehnerpotenz darstellen zu können... aber
da fängt es mit dem Runden ja erst richtig an... :-)
Wenn du es wirklich genau haben willst, dann machs mit ner Schleife.nerdinator schrieb:
Eine Schleife, kann soweit ich weiss nur mit mindestens 3 zeilen Code geschrieben werden. Da könnte ich dann auch gleich eine ceil()-function schreiben, welche immer aufrundet. Das wäre wesentlich schneller als eine Schleife.
Nun stellt sich die Frage: Gibt es eine Möglichkeit, das ganze so zu verpacken, dass er mit einer Zeile Code... -
Wenn's um absolute Schnelligkeit geht, dann würde ich an deiner Stelle mal prüfen,
wielang die Ausführung eines solchen Logarithmus-Befehls dauert (z.B. wieviele CPU-Takte).
Dadrin sind bestimmt noch irgendwelche Schleifen versteckt... Achso und du rufst auch 2
mal den Round-Befehl auf...
Könnte nämlich sein, dass eine Schleife, die nur ganz einfache Aufgaben erfüllt, viel schneller
ist (hier maximal 32 Durchläufe...) Außerdem ist die Schleife in diesem Fall
auf jeden Fall exakt. Bei der Log-Methode bin ich mir nicht sicher...
Aber das erstmal herauszufinden ist zu aufwändig, oder? (Also ich würde es nur im absoluten
Ausnahmefall tun^^)
Wenn du das in einer Zeile haben willst, dann mach doch eine Funktion draus
iAnz = getAnzahlBit(x) public function getAnzahl(byval x as integer) As integer '...... For i = 31 to 0 step -1 'Prüfen, ob i-tes Bit von x eine 1 ist... Next i return anzahlBit end function
Hoffe ich konnte dir etwas helfen. Auch, wenn es vielleicht nicht ganz das ist, wonach du gesucht hast...
In der Assemblerprogrammierung wäre dies mit sicherheit die viel schnellere Lösung, weil die eben am besten
angepasst an die Anforderungen ist. Angepasste Lösungen sind immer die schnellsten. Das nutzen von zusätzlichen
Funktionen (wie z.B. Round() und Log() ) ist da nicht so "angepasst".
Aber kann ich mal fragen, wozu du das so in dieser Form brauchst? Ich wundere mich nämlich, warum du nicht
eine solche Schleifenlösung bevorzugst... Kann mir keinen vernünftigen Grund gerade vorstellen... -
tangoal schrieb:
Wo rufe ich 2 mal den Round-Befehl auf? oO
Wenn's um absolute Schnelligkeit geht, dann würde ich an deiner Stelle mal prüfen,
wielang die Ausführung eines solchen Logarithmus-Befehls dauert (z.B. wieviele CPU-Takte).
Dadrin sind bestimmt noch irgendwelche Schleifen versteckt... Achso und du rufst auch 2
mal den Round-Befehl auf...
tangoal schrieb:
Eine Dualzahl mit
Könnte nämlich sein, dass eine Schleife, die nur ganz einfache Aufgaben erfüllt, viel schneller
ist (hier maximal 32 Durchläufe...) Außerdem ist die Schleife in diesem Fall
auf jeden Fall exakt. Bei der Log-Methode bin ich mir nicht sicher...Stellen kann maximal den Wert
annehmen. Also hat die Dezimalzahl
Stellen. Das ist eine Mathematische gewissheit.
tangoal schrieb:
Also nach einbau der logarithmus-Funktion spare ich fast ein Viertel der Zeit, auch wenn ich durch die fehlende Ceiling-Funktion noch nicht das richtige Ergebnis bekomme.
Aber das erstmal herauszufinden ist zu aufwändig, oder? (Also ich würde es nur im absoluten
Ausnahmefall tun^^)
tangoal schrieb:
Was VB noch immer nicht daran hindert, endlos Zeit damit zu vergeuden, von Befehl zu Befehl zu springen.
Wenn du das in einer Zeile haben willst, dann mach doch eine Funktion draus
tangoal schrieb:
Natürlich, aus Kieselsteinen kann man ja schließlich auch einen leckeren Salat machen...
Hoffe ich konnte dir etwas helfen. Auch, wenn es vielleicht nicht ganz das ist, wonach du gesucht hast...
tangoal schrieb:
Na was für ein Pech, dass wir hier von VB sprechen
In der Assemblerprogrammierung wäre dies mit sicherheit die viel schnellere Lösung, weil die eben am besten
angepasst an die Anforderungen ist.
tangoal schrieb:
For-Schleifen sind scheinbar langsamer als Do...Loop-Schleifen. (Nach Messung mit 1.000.000 Befehlen ca. 16 Ticks langsamer, was ca. 50% ausmachte) Schleifen die Ausserhalb der Runtime stehen sind langsamer als Schleifen innerhalb der VB-Runtime. "Fertigprodukte" wie Round() und Log() sind bei VB definitiv schneller, da sie nicht erst von der Runtime "Interpretiert" werden müssen.
Angepasste Lösungen sind immer die schnellsten. Das nutzen von zusätzlichen
Funktionen (wie z.B. Round() und Log() ) ist da nicht so "angepasst".
tangoal schrieb:
Ich schreibe einen Kompressions-Algorithmus, wo deine Schleife beispielsweise 100 Millionen mal aufgerufen werden könnte.Das heisst: Aus 100 Millionen Befehlen werden... über 3 Milliarden. Und das auch nur, wenn deine "überprüfung" mit einem Befehl möglich ist. VB6 ist dafür bekannt, jede Menge Zeit zwischen jedem einzelnem Befehl vergehen zu lassen. Diese Zeit ist relativ CPU-Unabhängig, da das mit der VB-Runtime zusammen hängt, denn die Runtime wird jeden Befehl erst interpretieren müssen, bevor sie ihn ausführt. Mathematische Operationen, wie Round() oder Log(), welche praktisch in der Runtime integriert sind, werden da schneller ausgeführt. Logisch, wenn man Dinge im Gedächnis hat, hat man sie auch schneller parat, als wenn man bei Wikipedia nachschlagen muss.
Aber kann ich mal fragen, wozu du das so in dieser Form brauchst? Ich wundere mich nämlich, warum du nicht
eine solche Schleifenlösung bevorzugst... Kann mir keinen vernünftigen Grund gerade vorstellen... -
nerdinator schrieb: tangoal schrieb:
Wenn's um absolute Schnelligkeit geht, dann würde ich an deiner Stelle mal prüfen,
wielang die Ausführung eines solchen Logarithmus-Befehls dauert (z.B. wieviele CPU-Takte).
Dadrin sind bestimmt noch irgendwelche Schleifen versteckt... Achso und du rufst auch 2
mal den Round-Befehl auf...
Wo rufe ich 2 mal den Round-Befehl auf? oO
Sorry, ich meine natürlich 2 Mal den Logarithmus-Befehl.
nerdinator schrieb: tangoal schrieb:
Könnte nämlich sein, dass eine Schleife, die nur ganz einfache Aufgaben erfüllt, viel schneller
ist (hier maximal 32 Durchläufe...) Außerdem ist die Schleife in diesem Fall
auf jeden Fall exakt. Bei der Log-Methode bin ich mir nicht sicher...
Eine Dualzahl mit n Stellen kann maximal den Wert 2^n-1 annehmen. Also hat die Dezimalzahl n gerundet log_2n+1 Stellen. Das ist eine Mathematische gewissheit.
Speichertechnisch werden die Variablen immer binär abgelegt. Eine Integer-Zahl besteht meinetwegen aus 32-Bit.
Du musst nur diese 32 Bit abklappern! Mehr als 32 Binäre Stellen hast du nicht zur Verfügung. Und wenn ich mich recht entsinne wolltest du doch die Anzahl an Binären Stellen haben, die eine beliebige Integer-Ganzzahl hat
nerdinator schrieb: tangoal schrieb:
Angepasste Lösungen sind immer die schnellsten. Das nutzen von zusätzlichen
Funktionen (wie z.B. Round() und Log() ) ist da nicht so "angepasst".
For-Schleifen sind scheinbar langsamer als Do...Loop-Schleifen. (Nach Messung mit 1.000.000 Befehlen ca. 16 Ticks langsamer, was ca. 50% ausmachte) Schleifen die Ausserhalb der Runtime stehen sind langsamer als Schleifen innerhalb der VB-Runtime. "Fertigprodukte" wie Round() und Log() sind bei VB definitiv schneller, da sie nicht erst von der Runtime "Interpretiert" werden müssen.
Mein Gott, dann nimm doch ne Do... Loop-Schleife. Rein vom logischen Ablauf ist doch in diesem Fall Jacke wie Hose
nerdinator schrieb:
tangoal schrieb:
Hoffe ich konnte dir etwas helfen. Auch, wenn es vielleicht nicht ganz das ist, wonach du gesucht hast...
Natürlich, aus Kieselsteinen kann man ja schließlich auch einen leckeren Salat machen...
tangoal schrieb:
In der Assemblerprogrammierung wäre dies mit sicherheit die viel schnellere Lösung, weil die eben am besten
angepasst an die Anforderungen ist.
Na was für ein Pech, dass wir hier von VB sprechen
Ja, gut. Am Besten verkrieche ich mich jetzt und versuche keine Lösungsansätze aus dem Hut zu zaubern
Aber nur mal so rein von ganz weit weg betrachtet:
Was ist für einen Rechner einfacher: einige Bits herumzuschieben und auf 1 oder 0 zu prüfen, oder irgendwelche
Algorithmen durchführen, um den Logarithmus einer Zahl herauszufinden und eine Rundung vorzunehmen?
Sorry, bei den ganzen Runtimes und so habe ich kein Plan, inwieweit der tatsächliche Zeitunterschied zwischen
eigenen und integrierten Befehlen ist. Wenn der allzu, allzu krass ist, dann ist VB doch eigentlich schrott, oder?
Einen Kompressionsalgorithmus? In sehr vereinfachter Form habe ich sowas schon mal für Bilder gemacht, mit Lauflängenkodierung und Ersetzung von häufig vorkommenden Zeichenkombinationen...
Nun, gut. Sorry, dass ich dir wirklich nicht weiterhelfen konnte. Viel Erfolg noch bei deinem Vorhaben.
Gruß tangoal
PS: mir fällt gerade ein, das man 7-Zip auch u.U. verwenden könnte. Lässt sich als Exe nämlich mit einer Kommandozeile steuern.
-
kochmarkus schrieb:
tangoal schrieb:
Sorry, ich meine natürlich 2 Mal den Logarithmus-Befehl.
Ja, das ist mir bekannt.
@nerdinator: du könntest doch log(2) noch durch eine Konstante ersetzen. Dann muss das nicht immer neu berechnet werden. Dürfte somit noch etwas schneller sein.
Das wolltest du doch auch damit sagen, kochmarkus. Oder nicht?
-
tangoal schrieb:
kochmarkus schrieb:
tangoal schrieb:
Sorry, ich meine natürlich 2 Mal den Logarithmus-Befehl.
Ja, das ist mir bekannt.
@nerdinator: du könntest doch log(2) noch durch eine Konstante ersetzen. Dann muss das nicht immer neu berechnet werden. Dürfte somit noch etwas schneller sein.
Das wolltest du doch auch damit sagen, kochmarkus. Oder nicht?
Nein, daran hab ich gar nicht gedacht, dass man log 2 noch mit einer Konstante ersetzen kann, ich muss gestehen, ich dachte dir ist nicht klar, dass man das so umrechnen kann. Allerdings denke ich ein anständiger Compiler ersetzt log 2 beim kompiliren automatisch durch eine Konstante. -
kochmarkus schrieb:
tangoal schrieb:
kochmarkus schrieb:
tangoal schrieb:
Sorry, ich meine natürlich 2 Mal den Logarithmus-Befehl.
Ja, das ist mir bekannt.
@nerdinator: du könntest doch log(2) noch durch eine Konstante ersetzen. Dann muss das nicht immer neu berechnet werden. Dürfte somit noch etwas schneller sein.
Das wolltest du doch auch damit sagen, kochmarkus. Oder nicht?
Nein, daran hab ich gar nicht gedacht, dass man log 2 noch mit einer Konstante ersetzen kann, ich muss gestehen, ich dachte dir ist nicht klar, dass man das so umrechnen kann. Allerdings denke ich ein anständiger Compiler ersetzt log 2 beim kompiliren automatisch durch eine Konstante.
Hm, wieso soll ein Compiler die Ersetzung durch eine Konstante durchführen? Überprüft der Compiler, ob einer Funktion ein "konstanter Wert" übergeben wird? Und wenn ja, dann führt er die Funktion einmal durch, ermittelt das Ergebnis und setzt den Rückgabewert als Konstante ein? Gut, kann ich mir vorstellen, dass es sowas gibt. Würde aber sagen, dass das nicht jeder Compiler wirklich machen kann. Das ist ja schon Programmoptimierung...^^
Und ob sowas in der Art mit VB6 geht, ist fraglich^^ -
Wie es mit VB aussieht, weiß ich nicht, aber ich hab das grad mal mit C versucht:
C-Code 1:
#include <math.h> int main(void) { volatile int x = 2; x=log(x); return x; }
mit "gcc -lm -S test.c" nach Assembler übersetzt:
.file "test.c" .text .globl main .type main, @function main: pushl %ebp movl %esp, %ebp andl $-16, %esp subl $48, %esp movl $2, 44(%esp) movl 44(%esp), %eax movl %eax, 28(%esp) fildl 28(%esp) fstpl (%esp) call log fnstcw 26(%esp) movzwl 26(%esp), %eax movb $12, %ah movw %ax, 24(%esp) fldcw 24(%esp) fistpl 28(%esp) fldcw 26(%esp) movl 28(%esp), %eax movl %eax, 44(%esp) movl 44(%esp), %eax leave ret .size main, .-main .ident "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3" .section .note.GNU-stack,"",@progbits
(Man sieht schön den "call log" Aufruf.)
Jetzt C-Code 2:
#include <math.h> int main(void) { int x; x=log(2); return x; }
Wieder mit "gcc -lm -S test.c" übersetzt (also eigentlich ohne Optimierung:
.file "test.c" .text .globl main .type main, @function main: pushl %ebp movl %esp, %ebp subl $16, %esp movl $0, -4(%ebp) movl -4(%ebp), %eax leave ret .size main, .-main .ident "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3" .section .note.GNU-stack,"",@progbits
Beitrag zuletzt geändert: 1.5.2010 23:17:03 von kochmarkus -
tangoal schrieb:
Ja, ich verwende zwei mal den Logarithmus-Befehl, was dennoch etwa 25% schneller ist, als wenn ich das ganze über eine Schleife (übrigens ist die Schnellste Schleife bei VB6 mit GoTo zu erreichen - vielleicht erwähnenswert.) oder if-abfragen mache.
Sorry, ich meine natürlich 2 Mal den Logarithmus-Befehl.
tangoal schrieb:
Zumindest VB6 ist es, ja. Wie das ganze dann mit .NET aussieht, weiss ich nicht. Aber genau dies ist beispielsweise das Problem, wenn man mit VB6 3D-Spiele ausarbeitet. Es gibt ein "Hard-Limit" an Polygonen die gezeichnet werden können, da VB6 sonst an schlicht mit der Verarbeitung ins Stocken kommt. Durch diesen Umstand kam ich mit all diesen Umständen in "Kontakt". Einfacher, als das ganze hier jetzt groß auszubreiten wäre jedoch gewesen, schlicht auf die Frage im Eingangs-Thread zu antworten und vorerst anzunehmen, dass jemand schon seine Gründe haben wird, seine Frage so zu formulieren, wie sie formuliert ist.
Sorry, bei den ganzen Runtimes und so habe ich kein Plan, inwieweit der tatsächliche Zeitunterschied zwischen
eigenen und integrierten Befehlen ist. Wenn der allzu, allzu krass ist, dann ist VB doch eigentlich schrott, oder?
tangoal schrieb:
Also RLE mit Data Dictionary - praktisch BMP? ;)
Einen Kompressionsalgorithmus? In sehr vereinfachter Form habe ich sowas schon mal für Bilder gemacht, mit Lauflängenkodierung und Ersetzung von häufig vorkommenden Zeichenkombinationen...
Meine Idee ist halt ein wenig Komplexer - das ganze hier auszubreiten wäre jetzt zu viel... Und soweit ich weiss habe ich eine frühe Version mit der "Grundidee" hier auch schonmal veröffentlicht. Es ist nicht der schnellste, nicht der beste... Aber es ist mein Algorithmus, den ich selbst sinniert habe. Soll nach Aussage einiger Leute ein paar Kleinigkeiten mit Entropie-Kodierung zutun haben ;) Bei Anfragen per PN erläuter ich das gerne näher.
tangoal schrieb:
Das ganze würde praktisch der meiner Idee einer Lookup-Tabelle gleich kommen.
Das wolltest du doch auch damit sagen, kochmarkus. Oder nicht?
Um das ganze nun einmal zu beenden:
Kochmarkus schlug damals vor
, was ursprünglich daran scheiterte, dass VB6 keine Ceil()-Funktion anbietet. Nachdem ich nun hier nachgelesen habe, was so eine Ceil-Function so tut, kam ich aufiAnz = ceil(log(x) / log(2))
, was theoretisch stimmen müsste, wenn ersteres Stimmt. Nun haben ich mich mit karlsve der FunktioniAnz = (log(x) + log(2) - 1) / log(2)
angenähert, was eigentlich ganz brauchbare Ergebnisse liefert - aber nicht in VB6. Denn dort scheint es einen Rundungsfehler bei log(8) / log(2) zu geben, wodurch er auf 2,99999....6 kommt, was ansich jetzt nicht so dramatisch wäre, wenn man sagen würdeiAnz = int(log(x) / log(2) + 1)
Das Problem entsteht da dadurch, dass er den Rundungsfehler nicht vorher rundet... Oder so ein Müll. Also werde ich nun wahrscheinlich erstmal VB6 in die Tonne werfen und das ganze auf C++ umsatteln, wo die Functionx = log(x) / log(2) + 1 iAnz = int(x)
das gewünschte Ergebnis zu bringen scheint. Wobei ich dort wahrscheinlich eine Kombination aus Bitoperanten und Lookup-Tabellen verwenden werde, da es dort um einiges Schneller ist.int bitValue(int x) { return ceil(log(x+1)/log(2)); }
Von meiner Seite her ist das ganze nun auf jeden Fall erledigt. Der Thread kann geschlossen werden. Oder lasst ihn offen, wenn ihr meint, andere Leute könnten noch interesse daran haben, etwas dazu zu äussern. Zumindest wird meine zukünftige Arbeit dann eher in den Bereich "c++" fallen, hier also Off-Topic werden. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
