Problem mit einem kompliziertem Ausdruck

unsigned snoob( unsigned x ) 
{
unsigned smallest , ripple , ones;			/* Definiert 3 Variablen vom Typ unsigned int */
smallest = x & -x;							/* smallest erhaelt den groessten Teiler von x, der eine Potenz von 2 ist */
ripple = x + smallest;						/* ripple erhaelt den Wert von x addiert mit smallest */
ones = x ^ ripple;							/**/
ones = (ones >> 2)/smallest;
return ripple | ones;
}

Es geht konkret um:

ones = x ^ ripple;							
ones = (ones >> 2)/smallest;

Ich habe jetzt händisch mit ein paar zufälligen werten probiert, was genau die Funktion machen könnte , ich komme aber nicht drauf, da mir die beiden Ausdrücke nicht genau verraten, was sie machen.

smallest = x & -x;

habe ich rausbekommen.

Könnt ihr mir vielleicht auf die Sprünge helfen?

Vielen lieben Dank

Bashar

wgerhtrj schrieb:

Es geht konkret um:
ones = x ^ ripple;							
ones = (ones >> 2)/smallest;
Ich habe jetzt händisch mit ein paar zufälligen werten probiert, was genau die Funktion machen könnte

Warum probieren? Hast du den ganzen Rest auch nur ausprobiert? Man kann sowas auch nachlesen.

https://www.google.de/search?q=c+operatoren

Hallo Bashar
Na klar kenne ich die Operationen.

Es geht konkret darum, herauszufinden, was die Funktion snoob macht.
Ich habe mir auch ne schleife gebaut, und einn paar werte eingegeben und geschaut, was die einzelnen Ausdrücke machen.

smallest = x & -x;

Dies gibt mir zum Beispiel den größten teiler von x, der eine Potenz von 2 ist.
Bsp: x = 2, smallest = 2;
x = 14, smallest = 2;
x = ungerade, smallest = 1;

Ich komme aber mir probieren nicht heraus, was die Funktion konkret macht.
Hier mal eine ausgabe für alle Zweierpotenzen, mit 2 beginnend und 512 endend:

smallest    2
ripple    4
ones    6
ones    0
snoob     4

1
smallest    4
ripple    8
ones    12
ones    0
snoob     8

1
smallest    8
ripple    16
ones    24
ones    0
snoob     16

1
smallest    16
ripple    32
ones    48
ones    0
snoob     32

1
smallest    32
ripple    64
ones    96
ones    0
snoob     64

1
smallest    64
ripple    128
ones    192
ones    0
snoob     128

1
smallest    128
ripple    256
ones    384
ones    0
snoob     256

1
smallest    256
ripple    512
ones    768
ones    0
snoob     512

1
smallest    512
ripple    1024
ones    1536
ones    0
snoob     1024

Die 1en am Anfang ignorieren bitte, die waren nur dazu da, auf Tastendruck den nächsten Schritt einzuleiten.

volkard

Mir erschließt sich der Sinn der Aufgabe nicht.

unsigned snoob( unsigned x )
{
//x=*****0111000 //statt 3 auch beliebig viele aber mindestens eine
unsigned smallest , ripple , ones;          /* Definiert 3 Variablen vom Typ unsigned int */
smallest = x & -x;                          /* smallest erhaelt den groessten Teiler von x, der eine Potenz von 2 ist */
//s=000000001000 //letze 1
ripple = x + smallest;                      /* ripple erhaelt den Wert von x addiert mit smallest */
//r=*****1000000 //rechteste einergruppe nullen, links davon eine 1 machen
ones = x ^ ripple;                          /**/
//o=000001111000 //nur die rechteste einergruppe und daneben eine 1 überleben
ones=ones/smallest;
//o=000000001111 //und sie wird an den rechten rand geschoben
ones = ones >> 2;
//o=000000000011 //einergruppe am rechten rand, hat eine 1 weniger als die rechteste
	//einergruppe von x
//o=000000011110
return ripple | ones;
//such die rechteste einergruppe
//verschiebe ihre linke 1 um eine stelle nach links
//verschiebe die anderen 1-en bis an den rand nach rechts
}

1 10
10 100
11 101
100 1000
101 110
110 1001
111 1011
1000 10000
1001 1010
1010 1100
1011 1101
1100 10001
1101 1110
1110 10011
1111 10111
10000 100000
10001 10010
10010 10100
10011 10101
…
1100100 1101000
1100101 1100110
1100110 1101001
1100111 1101011
1101000 1110000
1101001 1101010
1101010 1101100
1101011 1101101
1101100 1110001
1101101 1101110
1101110 1110011
1101111 1110111
1110000 10000011
1110001 1110010
1110010 1110100
1110011 1110101
1110100 1111000
1110101 1110110
1110110 1111001
1110111 1111011

volkard

x=7;
solange x<=(7<<3);
x=snoob(x);

zählt die (6 über 3) möglichkeiten auf, 3 bits von 6 zu setzen.

Hallo volkard.

Mir erschließt sich der Sinn der Aufgabe nicht.

Ich habe dem Lehrer jetzt die Aufgabe geschickt mit dem Vermerk, dass ich keine Ahnung habe, was die Funktion konkret macht, ich aber jeden einzelnen Schritt erklären kann.
Jetzt habe ich erfahren, dass dies der "Gosper-Algorithmus" ist.(Was zur Hölle...) Das höre ich gerade zum allerersten mal. Hab danach gegoogelt, und kann zwischen diesem Gospel und dem Listing keinen Zusammenhang erkennen.

Mir erschließt sich der Sinn der Aufgabe nicht.

Soll ich dir mal ein paar Aufgaben zeigen?
zB:

int x = 10, y = 20;
x = x++ + y++;
y = ++y + ++x;

Frage: Welche Werte haben x und y?
Meine Antwort: Ich habe ihm die Ausgabe meines Compilers geschrieben mit dem Anhang, dass dies ein undefiniertes Verhalten erzeugt.
Ergebnis: 0 Punkte, da Post- und Präinkrement immer gleiche Ergebnisse liefern, ist dieses Listing wohldefiniert...
Ich so: wtf..??!!

Wutz

Dein Lehrer hat keine Ahnung.
Da musst du leider mit leben.
Du kannst dich aber gleich daran gewöhnen, dass es im Leben oftmals Leute gibt, die von Dingen reden, von den sie keine Ahnung haben. Das hindert sie aber nicht daran, darüber zu reden, oftmals sogar sehen sie ihre Berufung darin, von Dingen zu reden, von denen sie keine Ahnung haben: Politiker,Manager,Lehrer,...

volkard

wgerhtrj schrieb:

Hallo volkard.

Mir erschließt sich der Sinn der Aufgabe nicht.

Ich habe dem Lehrer jetzt die Aufgabe geschickt mit dem Vermerk, dass ich keine Ahnung habe, was die Funktion konkret macht, ich aber jeden einzelnen Schritt erklären kann.
Jetzt habe ich erfahren, dass dies der "Gosper-Algorithmus" ist.(Was zur Hölle...) Das höre ich gerade zum allerersten mal. Hab danach gegoogelt, und kann zwischen diesem Gospel und dem Listing keinen Zusammenhang erkennen.

Ich meinte, was erwartet er, was Ihr davon lernt? Das ist doch keine lehrreiche Aufgabe, sondern schlichtes "Ich zeige Euch mal, daß ich viel schlauer bin".

wgerhtrj schrieb:

Mir erschließt sich der Sinn der Aufgabe nicht.

Soll ich dir mal ein paar Aufgaben zeigen?
zB:
int x = 10, y = 20;
x = x++ + y++;
y = ++y + ++x;
Frage: Welche Werte haben x und y?

dito.

wgerhtrj schrieb:

Meine Antwort: Ich habe ihm die Ausgabe meines Compilers geschrieben mit dem Anhang, dass dies ein undefiniertes Verhalten erzeugt.
Ergebnis: 0 Punkte, da Post- und Präinkrement immer gleiche Ergebnisse liefern, ist dieses Listing wohldefiniert...
Ich so: wtf..??!!

