Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Elegant Bits tauschen
Narses - Mi 13.01.10 16:51
Titel: Elegant Bits tauschen
Moin!
Aufgabe: Die Bits X und Y einer Binärzahl tauschen.
Die grundsätzliche Lösung ist klar, das ist auch nicht wirklich schwer. :nixweiss: Der Witz ist: wie macht man das möglichst "elegant" (wenig Befehle/Bitoperationen, kein Assembler). :?:
Bin auf Vorschläge gespannt. ;)
cu
Narses
rizla - Mi 13.01.10 17:29
Wat gibt's denn zu gewinnen? ;)
"Kein Assembler" schließt ja alles aus (shl,shr, and)..
Aber gute Frage! Gleich mal abonnieren, das Thema!
Denn auch ich bin gespannt!
:r:
danielf - Mi 13.01.10 17:50
Man negiert die "input" Binärzahl. Das Ergebnis wird mit einer Zahl verknüpft (und) die die Bitstellen repräsentiert ( Bitstelle 3 und 5 ändern == 0010100).
Quelltext
1:
2:
3:
4:
5:
| Input: 1011001
Negiert: 0100110
Zu veränderte Stellen: 0010100
UND-Verknüpft: 1001101 |
oder willst du Code sehen? ;)
Gruß Daniel
rizla - Mi 13.01.10 17:55
"AND" ist aber Assembler. Damit leider an der Aufgabenstellung vorbei.. :(
danielf - Mi 13.01.10 18:05
Naja, ist nicht alles letztendlich Assembler?
Xentar - Mi 13.01.10 18:13
 danielf hat folgendes geschrieben  : |
Quelltext 1:
2:
3:
4:
| Negiert: 0100110
Zu veränderte Stellen: 0010100
UND-Verknüpft: 1001101 |
|
Bei dem UND, das ich kenne, wäre das Ergebnis ja 0000100. Kann es sein, dass du XOR meinst? ;)
danielf - Mi 13.01.10 18:23
Hm.. wohl dann keine elegante Lösung mehr. Und mittlerweile stolpere ich auch über das Verb "tauschen".
Ist damit gemeint die Position oder der Wert des Bits toggeln?
BenBE - Mi 13.01.10 18:24
hmmm, warte:
Nehmen wir die (Binär-)Zahl 76543210 und die Maske 00010010, dann erhalten wir:
Quelltext
1:
2:
| 76543210 xor ((not 76543210) and 00010010) =
76543210 xor (000~400~10) = ... |
alles andere als das, was ich denke, woarauf
Narses hinaus will ...
Wenn ich seinen Post richtig verstanden habe, möchte er anhand der oben gegebenen Maske 76513240 als Ergebnis.
Narses - Mi 13.01.10 18:55
Moin!
| rizla hat folgendes geschrieben : |
| Wat gibt's denn zu gewinnen? ;) |
Ein herzliches "Prost!" :beer: ;)
| rizla hat folgendes geschrieben : |
| "Kein Assembler" schließt ja alles aus (shl,shr, and).. |
Nein, durchaus nicht, steht aber auch oben, Bitoperationen sind erlaubt (and, or, xor, not, shl, shr), aber möglichst wenige. :idea: Es soll schlussendlich eine Delphi-Funktion (oder von mir aus auch PHP) werden, die etwa so aussieht:
Delphi-Quelltext
1:
| function SwapBits(Value: Cardinal; const BitX, BitY: Byte): Cardinal; |
Vielleicht sagt´s das etwas genauer.
| danielf hat folgendes geschrieben : |
| oder willst du Code sehen? ;) |
Es würde mich nicht stören. :P Aber vermutlich hast du die Aufgabe noch nicht richtig verstanden (s.u.).
| BenBE hat folgendes geschrieben : |
| Wenn ich seinen Post richtig verstanden habe, möchte er anhand der oben gegebenen Maske 76513240 als Ergebnis. |
Jup, ich möchte den Wert des Bits an Position X mit dem an Position Y tauschen (Bits fangen bei Nr. 0 an). ;)
cu
Narses
Jakob_Ullmann - Mi 13.01.10 19:26
Hört sich interessant an! Meine Funktion ist ja schon mal viel zu lang geworden.
JDF - Mi 13.01.10 19:30
Hallo!
meinst Du das so:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte);
var
Maske: Integer;
Temp: Integer;
begin
Maske := (1 shl BitX) or (1 shl BitY);
Temp := (Value and Maske);
if (Temp <> 0) and (Temp <> Maske)
then Value := Value xor Maske;
end; |
Gruß
Jürgen
BenBE - Mi 13.01.10 19:32
Also erstmal GANZ simpel ...
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| function SwapBits(Value: Cardinal; const BitX, BitY: Byte): Cardinal;
var
Mask1, Mask2: Cardinal;
Mask1set, Mask2set: Boolean;
begin
Mask1 := 1 shl BitX;
Mask2 := 1 shl BitX;
Mask1set := 0 <> Value and Mask1;
Mask2set := 0 <> Value and Mask2;
Result := (Value and (not (Mask1 or Mask2))) or
(Ord(Mask1Set) * Mask2) or
(Ord(Mask2Set) * Mask1);
ene; |
Will man die Multiplikation noch raushaben, geht das so:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| function SwapBits(Value: Cardinal; const BitX, BitY: Byte): Cardinal;
var
Mask1, Mask2: Cardinal;
Mask1set, Mask2set: Boolean;
begin
Mask1 := 1 shl BitX;
Mask2 := 1 shl BitY;
Mask1set := 0 <> Value and Mask1;
Mask2set := 0 <> Value and Mask2;
Result := (Value and (not (Mask1 or Mask2))) or
(-Ord(Mask1Set) and Mask2) or
(-Ord(Mask2Set) and Mask1);
ene; |
Wobei in C sieht das irgendwie besser aus:
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| uint32_t SwapBits(uint32_t Value, uint8_t BitX, uint8_t BitY) {
uint32_t Mask1, Mask2;
uint32_t Mask1set, Mask2set;
Mask1 := 1 << BitX;
Mask2 := 1 << BitY;
Mask1set := -!(Value & Mask1);
Mask2set := -!(Value & Mask2);
Result := (Value & ~(Mask1 | Mask2)) |
(~Mask1Set & Mask2) | (~Mask2Set & Mask1);
} |
Ob man's weiter gekürzt bekommt, weiß ich aber grad nicht ...
Sirke - Mi 13.01.10 22:05
Das Tauschen der Bits muss ja nur vorgenommen werden, wenn die beiden Bits unterschiedlich sind. Sind beide Bits gleich, dann verändert ein Swap die Zahl nicht!
Daher würde ich erst die Bits auf Gleichheit prüfen:
Quelltext
1:
| Bit = ( (Value >> BitX) XOR (Value >> BitY) ) AND 1 |
Nur im Falle von
Bit == 1 muss weiter gemacht werden und die Bits geswappt werden:
Quelltext
1:
| NewValue = Value XOR ( (1 << BitX) OR (1 << BitY) ) |
Sofern eine if-Abfrage nicht erlaubt ist, kann man mit dem Wert von Bit Weiter machen, da dieser bei Ungleichheit
1 ist:
Quelltext
1:
2:
| Bit = ( (Value >> BitX) XOR (Value >> BitY) ) AND 1;
NewValue = Value XOR ( (Bit << BitX) OR (Bit << BitY) ) |
Der Aufwand wäre: 4 Shifts, 2 XOR, 1 OR und 1 AND, wobei ich denke diese Formel noch vereinfacht werden kann!
FinnO - Mi 13.01.10 22:28
möchte wer meine String-Implemenation ohne AND, XOR usw. sondern nur durch IF...THEN in For-schleifen? :mrgreen:
Horst_H - Mi 13.01.10 22:52
Hallo,
Genau, erstmal die BitX/BitY auf Ungleichheit prüfen.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
| function SwapBits2(Value: Cardinal; const BitX, BitY: Byte): Cardinal;
var
Mask : Cardinal;
begin
result := value;
IF BitX <> BitY then
begin
Mask := 1 shl BitX OR 1 shl BitY;
value := value AND Mask; IF (value <> 0) AND (value <> Mask) then
Result := Result XOR Mask;
end;
end; |
Aber ich schätze mal, dass ohne die Verwendung von If die Version von Sirke am schnellsten läuft.
Gruß Horst
Narses - Do 14.01.10 00:04
Moin!
Ich denke, der Pokal geht im Wesentlichen an
Sirke: :beer: Warum? Zweizeiler ohne Variablen (ich unterstelle mal, dass man als Programmierer in der Lage ist, die Funktion bei gleichen Bit-Nummern nicht aufzurufen). Da ich nach einer "eleganten" Lösung fragte und diese zugegeben im Auge des Betrachters liegt, geht der Eleganz-Punkt aber an
JDF, da in seinem Ansatz das erste Mal die Idee mit der XOR-Maske zum Tauschen der Bitwerte auftaucht (genau sowas hatte ich gesucht). ;)
Hier mein Extrakt:
Delphi-Quelltext
1:
2:
3:
4:
5:
| procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte);
begin
if ( ( (Value shr BitX) XOR (Value shr BitY) ) AND 1 ) <> 0 then
Value := Value XOR ( (1 shl BitX) OR (1 shl BitY) );
end; |
Zwischenzeitlich hat sich herausgestellt, dass eine Prozedur mit Referenzparameter für mich praktischer ist. :nixweiss:
Vielen Dank an alle für die konstruktiven Ideen. :zustimm:
cu
Narses
BenBE - Do 14.01.10 00:17
Hmmm, das dürfte sich auch noch Ohne If darstellen lassen:
Delphi-Quelltext
1:
2:
3:
4:
| procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte);
begin
Value := Value XOR ( ((1 shl BitX) OR (1 shl BitY)) * ( ((Value shr BitX) XOR (Value shr BitY)) AND 1 ) ) ;
end; |
Damit vermeidet man (wenn vom Compiler korrekt umgesetzt) eine Branch-Misprediction, was noch mal etwas Performance bringt. Ändert aber an
Sirke's Vorlage nicht viel ...
@
Narses: Einzeiler-Alert ;-)
Anmerkung: Bei gleichen Bitnummern ergibt die Bedingung immer False und somit ist die Funktion somit einfach ein längeres NOP ;-)
Moderiert von BenBE: Klammern ergänzt / korrigiert
JDF - Do 14.01.10 11:17
Danke für den Eleganz-Punkt !!
noch einen Vorschlag:
Du kannst bei mehreren Swaps ein Array mit den Masken anlegen und Laufzeit sparen.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
| procedure SwapBits(var Value: Cardinal; Maske: Cardinal); overload;
var
Temp: Cardinal;
begin
Temp := (Value and Maske);
if (Temp <> 0) and (Temp <> Maske)
then Value := Value xor Maske;
end;
var
Masks01: array[0..3] of Cardinal = (
$00000084
, $00008400
, $00840000
, $84000000
);
procedure SwapMasks(var Value: Cardinal; const Masks: array of Cardinal);
var
i: Integer;
begin
for i := 0 to High(Masks) do SwapBits( Value, Masks[i] );
end;
procedure TForm1.Button1Click(Sender: TObject);
var
Value: Cardinal;
begin
Value := $F0F0F0F0;
SwapMasks( Value, Masks01 );
end; |
Gruß
Jürgen
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!