Hey Leute,
ich habe ein Problem mit Java auf Blatt 4 von RS!
Wir sollen Nor und Xor und andere Sachen implementieren.
Bin gerade bei Nor und stolpere immer wieder über eine blöde Sache bei Java:
Wir dürfen nur & und ~ benutzen…
aber ~ macht nicht das was ich erwarte!
wenn ich ~1 machen will, erwarte ich 0! Doch es wird -2 (klar, vorzeichenbit getauscht) und evt. halt 01 invertiert!
Jezz probier ich mit 4 und ich bekomme nicht wie erwartet -3 (100 -> 011) sondern -5 (101) wie merkwürdig ist das denn? Das kann ich dann aber auch nicht mehr mit 0100 invertiert erklären.. das wäre ja 1011 und somit -(3+8) = -11

Kann mir wer erklären was das blöde Komplement da immer macht? :| Wenn ich wenigstens ein Muster erkennen könnte :D

Liebe Grüße…

ich vermute, dass ~ ¬ sein soll?!
also "nicht"?

was ich an deinen text auch nicht versteh:
011 soll -3 sein
-wegen der führenden 0
aber 101 ist -5?

check ich nicht
weil es wäre entweder 1 (bei führende 1 = +) oder 5 aber -5?
mhmh…

Japp… Das bildet das Komplement in Java… also invertiert bitweise ;)

Waren in der Vorlesung schon verschiedene Repräsentationsarten von negativen Ganzzahlen dran? Java benutzt nämlich das Zweierkomplement für int-Werte. Der ~-Operator (Bitwise Not) verhält sich bei dir genau so, wie er soll - was man aber nur verstehen kann, wenn man das Zweierkomplement kennt.

Dein Beispiel:

Der Wert 4 hat als 32-bit-Wert im Speicher die binäre Repräsentation 00000000000000000000000000000100. Dein ~-Operator invertiert nun alle Bits, also entspricht der Wert von ~4 dem Bitmuster 11111111111111111111111111111011. In der Zweierkomplementdarstellung entspicht das als Ganzzahl interpretiert dem Wert -5, also alles in Butter.

Du musst bei deinen Überlegungen beachten, dass int-Werte in Java immer 32 Bit lang sind, die ganzen führenden Nullen werden durch den ~-Operator mit invertiert.

heey,
vielen Dank, das hab ich jetzt verstanden… schon irritierend, das überall für den Operator ~ steht, dass es die bits invertiert… -_-

Jetzt muss ich nur noch die führenden 1 dann iwie wegbekommen *murks* aber da wird mir noch was einfallen hoffe ich :)

schon irritierend, das überall für den Operator ~ steht, dass es die bits invertiert… -_-

Tut er doch - aber eben alle Bits und nicht nur ein paar. :)

Jetzt muss ich nur noch die führenden 1 dann iwie wegbekommen *murks* aber da wird mir noch was einfallen hoffe ich :)

Da sind schon paar knackige Aufgaben dabei diesmal..(steht ja sogar "tricky" dort…)
Störende Bits lassen sich sehr leicht wegrechnen. Dazu hier mehr:
http://de.wikipedia.org/wiki/Bitweiser_Operator
Dort werden die Operatoren auch in ihrer praktischen Verwendung erklärt.

Danke, ist ja gut gemeint, aber die Operatoren sollten wir schon vorher ja können ;)
Ich hab bisher keine Lösung dafür gefunden die ersten bits, die noch dooferweise auf 1 sind wegzubekommen.
Man darf ja auch nur ~ und & benutzen… :(

Du hast dir den Link nicht gründlich genug druchgelesen, dort steht genau die Lösung deines Problems.
Das hat schon seinen Sinn, wenn ich das poste ;-)

Wieviele Bits willst Du denn haben? Wenn Du z.B. nur an den untersten 8 Bits von x interessiert bist, sagst Du einfach (x & 0xff).

Fred spricht genau mein Problem an :D
Also ich weiß natürlich, wie ich bits extrahiere. Das ist nicht allzuschwer!
Das Problem ist, ich weiß ja beim Programmieren nicht wieviele bits ich haben will.
Das ergibt sich ja aus den Parametern. Theoretisch könnten es ja alle sein, aber wenns nicht alle sein sollen…

Also ich hab jetzt ne Lösungsidee, aber noch nicht so richtig den Umsetzungsplan:
Die Methode bekommt 2 Parameter int a und int b:

Ich bestimme das höchste bit mit 1 versehen von a und das höchste bit mit eins versehen von b.
da die ja auf jedenfall null werden, weiß ich bis wohin ich die bits haben will. eben bis zu dem höchsten mit 1 versehenen bit von a und b!
Bin ich da auf dem richtigen Weg? :|

Das Problem ist, ich weiß ja beim Programmieren nicht wieviele bits ich haben will.

Poste doch mal den genauen Aufgabentext.

Ich bestimme das höchste bit mit 1 versehen von a und das höchste bit mit eins versehen von b.

Falls Du das wirklich brauchst (was ich mir nicht vorstellen kann), schau Dir mal Integer.numberOfLeadingZeros an.

http://tams-www.informatik.uni-hamburg.de/lectures/2009ws/vorlesung/rs/uebungen/aufgabenblatt-04.pdf

Wobei ich jetzt nicht sehe, zu welcher Aufgabe das Gestammel von unserem Anonymie passt.

Alle Eingabeparameter und Rückgabewerte sind jeweils Integerwerte (32-bit).

Na also, da steht's doch. Immer alle 32 Bits behandeln, nicht irgendwo abschneiden.

Fred spricht genau mein Problem an :D

Er schreibt genau das, was u.a. auch im Link stand. Ich dachte mir die relevanten Stellen kann man auch selbst finden.

Kleine Ergänzung: bitXor(x,y) gilt ohne die genannte Einschränkung ("nur & und ~ zu benutzen"; ist ein Schreibfehler). Wer eine Lösung nur mit & und ~ findet, kriegt evtl. Bonuspunkte.

bitXor(x,y) gilt ohne die genannte Einschränkung

Sicher? Wäre x ^ y nicht ein bischen zu einfach?

Das wäre es wirklich. Allerdings hat das Hendrich gestern in der Vorlesung gesagt. Und es sind ja auch nur 5 Punkte drauf.
Allerdings war seine Aussage auch etwas geschachtelt und meine Aufmerksamkeit schweifte ab. Wenn ich ihn falsch verstanden haben sollte, korrigiere mich bitte jemand der ebenfalls anwesend war.

Sooo, ich hab jetzt eine Lösung, allerdings bisher noch nicht mit nur & und ~ aber das wäre doch zu einfach mit XOR oder? also naja… das geht ja dank de morgan auch ganz einfach mit & und ~
naja wurst, hier mal meine Lösung und wofür ich das highestOneBit brauchte!
(~a & highestOneBit(a) - 1) & (~b & highestOneBit(b) - 1);

Vielleicht versteht ihr jetzt für was ich das brauchte… ;)

Bedenke, dass es auch für diese Aufgabe nur 5 Punkte gibt. Ich glaub du verkomplizierst die Aufgabe unnötig. NOR soll nur durch & und ~ "ersetzt"/ausgedrückt werden. Die &/~ Bestandteile von NOR lassen sich so hervorheben: N(~)OR(~&). D.h. hier kommt eigentlich nur De Morgan ins Spiel.
http://de.wikipedia.org/wiki/De_Morgansche_Gesetze (Da steht sogar die Lösung..)

Das Problem mit Bit-zerschneidern/ver"oder"n, konkreten Masken etc. kriegst du hier nicht, da die bitweise Operatoren bei int x, y auf ALLE 32 bit angewendet werden.

Ich frag Hendrich morgen nochmal wegen XOR…

(~a & highestOneBit(a) - 1) & (~b & highestOneBit(b) - 1);

Warum willst Du unbedingt Bits abschneiden? Auf dem Aufgabenzettel steht doch klipp und klar, dass Du auf allen 32 Bits arbeiten sollst.

Ok, er überlässt es jetzt doch uns bei XOR. Die einfache Lösung gibt evtl. auch Punkte (allerdings je nach Anzahl der Leute die es so lösen - ist alles etwas unklar…).

Hi,

Lösungen für 4.4 a) und b) sind ja noch eher die einfachen Sachen, wenn man das Prinzip verstanden hat, c) getByte habe ich auch hinbekommen (glaube ich XD).
Jetzt hänge ich allerdings schon Ewigkeiten daran d) bitCount(x) und e) abs(x) - Absolutwert, zu lösen und komme einfach auf keine Idee, wie sich das ohne IF, WHILE, oder FOR lösen lässt und die Lösung unter 32 Operationen(bei d)) bleibt.
Google war wenig hilfreich, oder ich hab' die falschen Suchbegriffe gewählt…

Ein kleiner Tipp in die richtige Richtung würde wahrscheinlich schon reichen, weil bei mir hängt gerade das sprichwörtliche Brett vorm Kopf.

'Habe zwar nicht alle Postings gelesen, aber ich glaube abs() lässt sich realisieren, indem man das störende vorzeichenbit ignoriert, dh überschreibt/wegwirft.
Bitshiften (schieben) wäre hierbei ein stichwort, was man sich mal angucken kann.
Oder natürlich alternativ mit Operationen wie OR oder AND mit einer sinnvollen Zeichenkette

Grundsätzlich kann man Schleifen auch allgemein durch Rekursion umgehen.. aber das ist sicher nicht Sinn der Aufgabe ;)

'Habe zwar nicht alle Postings gelesen, aber ich glaube abs() lässt sich realisieren, indem man das störende vorzeichenbit ignoriert, dh überschreibt/wegwirft.

Bei einer sign-and-magnitude-Darstellung würde das gehen, Java nutzt aber das 2er-Komplement.

Grundsätzlich kann man Schleifen auch allgemein durch Rekursion umgehen.. aber das ist sicher nicht Sinn der Aufgabe ;)

Rekursion braucht aber meistens eine Abbruchbedingung - und für die braucht man ein if, ein switch oder einen der short-circuit-Operatoren (&& und ||).

abs(x) - Absolutwert

Wenn der Wert negativ ist, musst Du alle Bits umdrehen und einen addieren. Wenn der Wert positiv ist, musst Du keine Bits umdrehen und nichts addieren. Hilft Dir das weiter?

Leider nicht wirklich. Soweit bin ich selber schon, das Problem ist, dass ich dazu wieder mit if abfragen müsste, ob der eingegebene Wert negativ oder positiv ist.
In der Aufgabe heißt es allerdings:

Der Absolutwert (Betrag) von x. Keine If-Abfragen, nur logische und Shift-Operationen verwenden.

Mit if könnte die Lösung z.B. wie folgt aussehen:
if (x < 0) // d.h. wenn oberstes Bit gesetzt     return (x ^ 0xffffffff) + 1 else // d.h. wenn oberstes Bit gelöscht     return (x ^ 0) + 0 Etwas anders formuliert:
if (x < 0) // d.h. wenn oberstes Bit 1     return (x ^ (-1)) - (-1) else // d.h. wenn oberstes Bit 0     return (x ^ 0) - 0 Siehst Du die Gemeinsamkeiten und Unterschiede in Zeile 2 und 4? Kannst Du das if jetzt eliminieren? Mehr Tipps kann ich nicht mehr geben, ohne die Lösung hinzuschreiben.

*kopf trifft mit einem lauten Krachen auf die Tastatur* Diese Aufgaben machen mich fertig XD
Ich seh' schon nur noch logische Operatoren, so dass ich gar nicht auf die Idee gekommen bin mir das mal mit den if-Anweisungen aufzuschreiben.

Vielen Dank so wird einiges klarer :)

Gna… da war meine Lösung ja viel zu kompliziert.

Abgabe bis 16/11/2009 12:00

Na dann kann ich meine Lösung ja mal posten :)
public static int abs(int x) {     int sign = x >> 31;     return (x ^ sign) - sign; } Für die bitCount-Aufgabe kann man sich ja einfach mal Integer.bitCount ansehen :)
public static int bitCount(int i) {     i = i - ((i >>> 1) & 0x55555555);     i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);     i = (i + (i >>> 4)) & 0x0f0f0f0f;     i = i + (i >>> 8);     i = i + (i >>> 16);     return i & 0x3f; } Es wäre übrigens schön, wenn mit Tabs zurechtkommen würde...

Na dann kann ich meine Lösung ja mal posten :)

Ich hätt nochpublic static int abs(int x) {     return (~(x >> 31) & x) | ((x >> 31) & (~x + 1)); } anzubieten.

Für die bitCount-Aufgabe kann man sich ja einfach mal Integer.bitCount ansehen :)

Die ist doch total hässlich. Das geht auch viel aufgeräumter:
public static int bitCount(int x) {     x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);     x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);     x = (x & 0x0f0f0f0f) + ((x >>> 4) & 0x0f0f0f0f);     x = (x & 0x00ff00ff) + ((x >>> 8) & 0x00ff00ff);     x = (x & 0x0000ffff) + ((x >>> 16) & 0x0000ffff);     return x; }

Für die bitCount-Aufgabe kann man sich ja einfach mal Integer.bitCount ansehen :)

Die ist doch total hässlich. Das geht auch viel aufgeräumter:
public static int bitCount(int x) {     x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);     x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);     x = (x & 0x0f0f0f0f) + ((x >>> 4) & 0x0f0f0f0f);     x = (x & 0x00ff00ff) + ((x >>> 8) & 0x00ff00ff);     x = (x & 0x0000ffff) + ((x >>> 16) & 0x0000ffff);     return x; }

Das braucht aber 5 Operationen mehr.