Binärdarstellung einer Zahl mit einer einzigen Stringallokation
Hallo,
ausgehend von diesem Thread habe ich mir überlegt, wie man eine Umwandlung in Binärdarstellung ohne Änderung der Länge des Strings hinbekommen könnte (ohne die Umrechnung einfach zweimal zu machen). Herausgekommen ist dann dieses Monster, das die Länge der Binärdarstellung mit binärer Suche findet :mrgreen:
Delphi-Quellcode:
Dann mir eingefallen, dass das vermutlich viel schneller geht:
function intToBin(x: cardinal) : string;
var offset: integer; nextOffset: integer; lbits: integer; i: integer; begin lbits := 0; offset := sizeof(cardinal)*8; // binäre Suche der richtige Größe while (offset > 0) and (cardinal(1 shl (lbits+offset-1)) > x) do begin // Maske kann verkleinert werden nextOffset := offset div 2; // immer kleiner if ((high(cardinal) shl (lbits + nextOffset)) and x) = 0 then begin // Maske der nicht von lbits + nextOffset abgedeckten Bits überdeckt keine Bits von x // -> Wir kennen bessere obere Schranke :) offset := nextOffset; end else begin // Wir haben eine bessere untere Schranke :) lbits := lbits + nextOffset + 1; // lbits + nextOffset ist definitiv zu klein offset := offset - nextOffset - 1; // offset so anpassen, dass lbit + offest gleich bleibt end; end; lbits := lbits + offset; if lbits = 0 then inc(lbits); // mindestens eine Stelle wollen wir haben setLength(intToBin, lbits); // jetzt nur noch das eigentliche Umwandeln for i := 0 to lbits-1 do begin if (x and 1) = 0 then intToBin[lbits-i] := '0' else intToBin[lbits-i] := '1'; x := x shr 1; end; end;
Delphi-Quellcode:
Auch hier wird der Heap nur einmal gequält, dafür aber ein Buffer auf dem Stack angelegt.
function intToBin(x: cardinal) : string;
const maxLength = sizeof(cardinal)*8; var buffer: array[0..maxLength-1] of char; digits: integer; begin digits := 0; repeat inc(digits); if (1 and x) = 0 then buffer[maxLength-digits] := '0' else buffer[maxLength-digits] := '1'; x := x shr 1; until (x = 0); setLength(intToBin, digits); move(&buffer[maxLength-digits], &intToBin[1], sizeof(char)*digits); end; Damit ich das nicht völlig umsonst geschrieben habe, könnt ihr es jetzt angucken und als Übung dafür nehmen, verworrenen Code zu lesen. Kommentare sind erlaubt :wink: |
AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation
Stringlänge := Ceil(Lb(Zahlenwert)) ;)
Delphi-Quellcode:
Ungetestet und nur für 8-Bit Strings. Möglich, dass der Laufindex noch versetzt ist, aber ich will ins Bett :)
var
i, k, len: Integer; begin k := 1; if x>0 then begin len := Ceil(Lb(x)); SetLength(result, len); dec(k); else if x<0 then begin len := Ceil(Lb(x))+1; SetLength(result, len); result[k] := '-'; x := -x; end else begin result := '0'; Exit; end; for i := 1 to Length(result)-k do result[i+k] := Chr(((x shr (len-i+1)) and 1)+Ord('0')); end; |
AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation
Zitat:
|
AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation
Wenn die Ausgabe immer in der tatsächlichen Bitbreite erfolgen soll:
Delphi-Quellcode:
function IntToBin(AInt: Cardinal): string;
const BITSPERBYTE = 8; BITCHARS: array[Boolean] of char = ('0', '1'); var BitPos: byte; CurrentBit: Cardinal; begin SetLength(Result, SizeOf(AInt) * BITSPERBYTE); CurrentBit := 1; for BitPos := Length(Result) downto 1 do begin Result[BitPos] := BITCHARS[(AInt and CurrentBit) = CurrentBit]; CurrentBit := CurrentBit shl 1; end; end; |
AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation
Die Anzahl der Stellen kann man doch einfach so ermitteln:
Delphi-Quellcode:
Oder geht es gar nicht darum?
var
digits: Integer; begin digits := ceil(log(Value)/log(2)); {...} end;
Delphi-Quellcode:
function IntToBin(Value: Integer): String;
var i: Integer; j: Double; const BitValues: Array[Boolean] of Char = ('0', '1'); begin if Value = 0 then Result := '0' else begin j := Log2(Value); i := Ceil(j); if IsZero(Frac(j)) then inc(i); SetLength(Result, i); while i > 0 do begin Result[i] := BitValues[(Value and 1) = 1]; Value := Value shr 1; dec(i); end; end; end; |
AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation
Doch, siehe meinen Beitrag. Und Furtis :)
|
AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation
Also diese Aufgabenstellung lässt sich sicher wieder auf 5 Seiten auswalzen ^^
Falls der Code einfach zu verstehen sein soll, würde ich die Lösung mit dem Logarithmus bevorzugen.
Delphi-Quellcode:
Result := Ceil(Math.Log2(Value));
Wenn das zu langsam ist, könntest du es mit der FPU versuchen: 1. Gibt es wohl einen Opcode für den Log2: FYL2X 2. Schreibe die Zahl in ein FPU Register und lese (durch einen Bitshift oder so) den Exponenten aus. (Trick 17 ^^) |
AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation
Noch ein Vorschlag, das Prinzip: Ermittele das höchste gesetzte Bit, allokiere den String und verarbeite die restlichen Bits.
Delphi-Quellcode:
function IntToBin(x: cardinal): string;
var i,n: integer; m: cardinal; begin if x=0 then Result := '0' else begin {Teil 1: Bestimme höchstes gesetztes Bit} m := cardinal($80000000); n := 32; while m and x = 0 do begin dec(n); m := m shr 1; end; {Teil 2: Allokieren und Bits abarbeiten, n>0 da x<>0!} Setlength(Result,n); for i:=1 to n do begin if m and x <> 0 then Result[i] := '1' else Result[i] := '0'; m := m shr 1; end; end; end; |
AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation
warum einfach und schnell wenns auch kompliziert und langsam geht?
Delphi-Quellcode:
FUNCTION IntToBin(v:cardinal):string;
FUNCTION NeededLength(v:cardinal):integer; asm bsr eax,eax jnz @1 xor eax,eax @1: add eax,1 end; var i:integer; begin i:=NeededLength(v); SetLength(result,i); repeat result[i]:=Chr(Ord('0') or v and 1); dec(i); v:=v shr 1; until i=0; end; |
AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation
Zitat:
Mein Gedanken für die binäre Suche war, das man nicht alle Bits zweimal angucken muss. Der Aufwand für einen Schleifendurchlauf ist vielleicht etwas zu hoch. Zitat:
Wenn ich es einsetzen müsste, würde ich wohl den Vorschlag von Amateurprofi wählen: keine Gleitkommazahlen und ohne Umwege. Aber kein pures Delphi/Pascal :stupid: |
Alle Zeitangaben in WEZ +1. Es ist jetzt 21:31 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz