Binärdarstellung einer Zahl mit einer einzigen Stringallokation

[gammatester]

Zitat:

Zitat von BUG (Beitrag 1167916)

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.
...
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:

Wahrscheinlich hast Du nicht genau hingesehen, aber bei meinem Code werden die Bits nur einmal angesehen (bis auf das höchste, aber das könnte man auch noch wegoptimieren).

Im Übrigen macht Amateurprofis NeededLength auch nichts wesentlich anderes, und ich bezweifele, ob ein Funktionsaufruf und langsames bsr schneller sind. Weiter kann man natürlich auch die finale Schleife rückwarts durchlaufen, hier also der kombinierte Code in Pur-Pascal:

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:=n downto 1 do begin
      Result[i] := Chr(Ord('0') or (x and 1));
      x := x shr 1;
    end;
  end;
end;

[p80286]

wie wäre es hiermit?

Delphi-Quellcode:

fuction GetLengthofBinString(z:longword):integer;
  i : integer;
begin
  result:=0;
  for i:=0 to 31 do
    if (z and (1 shl i))<>0 then result:=i+1;
end;

Gruß
K-H

[gammatester]

Damit wird ja schon allein zur Längenbestimmung jedes Bits angesehen!

[BUG]

Zitat:

Zitat von gammatester (Beitrag 1167920)

Wahrscheinlich hast Du nicht genau hingesehen, aber bei meinem Code werden die Bits nur einmal angesehen (bis auf das höchste, aber das könnte man auch noch wegoptimieren).

Stimmt, hast recht :thumb:

Zitat:

Zitat von gammatester (Beitrag 1167920)

Im Übrigen macht Amateurprofis NeededLength auch nichts wesentlich anderes,

Wie gesagt, die machen alle das gleiche.

Zitat:

Zitat von gammatester (Beitrag 1167920)

und ich bezweifele, ob ein Funktionsaufruf und langsames bsr schneller sind.

Bei kleinen Zahlen könnte es schneller sein.
Bei großen Zahlen muss der Code ja auch alle Bits durchgehen (siehe oben).

[himitsu]

Zitat:

Zitat von gammatester (Beitrag 1167925)

Damit wird ja schon allein zur Längenbestimmung jedes Bits angesehen!

Wobei BSR auch nicht so toll sein soll.
Zumindestens für 32 Bit war es so (64 weiß ich nicht), aber da gab es letzes Jahr einen Thread dazu, wo ich dieses BSR verwendete.

Delphi-Quellcode:

function GetLengthofBinString(z: LongWord): LongInt; inline:

function GetLengthOfBinString(Value: LongWord): LongInt;
begin
  Result := 32;
  while (Result >= 0) and (LongInt(Value) >= 0) do begin
    Dec(Result);
    Value := Value shl 1;
  end;
end;

Mit etwas Glück macht der Compiler daraus einen Code, welcher nur 2 Register belegt und komplett innerhalb der Register arbeitet.

Oder man nutzt eben doch Assembler.



klar, man könnte jetzt noch über eine Bitmaske mehrere Bits prüfen.
z.B. jedes Byte einzeln, aber ob das immer was bringt?

Delphi-Quellcode:

function GetLengthOfBinString(Value: LongWord): LongInt;
begin
  if Value = 0 then 
    Exit(0);
  Result := 32;
  if Value and $FFFF0000 = 0 then begin
    Result := 16;
    Value := Value shl 16;
  end;
  while (Result >= 0) and (LongInt(Value) >= 0) do begin
    Dec(Result);
    Value := Value shl 1;
  end;
end; 

//oder

function GetLengthOfBinString(LongWord: LongWord): LongInt;
begin
  if Value = 0 then 
    Exit(0);
  Result := 32;
  while (Result >= 0) and (Value and $FF000000 = 0) do begin
    Dec(Result, 8);
    Value := Value shl 8;
  end;
  while (Result >= 0) and (LongInt(Value) >= 0) do begin
    Dec(Result);
    Value := Value shl 1;
  end;
end;

