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
Thema durchsuchen
Ansicht
Themen-Optionen

Binärdarstellung einer Zahl mit einer einzigen Stringallokation

Ein Thema von BUG · begonnen am 24. Mai 2012 · letzter Beitrag vom 26. Mai 2012
 
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
 


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 13:33 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz