| Shalec |
[Java - Bitshifting] Kardinalität einer Menge
Hallo,
meine Aufgabe ist es ( ohne vorher je einen quellcode aus Java gesehen zu haben ) in java ein Programm zu schreiben ( ohne die Befehle aus der Vorlesung zu kennen ) einen code zu vollenden.
dabei werden folgende operationen definiert:
(die Klasse heißt MyBitSet)
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
|
public int setState
MyBitSet(){
setState=0;
}
public MyBitSet(MyBitSet theOtherSet) {
setState = theOtherSet.toInt();
}
public MyBitSet(int m) {
setState = m;
}
public boolean empty(){
boolean isEmpty = true;
if (setState !=0){
isEmpty =false;
}
return isEmpty;
public int card(){
int numElements=0;
>code ist zu entwickeln <;
return numElements;
}
|
|
ich hoffe, dass das so lesbar ist..
das ist eben der code bishin zu der stelle, an der ich nun einen weiteren befehl codieren soll..
nun 2 fragen:
1. ist das bislang so ok? (erstes Übungsblatt ohne Hintergrundwissen)
2. die bitshifting operatorn |, & sowie ^ sind in der übung angegeben, jedoch nicht weiter vertieft (d.h. funktionsweise unbekannt). nun habe ich eine seite gefunden:
Orcale
| Zitat: |
The bitwise & operator performs a bitwise AND operation.
The bitwise ^ operator performs a bitwise exclusive OR operation.
The bitwise | operator performs a bitwise inclusive OR operation. |
damit ist die Funktionsweise von & geklärt worden, aber ich habe keine ahnung, was eine exclusive bzw. inclusive OR operation ist.
Mit BlueJ kann man ja eine Liveprogrammierung ausprobieren.. dadurch habe ich mir gedacht, da wegen 1^2=3 eben die bits vereinigt werden, d.h. ^ steht für eine vereinigung, genauso wie |..
einen unterschied habe ich bei 1^3^4=6 sowie 1|3|4=7 bemerkt.
kann mir jemand diese operationen erklären?
(was eine kardinalität ist, ist mir klar - die Umsetzung in Java nicht so sehr..ich denke, man nimmt die Menge und verschiebt die Elemente innerhalb der Menge so lange, bis keine mehr übrig sind und iteriert gleichermaßen als counter..)
liebe Grüße und vielen Dank. |
| #Shalec |
frage hat sich nun soweit geklärt.. andere frage:
| 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:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
|
class MyBitSet {
public int setState;
/**
* Konstruktor erzeugt eine leere Menge
*/
MyBitSet() {
setState = 0;
}
/**
* Der sogenannte Copy-Konstruktor liest die Attribute
* eines Referenzobjektes desselben Typs und kopiert die Werte auf
* die Attribute des neu erzeugten Objektes
*/
public MyBitSet(MyBitSet theOtherSet) {
setState = theOtherSet.toInt();
}
public MyBitSet(int m) {
setState = m;
}
/**
* Gib true zurueck, falls die Menge leer ist
*/
public boolean empty() {
boolean isEmpty = true;
if (setState!=0) {
isEmpty=false;
}
else {
isEmpty=true;
}
return isEmpty;
}
/**
* Gib die Anzahl der Elemente ("Kardinalitaet") in der Menge zurueck,
* die vom Objekt repraesentiert wird
*/
public int card() {
int numElements = 0;
if (hasElem(0) != true) {
numElements = 0;
}
else {
numElements = 1;
}
for (int i=0; i<32; i++) {
int set2 = setState << (32-i);
if (set2 %2 == 1){
numElements++;
}
}
return numElements;
}
/**
* Gib den Zustand der Menge als Integer zurueck
*/
public int toInt() {
return setState;
}
/**
* Mache das Objekt zur leeren Menge
*/
public void erase() {
setState=0;
}
/**
* Fuege ein Element in die Menge ein
*
* @param elem Nummer des Elements, welches in die Menge einzufuegen ist
* Wenn das Element bereits in der Menge enthalten ist,
* hat die Operation keine Wirkung. Wenn das Element nicht im Wertebereich
* 0..31 liegt, wird dies still ignoriert.
*/
public void insert(int elem) {
setState= setState | elem;
}
/**
* Vereinige die durch das Objekt repr�sentierte Menge
* mit einer zweiten Menge, die als Parameter �bergeben wird.
*
* @param theOtherSet Objektinstanz vom Typ MyBitSet.
* Es wird die Vereinigung aus setState und theOtherSet gebildet.
*/
public void union(MyBitSet theOtherSet) {
setState = setState | theOtherSet.toInt();
}
/**
* Bilde aus dem aktuellen Objekt den Durchschnitt mit der als Parameter
* mit gegebenen zweiten Menge
*/
public void intersection(MyBitSet theOtherSet) {
setState = setState & theOtherSet.toInt();
}
/**
* Bilde aus dem aktuellen Objekt O1 die Mengendifferenz
* O1 \ theOtherSet mit der als Parameter eingegebene Menge
*/
public void setMinus(MyBitSet theOtherSet) {
setState = (setState & ~(theOtherSet.toInt()));
}
public boolean hasElem(int elem) {
boolean haveThisElem = false;
int n = setState & elem;
// if (elem == 0) {
if (n != 0){
haveThisElem = true;
}
empty(b);
return haveThisElem;
}
/**
* Repraesentiere die Menge als String, in der �blichen Notation
*/
public String toString() {
String theSetAsString;
boolean isFirst = true;
theSetAsString = "{ ";
for ( int i = 0; i < 32; i++ ) {
if ( (setState & (1 << i)) != 0 ) {
if ( ! isFirst )
theSetAsString = theSetAsString + ", ";
isFirst = false;
Integer e = new Integer(i);
String theElemAsString = new String(e.toString());
theSetAsString = theSetAsString + theElemAsString;
}
}
theSetAsString = theSetAsString + " }";
return theSetAsString;
}
}
class Uebung1 {
public static void tassert(String aStr, boolean a, MyBitSet b0, MyBitSet b1) {
if ( a ) {
System.out.println("PASS: " + aStr);
}
else {
System.out.println("FAIL: " + aStr);
System.out.println("b0: " + b0.toString());
System.out.println("b1: " + b1.toString());
}
}
/**
* Methode zum Test der eigentlich zu entwickelnden Klasse
*/
public static void main(String[] args) {
MyBitSet b0 = new MyBitSet();
MyBitSet b1 = new MyBitSet();
tassert("b0.empty()",b0.empty(),b0,b1);
tassert("b0.card() == 0",b0.card() == 0,b0,b1);
b0.insert(31);
tassert("b0.elem(31)",b0.hasElem(31),b0,b1);
b1.insert(0);
b1.insert(10);
b1.insert(320);
b1.insert(31);
b1.insert(20);
b1.insert(17);
b1.insert(19);
b1.insert(3);
tassert("b1.card() == 7", b1.card() == 7, b0, b1);
b0.setMinus(b1);
tassert("b0.empty()",b0.empty(),b0,b1);
b0.insert(31);
b0.insert(17);
b0.insert(23);
b0.insert(1);
b0.setMinus(b1);
tassert("!b0.empty()",!b0.empty(),b0,b1);
tassert("b0.toString() equals { 1, 23 }",b0.toString().equals("{ 1, 23 }"),b0,b1);
}
}
|
|
ist kompilierbar, mit java uebung1 folgt eine abfrage, programmcode ist genau dann richtig, wenn PASS, ansonsten FAIL.
dabei ist mir aufgefallen, dass entweder in
insert(),
hasElem(),
oder card(),
ein fehler liegen muss...
kann mir jemand eine korrekturhilfe geben?
DAnke 
|
| Dennis2011 |
Hallo!
1.) Bei der Methode public void insert(int elem) hast Du die Bitverschiebung vergessen!
Du hast durch setState eine Menge repräsentiert und diese willst Du vereinigen mit einer Zahl, die ja ebenfalls durch eine 1 an der entsprechenden Bit-Stelle repräsentiert wird. Also musst Du die 1 so weit verschieben (nach links), daß sie an der Stelle steht, die für die hinzuzufügende Zahl steht und DANN vereinigst Du das mit setState.
Außerdem sollst Du ja vorher noch schauen, ob die hinzuzufügende Zahl kleiner 32 ist. Das musst Du am Anfang mit einer if-Bedingung berücksichtigen.
2.) Bei der Methode public boolean hasElem(int elem) übergibst Du ja als Paramter diejenige Integer-Zahl, von der Du wissen möchtest, ob sie in der durch setState repräsentierten Menge enthalten ist.
Was muss dafür gelten, daß sie das ist? An der elem-ten Bitstelle muss eine 1 stehen. Erstelle also einen Booleschen Ausdruck, der true ist, wenn an der elem-ten Stelle eine 1 steht und setze diesen Booleschen Ausdruck in return ein.
Das ist es dann schon.
(Tipp: Du findest das schon fertig in dem Quellcode, der bereitgestellt wurde und so weit ich mich erinnere wurde das sogar in der Vorlesung besprochen.)
3. Die Methode public int card() kann man so aufbauen:
Nimm eine for-Schleife her und schaue mit der, ob an der i-ten Bitstelle eine 1 oder eine 0 steht. Wenn an der i-ten Stelle eine 1 steht, heißt das ja nix Anderes, als das die dazugehörige Bitstellen-Nummer ein Element der durch setState repräsentierten Menge ist und dann erhöhst Du die zu Beginn auf 0 gesetzte Kardinalität um 1.
Tipp: Auch hier findest Du den wichtigsten Ausdruck, den Du brauchst schon fertig im bereitgestellten Quellcode (ist der gleiche wie bei hasElem()). |