Leicht bessere Chanchen gehabt, wenn Du ein gut googlebares Wort wir Sequenzpunkte eingebaut hättest. In der Schule kann man gegen sowas noch den Aufstand proben…
Aber im Studium nicht mehr, da hat der Prof einfach Recht. Selbst vor Gericht, was könnte der Richter anderes machen, als den Prof fragen?
Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

Am besten, Du übst schonmal. Immer hübsch rausfinden, was er für Sachen falsch macht und die Antwort finden, auf die er am sichersten die volle Punktzahl gibt.

volkard

wgerhtrj schrieb:

Jetzt habe ich erfahren, dass dies der "Gosper-Algorithmus" ist.(Was zur Hölle...) Das höre ich gerade zum allerersten mal. Hab danach gegoogelt, und kann zwischen diesem Gospel und dem Listing keinen Zusammenhang erkennen.

Jo, Gosper's Algorithm ist auch was total anderes. "An Algorithm for finding closed form Hypergeometric Identities."

Für den Gosper's-Hack gibt es anscheinend inzwischen bessere Implementierungen, hier einer, der noch die Ursprüngliche Form nimmt.
http://read.seas.harvard.edu/cs207/2012/?p=64

Weils gerade passt:
http://www.pvv.org/~oma/DeepC_slides_oct2011.pdf

Bashar

volkard schrieb:

Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

Vielleicht wollte er darauf hinaus, dass es Polynomfunktionen sind.

volkard

Bashar schrieb:

volkard schrieb:

Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

Vielleicht wollte er darauf hinaus, dass es Polynomfunktionen sind.

Ähm, f(x)=5 ist doch auch eine Polynomfunktion, oder?

Das Fach war "Datensicherheit" oder sowas bei einem Lehrbeauftragten. Teil des Spezialisierungsschwerpunkts "Datenschutz". Helau, wer modernistisch tagesaktuellen unausgegorenen Schott belegt, und mehr Semesterwochenstunden abrockt, als sein müssten, verschwendet nicht nur seine Zeit, sondern senkt auch noch seine Note. Ähnliche Dinger gab es in jedem anderen Fach dieses Spezialisierungsschwerpunkts, außer bei "Kryptologie", das hielt eine Mathe-Prof. Da hätte ich beinahe eine 2 gekriegt, aber das war allein meine Schuld.

Es ging darum, uns Idioden-Studenten ein wenig begreiflich zu machen, daß es so manche Sachen gibt, die eher harmlos zu berechnen sind und manche, da steht man davor wie vor einer Wand. Lehrinhalte quasi aus der c't kopiert und wenn's nicht reicht, auch mal die Computerbild.

Sah ungefähr wir folgt aus:
(Hab schonmal angekreuzt, bei 'f' waren wir anderer Meinung.)

Bitte ankreuzen:

Die Funktion f ist...

f(x)    |  konstant | linear | quadratisch | polynomisch | exponentiell 
-----------------------------------------------------------------------
  2^x   |           |        |             |             |     x
-----------------------------------------------------------------------
   5    |     x     |        |             |      f      |
-----------------------------------------------------------------------
  x^2   |           |        |      x      |      x      |
-----------------------------------------------------------------------
   x^3  |           |        |             |      x      |
-----------------------------------------------------------------------
   x    |           |    x   |             |      f      |
-----------------------------------------------------------------------
(2^x)/x |           |        |             |             | x //wer die 1 verdient
-----------------------------------------------------------------------

Bashar

volkard schrieb:

Bashar schrieb:

volkard schrieb:

Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

Vielleicht wollte er darauf hinaus, dass es Polynomfunktionen sind.

Ähm, f(x)=5 ist doch auch eine Polynomfunktion, oder?

Ja, aber vielleicht kein Polynom (hängt von der vereinbarten Schreibweise ab).

