"Variablenübergreifende" Bitverschiebungen

[Neutral General]

Hi,

Habt ihr eine Idee wie man möglichst effizient eine (ich nenne es mal) "variablenübergreifende" Bitverschiebung durchführen kann?
Wie ich mir das vorgestellt habe:

Delphi-Quellcode:

var arr: Array[0..1] of Byte = (00000000,10000000); // binär
begin
  arr := arr shl 1;
  // =>   
  // arr = (00000001,00000000);
end;

Das ist jetzt natürlich nur Pseudocode. Es kann vorausgesetzt werden, dass die Werte im Speicher hintereinander stehen.

Gruß
Neutral General

[Dax]

Delphi-Quellcode:

function ArrayShl(arr: array of byte; count: integer): array of byte;
var i, offset: integer;
begin
  offset := count div (8 * sizeof(arr[0]));
  count := count mod (8 * sizeof(arr[0]));
  SetLength(result, arr - offset);
  for i := 0 to high(result) - 1 do
    result[i] := (arr[i + offset] shl count) or (arr[i + offset + 1] shr (8 * sizeof(arr[0]) - count));
  result[high(result)] := arr[high(arr)] shl count;
end;

Nicht getestet, aber sollte so gehen. Glaub ich :gruebel:

[Corpsman]

naja da es nur "bytes" sind gehts
interpretiere das array als ein Word und shifte in dem.

Delphi-Quellcode:

var arr: Array[0..1] of Byte = (00000000,10000000); // binär
w:Word;
begin
//  arr := arr shl 1;
  // =>   
  // arr = (00000001,00000000);
 @w := @arr[0] ; // oder 1 ???
w := w shl 8;

end;

[Neutral General]

Zitat:

Zitat von Corpsman

naja da es nur "bytes" sind gehts
interpretiere das array als ein Word und shifte in dem.

Delphi-Quellcode:

var arr: Array[0..1] of Byte = (00000000,10000000); // binär
w:Word;
begin
//  arr := arr shl 1;
  // =>   
  // arr = (00000001,00000000);
 @w := @arr[0] ; // oder 1 ???
w := w shl 8;

end;

Hi,

Ja das Problem wäre in meinem Fall aber, dass es quasi auch vorkommen kann, dass ich um 10, 20 oder 60 Bit verschiebe. Dann funktioniert das da nicht mehr.

@Dax: Ich schau mir deine Funktion mal an.

[Corpsman]

Mein Vorschlag diente eigentlich auch mehr der Abschreckung.

Ich empfehle dringend das so wie Dax zu machen. Wenn du natürlich um nicht 2^x ,x>=3 blöcke verschieben willst wird das ganze aufwendiger.

Wies auf jedenfall geht ist wenn du als zwischenschritt in ein Array of Boolean schreibst da drin dann schiebst und dann wieder zurück, wäre natürlich aber auch nicht so "schön"

evtl gibts aber auch ne "Move Speicher Funktion"

[Reinhard Kern]

Zitat:

Zitat von Neutral General

Ja das Problem wäre in meinem Fall aber, dass es quasi auch vorkommen kann, dass ich um 10, 20 oder 60 Bit verschiebe. Dann funktioniert das da nicht mehr.
...

Hallo,

null problemo: du shiftest zuerst um BitCount div 8 bytes, z.B. mit Move. Anschliessend shiftest du BitCount mod 8 Bits.

Gruss Reinhard

[Neutral General]

Zitat:

Zitat von Reinhard Kern

Anschliessend shiftest du BitCount mod 8 Bits.

Den Plan hatte ich mittlerweile auch schon, aber so einfach lässt sich das nicht shiften ;)
Aber hab ne Methode:

Ich rechne es mal mit 4 Bit pro Zahl vor:

(1100,1010) shl 2

1100 shl 2 = 0000 = a
1010 shl 2 = 1000 = b

1100 shr 2 = 0011 = c
1010 shr 2 = 0010 = d

Ergebnis:

(a or d) (+) b = 0010 1000

[Blup]

Funktioniert für count = 0..7:

Delphi-Quellcode:

function Rol(const AValue, ACount: Byte): Byte register;
asm
  mov cl, dl
  rol al, cl
end;

function ArrayShl(arr: TByteArray; count: integer): TByteArray; 
var
  mask0, mask1, b0, b1: Byte;
begin
  Result := Copy(arr);
  mask0 := $FF shl Count;
  mask1 := mask0 xor $FF;
  b1 := 0;
  for i := High(Result) downto 0 do
  begin
    b0 := rol(Result[i], count);
    Result[i] := (b0 and mask0) or (b1 and mask1);
    b1 := b0;
  end;
end;

[Neutral General]

Zitat:

Zitat von Blup

Funktioniert für count = 0..7 [...]

Ah jo das bringt mir ja nix ;)
Habs aber jetzt wie oben beschrieben gelöst

[brechi]

Musst du nur shiften oder folgen andere Operationen?

[Neutral General]

Wie meinst du das?

Also die geshiftete Zahl soll schon noch zu gebrauchen sein danach^^

[Dax]

Was hast du eigentlich vor? ;)

Wenn es um Arithmetik mit großen Zahlen geht und du dafür eine Library schreiben willst (weil du musst, nicht, weil dir einfach mal danach ist), wäre es vielleicht produktiver, ein Binding für GMP zu benutzen/schreiben.

[Neutral General]

Hi,

Ja genau das habe ich vor :mrgreen:
Will das aber gerne mal selbst probieren. Bisher funktioniert es auch ganz gut.

Allerdings weiß ich noch nicht so genau wie ich die Division halbwegs effizient implementieren kann... :(
Das shiften klappt mittlerweile. Und ich denke auch ganz gut.

[Blup]

Zitat:

Zitat von Neutral General

Zitat:

Zitat von Blup

Funktioniert für count = 0..7 [...]

Ah jo das bringt mir ja nix ;)
Habs aber jetzt wie oben beschrieben gelöst

Ganze Byte zu verschieben hab ich dir schon allein zugetraut. :zwinker:

Edit:

Delphi-Quellcode:

type
  TByteArray = packed array of Byte;

function Rol(const AValue, ACount: Byte): Byte register; 
asm
  mov cl, dl
  rol al, cl
end;

function ArrayShl(const arr: TByteArray; count: integer): TByteArray;
var
  mask0, mask1, b0, b1: Byte;
  i: integer;
begin
  Result := Copy(arr);
  {Byte-Verschiebung}
  i := count div 8;
  if i > 0 then
  begin
    Move(Result[i], Result[0], SizeOf(Result[0]) * (Length(Result) - i));
    FillChar(Result[Length(Result) - i], SizeOf(Result[0]) * i, #0);
    count := count mod 8;
  end;
  {Bit-Verschiebung}
  mask0 := $FF shl Count;
  mask1 := mask0 xor $FF;
  b1 := 0;
  for i := High(Result) downto 0 do
  begin
    b0 := rol(Result[i], count);
    Result[i] := (b0 and mask0) or (b1 and mask1);
    b1 := b0;
  end;
end;

[Neutral General]

Hi,

So habe ichs im Prinzip auch gemacht. Allerdings mit shl und shr, statt rol :mrgreen:
Wobei die Methode mit rol wahrscheinlich noch ein Stückchen schneller ist schätze ich.