AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Binärdarstellung einer Zahl mit einer einzigen Stringallokation

Binärdarstellung einer Zahl mit einer einzigen Stringallokation

Ein Thema von BUG · begonnen am 24. Mai 2012 · letzter Beitrag vom 26. Mai 2012
Antwort Antwort
Seite 1 von 3  1 23   
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#1

Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 02:17
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
Delphi-Quellcode:
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;
Dann mir eingefallen, dass das vermutlich viel schneller geht:
Delphi-Quellcode:
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;
Auch hier wird der Heap nur einmal gequält, dafür aber ein Buffer auf dem Stack angelegt.


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

Geändert von BUG (24. Mai 2012 um 02:38 Uhr)
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.674 Beiträge
 
Delphi 2007 Enterprise
 
#2

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 03:38
Stringlänge := Ceil(Lb(Zahlenwert))

Delphi-Quellcode:
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;
Ungetestet und nur für 8-Bit Strings. Möglich, dass der Laufindex noch versetzt ist, aber ich will ins Bett
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)

Geändert von Medium (24. Mai 2012 um 03:51 Uhr)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#3

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 07:30
und als Übung dafür nehmen, verworrenen Code zu lesen. Kommentare sind erlaubt
Der Code ist gar nicht so verworren, nur die Herleitung der Lösung ein klassisches Beispiel für "von Hinten durch die Brust ins Auge".
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.459 Beiträge
 
Delphi 11 Alexandria
 
#4

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 08:32
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;
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.198 Beiträge
 
Turbo Delphi für Win32
 
#5

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 10:37
Die Anzahl der Stellen kann man doch einfach so ermitteln:
Delphi-Quellcode:
var
  digits: Integer;
begin
  digits := ceil(log(Value)/log(2));
  {...}
end;
Oder geht es gar nicht darum?

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;
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton (24. Mai 2012 um 10:50 Uhr)
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.674 Beiträge
 
Delphi 2007 Enterprise
 
#6

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 10:47
Doch, siehe meinen Beitrag. Und Furtis
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#7

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 11:07
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.
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 ^^)
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#8

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 11:47
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;
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
963 Beiträge
 
Delphi XE2 Professional
 
#9

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 11:59
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;
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#10

AW: Binärdarstellung einer Zahl mit einer einzigen Stringallokation

  Alt 24. Mai 2012, 12:45
Noch ein Vorschlag, das Prinzip: Ermittele das höchste gesetzte Bit, allokiere den String und verarbeite die restlichen Bits.
Das ist das Prinzip (fast) aller hier vorgestellten Codes

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.

Gibt es wohl einen Opcode für den Log2 FYL2X
Ich würde doch hoffen, das lb den benutzt.

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
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:42 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf