Forum
 
Fragen
 
Suchen
 
Über Uns
 
 

Entwickeln eines Algorithmus, bei dem 2 Teile von 2 Dual Zahlen getauscht werden!?
Neue Frage »

14.10.2012, 19:23 Auf diesen Beitrag antworten »
Matze84 Entwickeln eines Algorithmus, bei dem 2 Teile von 2 Dual Zahlen getauscht werden!?

Meine Frage:
Hallo zusammen.
Ich habe eine Bitte.
In meiner letzten Vorlesung wurde folgende Aufgabe behandelt. Leider war nicht genug Zeit um da alle Fragen zum Verständnis zu stellen und trotzdem sollen wir eine ähnliche Aufgabe allein lösen.

Ich befinde mich in der Sprache "C" und es sollen nur Bitoperatoren verwendet werden.

Aufgabe:
Es ist eine Zahl x von der Bit-Position "p" an um "n" Stellen (nach Rechts) zu komplementieren. Das äußerste rechte Bit hat die Position 0.

Gegeben sind z.B.
x= 0123
p=4
n=2

x= 01010011
x_{Ergebnis} = 01001011

Die Fettgedruckten Zahlen sind quasi komplementiert worden.

Meine Ideen:
Die Lösung quasi ist:
#include <stdio.h>
main()
{
unsigned x=0123;
int p=4, n=2;
x=x^(~(~0<<n)<<(p+1-n));
printf("%o",x);
}
Ich habe es mit der Aufgabe und einem weiteren Beispiel probiert (und es funktioniert offensichtlich tatsächlich), weiß aber leider nicht Ansatzweise, wie man darauf kommen soll.
Kann mir bitte bitte jmd helfen bzw sagen wie man an sowas rangeht?

PS: In der Aufgabe die ich eigentlich lösen soll, sollen 2 Blöcke von Zahlen vertauscht werden.
Bsp.:
p=5
n=3
x=10110111
y=00011010
Ergebnis:
x=10010111
 
 
15.10.2012, 00:33 Auf diesen Beitrag antworten »
Karlito

Hallo,

leider weis ich nicht ganz, wo Dein Problem liegt. Ist es, dass du das Programm und die Operationen nicht verstehst oder Du nicht weist wie man darauf kommt?

In jedem Fall empfehle ich Dir, das Programm zu verstehen. Wenn Du die Einzelkomponenten des Ausdrucks
code: 
1:
2:
3:

x=x^(~(~0<<n)<<(p+1-n));

verstanden hast, wird sicher auch klar, wie man darauf kommt. Ein wenig Erfahrung vorrausgesetzt, kommt man früher oder später selbst auf solche Ausdrücke.

Um den Ausdruck zu verstehen nimmst du Ihn am besten Stück für Stück auseinander und lässt dir ausgaben erzeugen, welche dir ersichtlich machen, was da passiert.

code: 
1:
2:
3:
4:
5:

printf("%o\n", (~0<<n));
printf("%o\n", (~0<<n)<<(p+1-n));
printf("%o\n", (~(~0<<n)<<(p+1-n)));


Sowas in der Art.

Ich hoffe ich konnte weiterhelfen.

VG,

Karlito
15.10.2012, 06:53 Auf diesen Beitrag antworten »
Matze84

Zitat:
Original von Karlito
Hallo,

leider weis ich nicht ganz, wo Dein Problem liegt. Ist es, dass du das Programm und die Operationen nicht verstehst oder Du nicht weist wie man darauf kommt?

In jedem Fall empfehle ich Dir, das Programm zu verstehen. Wenn Du die Einzelkomponenten des Ausdrucks
code: 
1:
2:
3:

x=x^(~(~0<<n)<<(p+1-n));



Hallo Karlito
Also das Programm als solches kann ich nachvollziehen...
habe mir auch mal Zettel und Stift geschnappt gehabt und bin es Schritt für Schritt durchgegangen.

Also erst die "0" komplementieren, dann um "n" stellen nach links schieben und so weiter.
Die Bit-Operatoren versteh ich glaub ich auch smile
Nur weiß ich wie gesagt nicht, wie man Anhand des Problems auf SO einen Algorithmus (Codezeile) kommt.

Ich habe inzwischen für mein eigentliches Problem, für das das hier ja das Beispiel ist eine einzige Lösung gefunden.
Die Funktioniert aber nur an EINEM Exemplar.
Kann also NICHT auf alle Zahlen angewendet werden unglücklich

Ich hoffe jetzt ist mein Problem etwas verständlicher *g*

Lg Matze
15.10.2012, 21:50 Auf diesen Beitrag antworten »
Karlito

Hi,

naja, ist es Anforderung, den Ausdruck mit einer Zeile zu bewältigen? Wenn nicht, mach es doch erst einmal so naiv wie nötig und taste dich langsam ran.

Es ist sowieso die frage, wie sinnvoll es ist, solche Ausrücke in nur eine Zeile zu schreiben. Im Endeffekt sind Programmiersprachen ja nicht für den Rechner gemacht, sondern für Menschen, welche es auch verstehen wollen. Sonst könnte man auch in Assembler oder binärcode programmieren...

Aber wenn du wissen willst, wie man an sowas rangeht: Divide and Conquer! Also zerlege das Problem erst einmal in Teilschritte.

In deinem Beispiel hätte mich erst einmal interessiert, wie man einen Bitflip realisiert. Das geht bekanntlich mit XOR. Also braucht es in C ein binäres XOR als Grundlegende Operation.
Weiterhin muss man eine "Maske" für den Flip erzeugen. Ich persönlich hätte naiv 2^n-1 gewählt, wobei n die Anzahl der zu ändernden bits ist. Danach nur noch eine Verschiebung der Maske nach links. Leider kann es sein, dass dies schief gehtl, wenn man alle bits flippen möchte (das habe ich nicht ausprobiert).

Du siehst also man muss sich an die Lösung heranarbeiten und dann ein wenig experimentieren. Mit Erfahung geht das dann alles schneller....

Dein spezielles Problem kannst du ja mal posten. wenn das möglich ist. Ich würde dann versuchen dich zur Lösung zu lotsen...

VG,

Karlito
 Anzeige
 
16.10.2012, 14:30 Auf diesen Beitrag antworten »
Matze84

Danke schon mal im vorraus.
Also ich zitiere wörtlich aus http://dblabor.fh-stralsund.de/pr1/index.html
aufg01.pdf

Schreiben Sie ein Programm (wie in der Vorlesung), das eine Zahl x so verändert, daß die von der Position p an rechten n Bits von x durch die n am weitesten rechts stehenden Bits einer Zahl y ersetzt werden. Das am weitesten rechts stehende Bit einer Zahl hat die Position 0.

Programmeingabe: x,y,p,n

Beispiel:
Eingabe:
p=5,
n=3,
x= 10110111
y= 00011010

Ausgabe:
x = 10010

MEINE IDEEN:
Also ich bin bisher soweit gekommen.
00000000 komplementieren
11111111 das um 3(n) stellen nach links verschieben
11111000 das wieder komplementieren
00000111 diese zahl sei mal "z"

dann habe ich y
00011010 um 3(n) stellen nach links verschoben
11010000 diese zahl habe ich mit "z" über ein ODER verglichen
ALSO
11010000 (mein verschobenes y)
ODER
00000111 (mein z)
11010111 (y ODER z)
(y ODER z) habe ich mit x über ein UND verglichen
ALSO
11010111 (y ODER z)
UND
10110111 (x)
10010111 (x UND(y ODER z))

Problem ist das das nicht allgemeingültig ist.
Also das stimmt nur, wenn ich GENAU die Parameter habe, die oben stehen, aber das soll ja quasi variabel sein. unglücklich

Gedankentechnisch ist mir klar, das ich bestimmt etwas um "n" und "p" verschieben muss.
Ich müsste also die n Bits von y irgendwie unter die n Bits von x kriegen und das dann gewissermaßen vergleichen damit ich aufs Ergebnis komme.

Wie gesagt Danke schonmal für deine Hilfe.
Lg Matze

EDIT: ich hoffe man kann das lesen Augenzwinkern
16.10.2012, 18:42 Auf diesen Beitrag antworten »
Karlito

Hallo,

Zitat:
Original von Matze84
EDIT: ich hoffe man kann das lesen Augenzwinkern


Es ist alles lesbar. Jedoch erscheinen mir deine Operationen etwas wild...

Zitat:
Original von Matze84
Gedankentechnisch ist mir klar, das ich bestimmt etwas um "n" und "p" verschieben muss.
Ich müsste also die n Bits von y irgendwie unter die n Bits von x kriegen und das dann gewissermaßen vergleichen damit ich aufs Ergebnis komme.


Die betroffenen Bits des Wortes y so zurechtzuschieben ist eine gute Idee. Danach würde ich dir jedoch raten, bei der "Zusammenführung" der beiden Wörter, erst einmal dei Wörter vorzubereiten, indem du alle Stellen, die nicht relevant sind löschst. D.h. die betroffenen Stellen in X, die geändert werden sollen und alle Stellen, welche aus y nicht gebraucht werden.

Ich will nicht zu viel verraten. Wenn der Tipp nicht reicht, kannst du ja noch mal nachhaken.

VG,

Karlito
16.10.2012, 19:38 Auf diesen Beitrag antworten »
Matze84

ja hab ich verstanden smile (glaub ich)

Ich schreibe einfach mal auf, wie ichs im Programm schreiben würde.
code: 
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:

#include<stdio.h>
main()
{
unsigned x,y,z,z2,z3,z4,erg;
int p,n;
printf("Geben Sie "X" als Oktalzahl ein.\n");
scanf("%o", x);
printf("Geben Sie "Y" als Oktalzahl ein.\n");
scanf("%o",y);
printf("Geben Sie "p" als Dezimalzahl ein.\n");
scanf("%d",p);
printf("Geben Sie "n" als Dezimalzahl ein.\n");
scanf("%d",n);

z=x>>(p+1); 
z=z<<(p+1); 

z2=x<<(15-p+n);
z2=z2>>(15-p+n);

z3=z2|z;

z4=y<<(16-n);
z4=z4>>(15-p);

erg=z4|z3;
printf("das Ergebnis ist: %o\n",erg);
}


Bitte sag mir das das stimmt großes Grinsen Gott
Obwohl ich zugeben muss, das ich mir bei den ganzen printf und scanf nicht ganz sicher bin.
16.10.2012, 19:58 Auf diesen Beitrag antworten »
Karlito

Hi,

ist leider nicht korrekt. Irgendwie bist du sehr im binären Oder verhaftet.

Zum Ausprobieren hier noch mal dein Programm kompilierfähig:

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

#include<stdio.h>
main()
{
	unsigned x,y,z,z2,z3,z4,erg;
	int p,n;
	printf("Geben Sie \"X\" als Oktalzahl ein.\n");
	scanf("%o", &x);
	printf("Geben Sie \"Y\" als Oktalzahl ein.\n");
	scanf("%o", &y);
	printf("Geben Sie \"p\" als Dezimalzahl ein.\n");
	scanf("%d", &p);
	printf("Geben Sie \"n\" als Dezimalzahl ein.\n");
	scanf("%d", &n);

	z=x>>(p+1); 
	z=z<<(p+1); 

	z2=x<<(15-p+n);
	z2=z2>>(15-p+n);

	z3=z2|z;

	z4=y<<(16-n);
	z4=z4>>(15-p);

	erg=z4|z3;
	printf("das Ergebnis ist: %o\n",erg);
}


Ich habe folgende Eingaben gewählt alles Oktal:

X=777
Y=221
n=5
p=3

Das Ergebnis müsste ja 717 sein. Dein Programm liefert aber 2777.

Noch 2 Tipps:
- Kann man mit einem Binären oder Bitstellen löschen?
- Welcher binäre operator wäre dazu geignet?

Erstelle dir doch mal die Wahrheitstabellen von & | und ^ mit nur einem Bit.