Die Pascal-Variante hätte den Vorteil derPlattformunabhängigkeit und sie könnte man auch für 64 Bit anpassen.
32 = SizeOf(NativeInt) * 8
LongInt = NativeInt
LongWord = LongWord
$FF000000 = ($FF shl (SizeOf(NativeInt) - 1) * 8)
usw.

[Iwo Asnet]

Also ich wäre schwer dafür, für die Bitlänge eine Lookuptabelle zu nehmen. Das könnte noch schneller sein. Gut, der Speicherverbrauch ist suboptimal, aber darum geht es hier nichtm, denn die Aufgabenstellung besagt:
1. Jedes Bit nur einmal anschauen (wegen der bit abrasion, is klar) und
2. soll der String soll auch nur 1x alloziiert werden. Vermutlich das schädlich für den Speicher, ich tippe auf memory rotting, wegen dem fehlenden garbage collector

[himitsu]

Wegen Speicher ... macht es doch so wie IntToStr oder Format?

ein

Delphi-Quellcode:

array[0..31] of Char

als Puffer auf'm Stack,
dann einmal die Zeichen berechnen und den Puffer befüllen,
gleichzeitig werden die Bits automatisch gezählt
und zum Schluß ein SetString, wo nur einmal Speicher allociert wird.
:stupid:

[Iwo Asnet]

Spielverderber.

[BUG]

Zitat:

Zitat von himitsu (Beitrag 1167940)

ein

Delphi-Quellcode:

array[0..31] of Char

als Puffer auf'm Stack,
dann einmal die Zeichen berechnen und den Puffer befüllen,
gleichzeitig werden die Bits automatisch gezählt
und zum Schluß ein SetString, wo nur einmal Speicher allociert wird.
:stupid:

Guck mal in den ersten Beitrag :tongue:

So daneben lag ich mit der binären Suche für das wohl trotzdem nicht:

Zitat:

Zitat von http://coding.derkeiler.com/Archive/Assembler/comp.lang.asm.x86/2005-04/msg00283.html

K7 - microcoded binary-search, runs in constant 7-8 cycles

Das blr so langsam sein kann, hatte ich nicht vermutet.

[Amateurprofi]

Zitat:

Zitat von gammatester (Beitrag 1167920)

Im Übrigen macht Amateurprofis NeededLength auch nichts wesentlich anderes, und ich bezweifele, ob ein Funktionsaufruf und langsames bsr schneller sind.

Hallo gammatester,

vielleicht solltest du nicht nur bezweifeln sondern prüfen.

Ich habe mal mit den Werten 0, 2^0..31 getestet.

Die nachstehende Tabelle zeigt von links nach rechts folgende Daten

1) Der Wert der umgewandelt wurde.
2) CPU-Ticks für deine IntToBin.
3) CPU-Ticks für meine IntToBin.
4) CPU-Ticks für deine Ermittlung der benötigten Länge.
5) CPU-Ticks für meine Ermittlung der benötigten Länge.

Mein zusätzlicher Funktionsaufruf und das so langsame "bsr" ist im (Vergleich zu deiner Methode) genau so schnell bis 7 Mal so schnell.

Code:

         0 238 110 /   50  50
         1 568 110 /  374  50
         2 484 136 /  358  50
         4 484 152 /  340  50
         8 492 178 /  330  50
        16 494 204 /  322  50
        32 500 220 /  306  50
        64 518 238 /  288  50
       128 520 264 /  280  50
       256 534 288 /  262  50
       512 544 314 /  246  50
      1024 552 340 /  238  50
      2048 568 356 /  228  50
      4096 578 382 /  212  50
      8192 586 408 /  204  50
     16384 594 432 /  188  52
     32768 604 450 /  170  50
     65536 612 476 /  162  50
    131072 630 502 /  144  50
    262144 706 526 /  136  50
    524288 714 612 /  128  50
   1048576 730 630 /  110  50
   2097152 730 670 /  102  50
   4194304 748 680 /   92  50
   8388608 756 714 /   84  50
  16777216 782 730 /   84  50
  33554432 782 748 /   68  50
  67108864 792 774 /   68  50
 134217728 808 798 /   60  50
 268435456 824 826 /   58  50
 536870912 840 850 /   58  50
1073741824 858 866 /   50  58
2147483648 892 884 /   50  50