(Ein Polynom ist durch seine Koeffizienten definiert und eine Funktion durch ihre Wertepaare, was bedeutet, dass zwei verschiedene Polynome als Funktion interpretiert gleich sein können.)

Aber da es bei dir anscheinend um Komplexitätsklassen ging, kann es das eher nicht gewesen sein BTW das ist komisch, weil polynomiale Laufzeit ja lediglich bedeutet, dass die Laufzeit asymptotisch durch ein Polynom beschränkt ist, also ist sogar log, Wurzel, Sinus etc. polynomiell, insbesondere natürlich 5 und x.

volkard

Abgesehen von dem Problemchen damals…

Bashar schrieb:

Ein Polynom ist durch seine Koeffizienten definiert und eine Funktion durch ihre Wertepaare, was bedeutet, dass zwei verschiedene Polynome als Funktion interpretiert gleich sein können.

Leuchtet mir sofort ein. Mir fällt nur gerade kein Fall ein. Bin wohl zu fest damit verhaftet, als Grundmenge die Reellen Zahlen zu nehmen.

Nehmen wir als Definition des Polynoms mal
http://de.wikipedia.org/wiki/Polynom#Definition

Kannste mir auf die Schnelle mal ein Beispiel liefern, damit ich darüber träumen kann? (Bin im Umzug, Fernseher weg, vermutlich endgültig, Mathe-Träumen ist gut, mach ich schon die letzten drei Tage.)

Bashar

Klar: x^2 + x\in\mathbb{F}_2[x] ist (als Funktion auf $\mathbb{F}_2$ ) überall 0.

volkard

Bashar schrieb:

Klar: x^2 + x\in\mathbb{F}_2[x] ist (als Funktion auf $\mathbb{F}_2$ ) überall 0.

lol!
klar.

Wenn schon, denn schon: 5 ist nicht nur konstant und polynomisch, sondern auch linear.

Überhaupt: 5 = 0 * x² + 5 ist auch quadratisch, und in welcher Mathematik bitte ist 2^x / x eine Exponentialfunktion? Lasst euch den Graphen mal plotten und vergleicht.

volkard

seldon schrieb:

Wenn schon, denn schon: 5 ist nicht nur konstant und polynomisch, sondern auch linear.

Uups, übersehen. http://de.wikipedia.org/wiki/Lineare_Funktion

seldon schrieb:

Überhaupt: 5 = 0 * x² + 5 ist auch quadratisch,

Nö, das dann doch nicht.
http://de.wikipedia.org/wiki/Quadratische_Funktion

seldon schrieb:

und in welcher Mathematik bitte ist 2^x / x eine Exponentialfunktion? Lasst euch den Graphen mal plotten und vergleicht.

Haste sie jetzt nur zwischen x=-2 und x=2 plotten lassen?
Also ich würde mal sagen 1.99^x < 2^x/x < 2^x für alle x>=1453, insofern ist sie mir für Komplexitätsüberlegungen exponentiell genug. Ist sie nicht?

Jaaaa...bei der quadratischen Funktion muss ich dir Recht geben. Ich hatte, zugegeben, nicht auf dem Schirm, dass a != 0 gefordert ist.

Bei der Exponentialfunktion sehe ich die Dinge dann aber doch anders. Ob eine Funktion eine Exponentialfunktion ist, hat erstmal wenig mit Komplexitätsklassen zu tun, und 2^x / x verhält sich in vielen Dingen anders als Exponentialfunktionen.

Wenn wir über Komplexitätsklassen reden wollen, sieht die Sache wieder ganz anders aus -- da sprechen wir ja größtenteils über Teilmengen. Eine Funktion, die zeitlich mit Θ(2^x / x) skaliert, ist in EXPTIME, aber das ist mit 5, x, x² und x³ auch der Fall. f(x) in O(1) impliziert f(x) in O(n²), aber f(x) in Θ(2^x/x) impliziert f(x) nicht in Θ(2^x), und beide dieser Dinge implizieren f(x) nicht in Θ(1.99^x). Was ist also unser Kriterium?