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
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
|
<html>
<head>
<title>
Handbuch der Java-Programmierung, 5. Auflage
</title>
</head>
<body>
<a name="startofbody"></a>
<script language="JavaScript" src="hjp4lib.js">
</script>
<script language="JavaScript">
installKbdHandler("97,#startofbody;101,#endofbody;116,cover.html;122,k100003.html;115,search.html;105,index.html;100,JDKDOCS;112,APIDOCS;104,k100090.html;106,k100094.html;107,k100096.html;108,k100097.html");
</script>
<table border=0 cellpadding=0 cellspacing=1 width="100%">
<tr bgcolor="#EEFFCC">
<td width="7%" align=center bgcolor="#DDCC99"><a href="cover.html"> Titel </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100003.html"> Inhalt </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="search.html"> Suchen </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="index.html"> Index </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="../jdkdocs/index.html" onClick="this.href=getDocIndex()"> DOC </a>
<td align="right">Handbuch der Java-Programmierung, 5. Auflage
<tr bgcolor="#EEFFCC">
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100090.html"> << </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100094.html"> < </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100096.html"> > </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100097.html"> >> </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="../jdkdocs/api/index.html" onClick="this.href=getApiIndex()"> API </a>
<td align="right">Kapitel 14 - Collections I
</table>
<hr>
<!-- Section -->
<a name="sectlevel2id014005"></a>
<h2>14.5 Die Klasse BitSet </h2>
<hr>
<ul>
<li><a href="k100095.html#sectlevel2id014005">14.5 Die Klasse BitSet</a>
<ul>
<li><a href="k100095.html#sectlevel3id014005001">14.5.1 Elementweise Operationen</a>
<li><a href="k100095.html#sectlevel3id014005002">14.5.2 Mengenorientierte Operationen</a>
</ul>
</ul>
<hr>
<p>
Die Klasse <a name="ixa100910"><a href="index_b.html#ixb100676"><font color=#000080><tt>BitSet</tt></font></a></a>
dient dazu, <i>Mengen ganzer Zahlen</i> zu repräsentieren. Sie
erlaubt es, Zahlen einzufügen oder zu löschen und zu testen,
ob bestimmte Werte in der Menge enthalten sind. Die Klasse bietet
zudem die Möglichkeit, Teil- und Vereinigungsmengen zu bilden.
<p>
<table border=0 cellspacing=0 cellpadding=0 width=100%>
<tr>
<td width=1 align=left valign=top bgcolor="#0099CC"><img src="trp1_1.gif"></td>
<td><img src="trp1_1.gif" width=1></td>
<td width=1 align=left valign=top bgcolor="#0099CC"><img src="trp1_1.gif"></td>
<td><img src="trp1_1.gif" width=2></td>
<td valign=top width=1000>
<p>
Ein <a href="index_b.html#ixb100676"><font color=#000080><tt>BitSet</tt></font></a>
erlaubt aber auch noch eine andere Interpretation. Sie kann nämlich
auch als eine Menge von Bits, die entweder gesetzt oder nicht gesetzt
sein können, angesehen werden. In diesem Fall entspricht das
Einfügen eines Elements dem Setzen eines Bits, das Entfernen
dem Löschen und die Vereinigungs- und Schnittmengenoperationen
den logischen ODER- bzw. UND-Operationen.</td>
<td><img src="trp1_1.gif" width=2></td>
<td valign=top>
<table border=0 cellspacing=0 cellpadding=1 width=100% bgcolor="#0099CC">
<tr>
<td><font color="#FFFFFF"> Tipp </font></td>
</tr>
</table>
</td>
<td width=1 align=left valign=top bgcolor="#0099CC"><img src="trp1_1.gif"></td>
</tr>
</table>
<p>
Diese Analogie wird insbesondere dann deutlich, wenn man eine Menge
von ganzen Zahlen in der Form repräsentiert, dass in einem booleschen
Array das Element an Position <i>i</i> genau dann auf <a href="index_t.html#ixb100233"><font color=#000080><tt>true</tt></font></a>
gesetzt wird, wenn die Zahl <i>i</i> Element der repräsentierten
Menge ist. Mit <a href="index_b.html#ixb100676"><font color=#000080><tt>BitSet</tt></font></a>
bietet Java nun eine Klasse, die sowohl als Liste von Bits als auch
als Menge von Ganzzahlen angesehen werden kann.
<!-- Section -->
<a name="sectlevel3id014005001"></a>
<h3>14.5.1 Elementweise Operationen </h3>
<p>
Ein neues Objekt der Klasse <a href="index_b.html#ixb100676"><font color=#000080><tt>BitSet</tt></font></a>
kann mit dem parameterlosen Konstruktor angelegt werden. Die dadurch
repräsentierte Menge ist zunächst leer.
<p>
<table border=0 cellspacing=0 cellpadding=0 width=100% bgcolor="#EEFFCC">
<tr>
<td valign=top width=100%>
<font color="#660066">
<pre>
public BitSet()
</pre>
</font>
</td>
<td valign=top>
<a href="../jdkdocs/api/java/util/BitSet.html" onClick="this.href=getApiDoc('java.util.BitSet')"><font color="#660066" size=-1>java.util.BitSet</font></a></td>
</tr>
</table>
<p>
Das Einfügen einer Zahl (bzw. das Setzen eines Bits) erfolgt
mit Hilfe der Methode <a name="ixa100911"><a href="index_s.html#ixb100181"><font color=#000080><tt>set</tt></font></a></a>.
Das Entfernen einer Zahl (bzw. das Löschen eines Bits) erfolgt
mit der Methode <a name="ixa100912"><a href="index_c.html#ixb100710"><font color=#000080><tt>clear</tt></font></a></a>.
Die Abfrage, ob eine Zahl in der Menge enthalten ist (bzw. die Abfrage
des Zustands eines bestimmten Bits), erfolgt mit Hilfe der Methode
<a name="ixa100913"><a href="index_g.html#ixb100699"><font color=#000080><tt>get</tt></font></a></a>:
<p>
<table border=0 cellspacing=0 cellpadding=0 width=100% bgcolor="#EEFFCC">
<tr>
<td valign=top width=100%>
<font color="#660066">
<pre>
public void set(int bit)
public void clear(int bit)
public boolean get(int bit)
</pre>
</font>
</td>
<td valign=top>
<a href="../jdkdocs/api/java/util/BitSet.html" onClick="this.href=getApiDoc('java.util.BitSet')"><font color="#660066" size=-1>java.util.BitSet</font></a></td>
</tr>
</table>
<!-- Section -->
<a name="sectlevel3id014005002"></a>
<h3>14.5.2 Mengenorientierte Operationen </h3>
<p>
Die mengenorientierten Operationen benötigen zwei Mengen als
Argumente, nämlich das aktuelle Objekt und eine weitere Menge,
die als Parameter übergeben wird. Das Ergebnis der Operation
wird dem aktuellen Objekt zugewiesen. Das Bilden der Vereinigungsmenge
(bzw. die bitweise ODER-Operation) erfolgt durch Aufruf der Methode
<a name="ixa100914"><a href="index_o.html#ixb100711"><font color=#000080><tt>or</tt></font></a></a>,
das Bilden der Durchschnittsmenge (bzw. die bitweise UND-Operation)
mit Hilfe von <a name="ixa100915"><a href="index_a.html#ixb100712"><font color=#000080><tt>and</tt></font></a></a>.
Zusätzlich gibt es die Methode <a name="ixa100916"><a href="index_x.html#ixb100713"><font color=#000080><tt>xor</tt></font></a></a>,
die ein bitweises Exklusiv-ODER durchführt. Deren mengentheoretisches
Äquivalent ist die Vereinigung von Schnittmenge und Schnittmenge
der Umkehrmengen.
<p>
<table border=0 cellspacing=0 cellpadding=0 width=100%>
<tr>
<td width=1 align=left valign=top bgcolor="#FF9900"><img src="trp1_1.gif"></td>
<td><img src="trp1_1.gif" width=1></td>
<td width=1 align=left valign=top bgcolor="#FF9900"><img src="trp1_1.gif"></td>
<td><img src="trp1_1.gif" width=2></td>
<td valign=top width=1000>
<p>
Seit dem JDK 1.2 gibt es zusätzlich die Methode <a name="ixa100917"><a href="index_a.html#ixb100714"><font color=#000080><tt>andNot</tt></font></a></a>,
mit der die Bits der Ursprungsmenge gelöscht werden, deren korrespondierendes
Bit in der Argumentmenge gesetzt ist.</td>
<td><img src="trp1_1.gif" width=2></td>
<td valign=top>
<table border=0 cellspacing=0 cellpadding=1 width=100% bgcolor="#FF9900">
<tr>
<td><font color="#FFFFFF"> JDK1.1-6.0 </font></td>
</tr>
</table>
</td>
<td width=1 align=left valign=top bgcolor="#FF9900"><img src="trp1_1.gif"></td>
</tr>
</table>
<p>
<table border=0 cellspacing=0 cellpadding=0 width=100% bgcolor="#EEFFCC">
<tr>
<td valign=top width=100%>
<font color="#660066">
<pre>
public void or(BitSet set)
public void and(BitSet set)
public void xor(BitSet set)
public void andNot(BitSet set)
</pre>
</font>
</td>
<td valign=top>
<a href="../jdkdocs/api/java/util/BitSet.html" onClick="this.href=getApiDoc('java.util.BitSet')"><font color="#660066" size=-1>java.util.BitSet</font></a></td>
</tr>
</table>
<p>
Das folgende Programm verdeutlicht die Anwendung der Klasse <a href="index_b.html#ixb100676"><font color=#000080><tt>BitSet</tt></font></a>
am Beispiel der Konstruktion der Menge der Primzahlen kleiner gleich
20. Dabei werden besagte Primzahlen einfach als Menge <i>X</i> der
natürlichen Zahlen bis 20 angesehen, bei der jedes Element keinen
echten Teiler in <i>X</i> enthält:
<a name="listingid014004"></a>
<p>
<table border=0 cellspacing=0 cellpadding=0 width=100% bgcolor="#DDDDDD">
<tr>
<td valign=top>
<font color="#000055">
<pre>
<font color="#555555">001 </font><font color="#00AA00">/* Listing1404.java */</font>
<font color="#555555">002 </font>
<font color="#555555">003 </font><font color="#0000AA">import</font> java.util.*;
<font color="#555555">004 </font>
<font color="#555555">005 </font><font color="#0000AA">public</font> <font color="#0000AA">class</font> Listing1404
<font color="#555555">006 </font>{
<font color="#555555">007 </font> <font color="#0000AA">private</font> <font color="#0000AA">final</font> <font color="#0000AA">static</font> <font color="#006699">int</font> MAXNUM = 20;
<font color="#555555">008 </font>
<font color="#555555">009 </font> <font color="#0000AA">public</font> <font color="#0000AA">static</font> <font color="#006699">void</font> main(String[] args)
<font color="#555555">010 </font> {
<font color="#555555">011 </font> BitSet b;
<font color="#555555">012 </font> <font color="#006699">boolean</font> ok;
<font color="#555555">013 </font>
<font color="#555555">014 </font> System.out.println(<font color="#0000FF">"Die Primzahlen <= "</font> + MAXNUM + <font color="#0000FF">":"</font>);
<font color="#555555">015 </font> b = <font color="#0000AA">new</font> BitSet();
<font color="#555555">016 </font> <font color="#0000AA">for</font> (<font color="#006699">int</font> i = 2; i <= MAXNUM; ++i) {
<font color="#555555">017 </font> ok = <font color="#006699">true</font>;
<font color="#555555">018 </font> <font color="#0000AA">for</font> (<font color="#006699">int</font> j = 2; j < i; ++j) {
<font color="#555555">019 </font> <font color="#0000AA">if</font> (b.get(j) && i % j == 0) {
<font color="#555555">020 </font> ok = <font color="#006699">false</font>;
<font color="#555555">021 </font> <font color="#0000AA">break</font>;
<font color="#555555">022 </font> }
<font color="#555555">023 </font> }
<font color="#555555">024 </font> <font color="#0000AA">if</font> (ok) {
<font color="#555555">025 </font> b.set(i);
<font color="#555555">026 </font> }
<font color="#555555">027 </font> }
<font color="#555555">028 </font> <font color="#0000AA">for</font> (<font color="#006699">int</font> i = 1; i <= MAXNUM; ++i) {
<font color="#555555">029 </font> <font color="#0000AA">if</font> (b.get(i)) {
<font color="#555555">030 </font> System.out.println(<font color="#0000FF">" "</font> + i);
<font color="#555555">031 </font> }
<font color="#555555">032 </font> }
<font color="#555555">033 </font> }
<font color="#555555">034 </font>}</pre>
</font>
</td>
<td valign=top align=right>
<a href="../examples/Listing1404.java"><font color="#000055" size=-1>Listing1404.java</font></a></td>
</tr>
</table>
<i>
Listing 14.4: Konstruktion von Primzahlen mit der Klasse BitSet</i></p>
<p>
Die Ausgabe des Programms ist:
<font color="#333300">
<pre>
Die Primzahlen <= 20:
2
3
5
7
11
13
17
19
</pre>
</font>
<hr>
<table border=0 cellpadding=0 cellspacing=1 width="100%">
<tr bgcolor="#EEFFCC">
<td width="7%" align=center bgcolor="#DDCC99"><a href="cover.html"> Titel </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100003.html"> Inhalt </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="search.html"> Suchen </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="index.html"> Index </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="../jdkdocs/index.html" onClick="this.href=getDocIndex()"> DOC </a>
<td align="right">Handbuch der Java-Programmierung, 5. Auflage, Addison
Wesley, Version 5.0.1
<tr bgcolor="#EEFFCC">
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100090.html"> << </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100094.html"> < </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100096.html"> > </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="k100097.html"> >> </a>
<td width="7%" align=center bgcolor="#DDCC99"><a href="../jdkdocs/api/index.html" onClick="this.href=getApiIndex()"> API </a>
<td align="right">© 1998, 2007 Guido Krüger & Thomas
Stark, <a href="http://www.javabuch.de">http://www.javabuch.de</a>
</table>
<a name="endofbody"></a>
</body>
</html>
|