VG,

Karlito
16.10.2012, 20:47 Auf diesen Beitrag antworten »
Matze84

Habe den Fehler mit einem Kumpel gefunden....
Ich habe ein 64-bit System und damit sind die unsigned offensichtlich 32bit statt 16bit lang...

Folgende Änderung bezüglich der Verschiebungen.
code: 
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:
32:

#include<stdio.h>

main()
{
	unsigned x,y,z,z2,z3,z4,erg;
	int p,n;
	printf("Geben Sie \"X\" als Oktalzahl ein.\n");
	scanf("%o", &x);
	printf("Geben Sie \"Y\" als Oktalzahl ein.\n");
	scanf("%o", &y);
	printf("Geben Sie \"p\" als Dezimalzahl ein.\n");
	scanf("%d", &p);
	printf("Geben Sie \"n\" als Dezimalzahl ein.\n");
	scanf("%d", &n);

	z=x>>(p+1); 
	z=z<<(p+1); 

	z2=x<<(31-p+n); //bei einem 32-bit System die 31 durch eine 15 ersetzen
	z2=z2>>(31-p+n); //bei einem 32-bit System die 31 durch eine 15 ersetzen

	z3=z2|z;

	z4=y<<(32-n); //bei einem 32-bit System die 32 durch eine 16 ersetzen
	z4=z4>>(31-p); //bei einem 32-bit System die 31 durch eine 15 ersetzen

	erg=z4|z3;
	printf("das Ergebnis ist: %o\n",erg);
	scanf("%d",&p);
}

Damit funktioniert es offensichtlich...

Aber was genau meinst du mit:
Zitat:

Noch 2 Tipps:
- Kann man mit einem Binären oder Bitstellen löschen?
- Welcher binäre operator wäre dazu geignet?

Weil das will ich trotzdem probieren denn ich soll ja "besser" werden Augenzwinkern
Lg Matze
16.10.2012, 21:50 Auf diesen Beitrag antworten »
Karlito

Hi,

habe erstmal kein Gegenbeispiel gefunden (und war ehrlich gesagt grad zu faul dein Programm zu durchdenken).

Naja, was ich mit meinen Tipps meinte ist, wenn du zum beispiel folgendes Wort hast:
1010111011 und du willst die Bits 5 - 3 löschen so dass das Wort
1010000011 entsteht. Wie würdest du das anstellen? Man kann das sehr einfach mit einer Logischen Operation und einer "Maske" erreichen. Hast du da eine Idee?

VG,

Karlito
18.10.2012, 18:47 Auf diesen Beitrag antworten »
Matze84

Ich habe eine Lösung gefunden und sie scheint super zu funktionieren....
Um etwas zu löschen, muss ich die entsprechende Stelle mit einem & und 0 vergleichen, den Rest mit 1

Hier mal mein Ergebnis.


Ich weiß es ist in einer Zeile geschrieben und nicht so übersichtlich.

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

unsigned x,y,erg;
        int n,p;
        printf("Geben Sie \"X\" als Oktalzahl ein.\n");
        scanf("%o",&x);
        printf("Geben Sie \"Y\" als Oktalzahl ein.\n");
        scanf("%o",&y);
        printf("Geben Sie \"p\" als Dezimalzahl ein.\n");
        scanf("%d",&p);
        printf("Geben Sie \"n\" als Dezimalzahl ein.\n");
        scanf("%d",&n);
        erg=(x&~(~(~0<<n)<<(p-n+1)))|((y&~(~0<<n))<<(p-n+1));
        printf("das Ergenis ist: %x als Hexadezimalzahl\n",erg);
        scanf("%o",&x);
        return 0;
18.10.2012, 18:57 Auf diesen Beitrag antworten »
Karlito

Hi,

super gelöst. Das ist es, worauf ich hinauswollte.

VG,

Karlito
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


Informatiker Board » Themengebiete » Praktische Informatik » Entwickeln eines Algorithmus, bei dem 2 Teile von 2 Dual Zahlen getauscht werden!?

 
© 2005-2019 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen