Autor |
Beitrag |
Narses
Beiträge: 10182
Erhaltene Danke: 1255
W10ent
TP3 .. D7pro .. D10.2CE
|
Verfasst: Mi 13.01.10 16:51
Moin!
Aufgabe: Die Bits X und Y einer Binärzahl tauschen.
Die grundsätzliche Lösung ist klar, das ist auch nicht wirklich schwer. Der Witz ist: wie macht man das möglichst "elegant" (wenig Befehle/Bitoperationen, kein Assembler).
Bin auf Vorschläge gespannt.
cu
Narses
_________________ There are 10 types of people - those who understand binary and those who don´t.
|
|
rizla
Beiträge: 417
Erhaltene Danke: 2
XP
FPC mit Lazarus
|
Verfasst: 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:
_________________ if you have what they want - they'll find a way to take it (bruce sterling)
WOW - 10 JAHRE Mitglied beim Delphi-Forum. Wie die Zeit vergeht, Freunde.
|
|
danielf
Beiträge: 1012
Erhaltene Danke: 24
Windows XP
C#, Visual Studio
|
Verfasst: 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
Beiträge: 417
Erhaltene Danke: 2
XP
FPC mit Lazarus
|
Verfasst: Mi 13.01.10 17:55
"AND" ist aber Assembler. Damit leider an der Aufgabenstellung vorbei..
_________________ if you have what they want - they'll find a way to take it (bruce sterling)
WOW - 10 JAHRE Mitglied beim Delphi-Forum. Wie die Zeit vergeht, Freunde.
|
|
danielf
Beiträge: 1012
Erhaltene Danke: 24
Windows XP
C#, Visual Studio
|
Verfasst: Mi 13.01.10 18:05
Naja, ist nicht alles letztendlich Assembler?
|
|
Xentar
Beiträge: 2077
Erhaltene Danke: 2
Win XP
Delphi 5 Ent., Delphi 2007 Prof
|
Verfasst: Mi 13.01.10 18:13
_________________ PROGRAMMER: A device for converting coffee into software.
|
|
danielf
Beiträge: 1012
Erhaltene Danke: 24
Windows XP
C#, Visual Studio
|
Verfasst: Mi 13.01.10 18:17
ups richtig
Wie hieß das Teil nochmal? Ah... Die ausschließende Disjunktion negiert
|
|
danielf
Beiträge: 1012
Erhaltene Danke: 24
Windows XP
C#, Visual Studio
|
Verfasst: 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
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Narses
Beiträge: 10182
Erhaltene Danke: 1255
W10ent
TP3 .. D7pro .. D10.2CE
|
Verfasst: Mi 13.01.10 18:55
Moin!
rizla hat folgendes geschrieben : | Wat gibt's denn zu gewinnen? |
Ein herzliches "Prost!"
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. 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. 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
_________________ There are 10 types of people - those who understand binary and those who don´t.
|
|
Jakob_Ullmann
Beiträge: 1747
Erhaltene Danke: 15
Win 7, *Ubuntu GNU/Linux*
*Anjuta* (C, C++, Python), Geany (Vala), Lazarus (Pascal), Eclipse (Java)
|
Verfasst: Mi 13.01.10 19:26
Hört sich interessant an! Meine Funktion ist ja schon mal viel zu lang geworden.
|
|
JDF
Beiträge: 29
WinNT, Win2k, WinXP, Win2003
d6ent, d7pro, bds2006ent, vs2003
|
Verfasst: 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
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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 ...
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Sirke
Beiträge: 208
Erhaltene Danke: 2
|
Verfasst: 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
Beiträge: 1331
Erhaltene Danke: 123
Mac OSX, Arch
TypeScript (Webstorm), Kotlin, Clojure (IDEA), Golang (VSCode)
|
Verfasst: Mi 13.01.10 22:28
möchte wer meine String-Implemenation ohne AND, XOR usw. sondern nur durch IF...THEN in For-schleifen?
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
Beiträge: 10182
Erhaltene Danke: 1255
W10ent
TP3 .. D7pro .. D10.2CE
|
Verfasst: Do 14.01.10 00:04
Moin!
Ich denke, der Pokal geht im Wesentlichen an Sirke: 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.
Vielen Dank an alle für die konstruktiven Ideen.
cu
Narses
_________________ There are 10 types of people - those who understand binary and those who don´t.
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
JDF
Beiträge: 29
WinNT, Win2k, WinXP, Win2003
d6ent, d7pro, bds2006ent, vs2003
|
Verfasst: 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.
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
|
|
|