Autor Beitrag
Narses
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10181
Erhaltene Danke: 1254

W10ent
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: 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. :nixweiss: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 417
Erhaltene Danke: 2

XP
FPC mit Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 1012
Erhaltene Danke: 24

Windows XP
C#, Visual Studio
BeitragVerfasst: 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).


ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 417
Erhaltene Danke: 2

XP
FPC mit Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 1012
Erhaltene Danke: 24

Windows XP
C#, Visual Studio
BeitragVerfasst: Mi 13.01.10 18:05 
Naja, ist nicht alles letztendlich Assembler?
Xentar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2077
Erhaltene Danke: 2

Win XP
Delphi 5 Ent., Delphi 2007 Prof
BeitragVerfasst: Mi 13.01.10 18:13 
user profile icondanielf hat folgendes geschrieben Zum zitierten Posting springen:
ausblenden 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? ;)

_________________
PROGRAMMER: A device for converting coffee into software.
danielf
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 1012
Erhaltene Danke: 24

Windows XP
C#, Visual Studio
BeitragVerfasst: Mi 13.01.10 18:17 
ups richtig :)

Wie hieß das Teil nochmal? Ah... Die ausschließende Disjunktion negiert
danielf
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 1012
Erhaltene Danke: 24

Windows XP
C#, Visual Studio
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Mi 13.01.10 18:24 
hmmm, warte:

Nehmen wir die (Binär-)Zahl 76543210 und die Maske 00010010, dann erhalten wir:

ausblenden Quelltext
1:
2:
76543210 xor ((not 76543210) and 00010010) =
76543210 xor (000~400~10) = ...


alles andere als das, was ich denke, woarauf user profile iconNarses 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10181
Erhaltene Danke: 1254

W10ent
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: Mi 13.01.10 18:55 
Moin!

user profile iconrizla hat folgendes geschrieben Zum zitierten Posting springen:
Wat gibt's denn zu gewinnen? ;)
Ein herzliches "Prost!" :beer: ;)

user profile iconrizla hat folgendes geschrieben Zum zitierten Posting springen:
"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:
ausblenden Delphi-Quelltext
1:
function SwapBits(Value: Cardinal; const BitX, BitY: Byte): Cardinal;					
Vielleicht sagt´s das etwas genauer.

user profile icondanielf hat folgendes geschrieben Zum zitierten Posting springen:
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.).

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1747
Erhaltene Danke: 15

Win 7, *Ubuntu GNU/Linux*
*Anjuta* (C, C++, Python), Geany (Vala), Lazarus (Pascal), Eclipse (Java)
BeitragVerfasst: Mi 13.01.10 19:26 
Hört sich interessant an! Meine Funktion ist ja schon mal viel zu lang geworden.
JDF
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 29

WinNT, Win2k, WinXP, Win2003
d6ent, d7pro, bds2006ent, vs2003
BeitragVerfasst: Mi 13.01.10 19:30 
Hallo!

meinst Du das so:

ausblenden 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 <> 0and (Temp <> Maske)
  then Value := Value xor Maske;
end;


Gruß
Jürgen
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Mi 13.01.10 19:32 
Also erstmal GANZ simpel ...

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

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


ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 208
Erhaltene Danke: 2



BeitragVerfasst: 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:
ausblenden 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:
ausblenden 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:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1331
Erhaltene Danke: 123

Mac OSX, Arch
TypeScript (Webstorm), Kotlin, Clojure (IDEA), Golang (VSCode)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Mi 13.01.10 22:52 
Hallo,

Genau, erstmal die BitX/BitY auf Ungleichheit prüfen.
ausblenden 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; //value mal kurz anders verwendet
    //Bits der Position BitX/BitY unterscheiden sich 
    IF (value <> 0AND (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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10181
Erhaltene Danke: 1254

W10ent
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: Do 14.01.10 00:04 
Moin!

Ich denke, der Pokal geht im Wesentlichen an user profile iconSirke: :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 user profile iconJDF, 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:
ausblenden 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

_________________
There are 10 types of people - those who understand binary and those who don´t.
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Do 14.01.10 00:17 
Hmmm, das dürfte sich auch noch Ohne If darstellen lassen:

ausblenden 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 user profile iconSirke's Vorlage nicht viel ...

@user profile iconNarses: Einzeiler-Alert ;-)

Anmerkung: Bei gleichen Bitnummern ergibt die Bedingung immer False und somit ist die Funktion somit einfach ein längeres NOP ;-)

Moderiert von user profile iconBenBE: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 29

WinNT, Win2k, WinXP, Win2003
d6ent, d7pro, bds2006ent, vs2003
BeitragVerfasst: 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.

ausblenden volle Höhe 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 <> 0and (Temp <> Maske)
  then Value := Value xor Maske;
end;

var
  Masks01: array[0..3of 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