BitSet


1   /*
2    * @(#)BitSet.java  1.60 04/02/19
3    *
4    * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   package java.util;
9   
10  import java.io.*;
11  
12  /**
13   * This class implements a vector of bits that grows as needed. Each 
14   * component of the bit set has a <code>boolean</code> value. The 
15   * bits of a <code>BitSet</code> are indexed by nonnegative integers. 
16   * Individual indexed bits can be examined, set, or cleared. One 
17   * <code>BitSet</code> may be used to modify the contents of another 
18   * <code>BitSet</code> through logical AND, logical inclusive OR, and 
19   * logical exclusive OR operations.
20   * <p>
21   * By default, all bits in the set initially have the value 
22   * <code>false</code>. 
23   * <p>
24   * Every bit set has a current size, which is the number of bits 
25   * of space currently in use by the bit set. Note that the size is
26   * related to the implementation of a bit set, so it may change with
27   * implementation. The length of a bit set relates to logical length
28   * of a bit set and is defined independently of implementation.
29   * <p>
30   * Unless otherwise noted, passing a null parameter to any of the
31   * methods in a <code>BitSet</code> will result in a
32   * <code>NullPointerException</code>.
33   *
34   * A <code>BitSet</code> is not safe for multithreaded use without
35   * external synchronization.
36   *
37   * @author  Arthur van Hoff
38   * @author  Michael McCloskey
39   * @version 1.60, 02/19/04
40   * @since   JDK1.0
41   */
42  public class BitSet implements Cloneable  , java.io.Serializable   {
43      /*
44       * BitSets are packed into arrays of "units."  Currently a unit is a long,
45       * which consists of 64 bits, requiring 6 address bits.  The choice of unit
46       * is determined purely by performance concerns.
47       */
48      private final static int ADDRESS_BITS_PER_UNIT = 6;
49      private final static int BITS_PER_UNIT = 1 << ADDRESS_BITS_PER_UNIT;
50      private final static int BIT_INDEX_MASK = BITS_PER_UNIT - 1;
51  
52      /* Used to shift left or right for a partial word mask */
53      private static final long WORD_MASK = 0xffffffffffffffffL;
54  
55      /**
56       * The bits in this BitSet.  The ith bit is stored in bits[i/64] at
57       * bit position i % 64 (where bit position 0 refers to the least
58       * significant bit and 63 refers to the most significant bit).
59       * INVARIANT: The words in bits[] above unitsInUse-1 are zero.
60       *
61       * @serial
62       */
63      private long bits[];  // this should be called unit[]
64  
65      /**
66       * The number of units in the logical size of this BitSet.
67       * INVARIANT: unitsInUse is nonnegative.
68       * INVARIANT: bits[unitsInUse-1] is nonzero unless unitsInUse is zero.
69       */
70      private transient int unitsInUse = 0;
71  
72      /* use serialVersionUID from JDK 1.0.2 for interoperability */
73      private static final long serialVersionUID = 7997698588986878753L;
74  
75      /**
76       * Given a bit index return unit index containing it.
77       */
78      private static int unitIndex(int bitIndex) {
79          return bitIndex >> ADDRESS_BITS_PER_UNIT;
80      }
81  
82      /**
83       * Given a bit index, return a unit that masks that bit in its unit.
84       */
85      private static long bit(int bitIndex) {
86          return 1L << (bitIndex & BIT_INDEX_MASK);
87      }
88  
89      /**
90       * Set the field unitsInUse with the logical size in units of the bit
91       * set.  WARNING:This function assumes that the number of units actually
92       * in use is less than or equal to the current value of unitsInUse!
93       */
94      private void recalculateUnitsInUse() {
95          // Traverse the bitset until a used unit is found
96          int i;
97          for (i = unitsInUse-1; i >= 0; i--)
98          if(bits[i] != 0)
99          break;
100 
101         unitsInUse = i+1; // The new logical size
102     }
103 
104     /**
105      * Creates a new bit set. All bits are initially <code>false</code>.
106      */
107     public BitSet() {
108     this(BITS_PER_UNIT);
109     }
110 
111     /**
112      * Creates a bit set whose initial size is large enough to explicitly
113      * represent bits with indices in the range <code>0</code> through
114      * <code>nbits-1</code>. All bits are initially <code>false</code>. 
115      *
116      * @param     nbits   the initial size of the bit set.
117      * @exception NegativeArraySizeException if the specified initial size
118      *               is negative.
119      */
120     public BitSet(int nbits) {
121     // nbits can't be negative; size 0 is OK
122     if (nbits < 0)
123         throw new NegativeArraySizeException  ("nbits < 0: " + nbits);
124 
125     bits = new long[(unitIndex(nbits-1) + 1)];
126     }
127 
128     /**
129      * Ensures that the BitSet can hold enough units.
130      * @param   unitsRequired the minimum acceptable number of units.
131      */
132     private void ensureCapacity(int unitsRequired) {
133     if (bits.length < unitsRequired) {
134         // Allocate larger of doubled size or required size
135         int request = Math.max(2 * bits.length, unitsRequired);
136         long newBits[] = new long[request];
137         System.arraycopy(bits, 0, newBits, 0, unitsInUse);
138         bits = newBits;
139     }
140     }
141 
142     /**
143      * Sets the bit at the specified index to the complement of its
144      * current value.
145      * 
146      * @param   bitIndex the index of the bit to flip.
147      * @exception IndexOutOfBoundsException if the specified index is negative.
148      * @since   1.4
149      */
150     public void flip(int bitIndex) {
151     if (bitIndex < 0)
152         throw new IndexOutOfBoundsException  ("bitIndex < 0: " + bitIndex);
153         
154     int unitIndex = unitIndex(bitIndex);
155         int unitsRequired = unitIndex+1;
156 
157         if (unitsInUse < unitsRequired) {
158             ensureCapacity(unitsRequired);
159             bits[unitIndex] ^= bit(bitIndex);
160             unitsInUse = unitsRequired;
161         } else {
162             bits[unitIndex] ^= bit(bitIndex);
163             if (bits[unitsInUse-1] == 0)
164                 recalculateUnitsInUse();
165         }
166     }
167 
168     /**
169      * Sets each bit from the specified fromIndex(inclusive) to the
170      * specified toIndex(exclusive) to the complement of its current
171      * value.
172      * 
173      * @param     fromIndex   index of the first bit to flip.
174      * @param     toIndex index after the last bit to flip.
175      * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
176      *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
177      *            larger than <tt>toIndex</tt>.
178      * @since   1.4
179      */
180     public void flip(int fromIndex, int toIndex) {
181     if (fromIndex < 0)
182         throw new IndexOutOfBoundsException  ("fromIndex < 0: " + fromIndex);
183         if (toIndex < 0)
184         throw new IndexOutOfBoundsException  ("toIndex < 0: " + toIndex);
185         if (fromIndex > toIndex)
186         throw new IndexOutOfBoundsException  ("fromIndex: " + fromIndex +
187                                                 " > toIndex: " + toIndex);
188         
189         // Increase capacity if necessary
190         int endUnitIndex = unitIndex(toIndex);
191         int unitsRequired = endUnitIndex + 1;
192 
193         if (unitsInUse < unitsRequired) {
194             ensureCapacity(unitsRequired);
195             unitsInUse = unitsRequired;
196         }
197 
198         int startUnitIndex = unitIndex(fromIndex);
199         long bitMask = 0;
200         if (startUnitIndex == endUnitIndex) {
201             // Case 1: One word
202             bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
203                       (1L << (fromIndex & BIT_INDEX_MASK));
204             bits[startUnitIndex] ^= bitMask;
205             if (bits[unitsInUse-1] == 0)
206                 recalculateUnitsInUse();
207             return;
208         }
209         
210         // Case 2: Multiple words
211         // Handle first word
212         bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
213         bits[startUnitIndex] ^= bitMask;
214 
215         // Handle intermediate words, if any
216         if (endUnitIndex - startUnitIndex > 1) {
217             for(int i=startUnitIndex+1; i<endUnitIndex; i++)
218                 bits[i] ^= WORD_MASK;
219         }
220 
221         // Handle last word
222         bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
223         bits[endUnitIndex] ^= bitMask;
224 
225         // Check to see if we reduced size
226         if (bits[unitsInUse-1] == 0)
227             recalculateUnitsInUse();
228     }
229 
230     /**
231      * Returns a long that has all bits that are less significant
232      * than the specified index set to 1. All other bits are 0.
233      */
234     private static long bitsRightOf(int x) {
235         return (x==0 ? 0 : WORD_MASK >>> (64-x));
236     }
237 
238     /**
239      * Returns a long that has all the bits that are more significant
240      * than or equal to the specified index set to 1. All other bits are 0.
241      */
242     private static long bitsLeftOf(int x) {
243         return WORD_MASK << x;
244     }
245 
246     /**
247      * Sets the bit at the specified index to <code>true</code>.
248      *
249      * @param     bitIndex   a bit index.
250      * @exception IndexOutOfBoundsException if the specified index is negative.
251      * @since     JDK1.0
252      */
253     public void set(int bitIndex) {
254     if (bitIndex < 0)
255         throw new IndexOutOfBoundsException  ("bitIndex < 0: " + bitIndex);
256 
257         int unitIndex = unitIndex(bitIndex);
258         int unitsRequired = unitIndex + 1;
259 
260         if (unitsInUse < unitsRequired) {
261             ensureCapacity(unitsRequired);
262             bits[unitIndex] |= bit(bitIndex);
263             unitsInUse = unitsRequired;
264         } else {
265             bits[unitIndex] |= bit(bitIndex);
266         }            
267     }
268 
269     /**
270      * Sets the bit at the specified index to the specified value.
271      *
272      * @param     bitIndex   a bit index.
273      * @param     value a boolean value to set.
274      * @exception IndexOutOfBoundsException if the specified index is negative.
275      * @since     1.4
276      */
277     public void set(int bitIndex, boolean value) {
278         if (value)
279             set(bitIndex);
280         else
281             clear(bitIndex);
282     }
283 
284     /**
285      * Sets the bits from the specified fromIndex(inclusive) to the
286      * specified toIndex(exclusive) to <code>true</code>.
287      *
288      * @param     fromIndex   index of the first bit to be set.
289      * @param     toIndex index after the last bit to be set.
290      * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
291      *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
292      *            larger than <tt>toIndex</tt>.
293      * @since     1.4
294      */
295     public void set(int fromIndex, int toIndex) {
296     if (fromIndex < 0)
297         throw new IndexOutOfBoundsException  ("fromIndex < 0: " + fromIndex);
298         if (toIndex < 0)
299         throw new IndexOutOfBoundsException  ("toIndex < 0: " + toIndex);
300         if (fromIndex > toIndex)
301         throw new IndexOutOfBoundsException  ("fromIndex: " + fromIndex +
302                                                 " > toIndex: " + toIndex);
303 
304         // Increase capacity if necessary
305         int endUnitIndex = unitIndex(toIndex);
306         int unitsRequired = endUnitIndex + 1;
307 
308         if (unitsInUse < unitsRequired) {
309             ensureCapacity(unitsRequired);
310             unitsInUse = unitsRequired;
311         }
312 
313         int startUnitIndex = unitIndex(fromIndex);
314         long bitMask = 0;
315         if (startUnitIndex == endUnitIndex) {
316             // Case 1: One word
317             bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
318                       (1L << (fromIndex & BIT_INDEX_MASK));
319             bits[startUnitIndex] |= bitMask;
320             return;
321         }
322         
323         // Case 2: Multiple words
324         // Handle first word
325         bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
326         bits[startUnitIndex] |= bitMask;
327 
328         // Handle intermediate words, if any
329         if (endUnitIndex - startUnitIndex > 1) {
330             for(int i=startUnitIndex+1; i<endUnitIndex; i++)
331                 bits[i] |= WORD_MASK;
332         }
333 
334         // Handle last word
335         bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
336         bits[endUnitIndex] |= bitMask;
337     }
338 
339     /**
340      * Sets the bits from the specified fromIndex(inclusive) to the
341      * specified toIndex(exclusive) to the specified value.
342      *
343      * @param     fromIndex   index of the first bit to be set.
344      * @param     toIndex index after the last bit to be set
345      * @param     value value to set the selected bits to
346      * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
347      *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
348      *            larger than <tt>toIndex</tt>.
349      * @since     1.4
350      */
351     public void set(int fromIndex, int toIndex, boolean value) {
352     if (value)
353             set(fromIndex, toIndex);
354         else
355             clear(fromIndex, toIndex);
356     }
357 
358     /**
359      * Sets the bit specified by the index to <code>false</code>.
360      *
361      * @param     bitIndex   the index of the bit to be cleared.
362      * @exception IndexOutOfBoundsException if the specified index is negative.
363      * @since     JDK1.0
364      */
365     public void clear(int bitIndex) {
366     if (bitIndex < 0)
367         throw new IndexOutOfBoundsException  ("bitIndex < 0: " + bitIndex);
368 
369     int unitIndex = unitIndex(bitIndex);
370     if (unitIndex >= unitsInUse)
371         return;
372 
373     bits[unitIndex] &= ~bit(bitIndex);
374         if (bits[unitsInUse-1] == 0)
375             recalculateUnitsInUse();
376     }
377 
378     /**
379      * Sets the bits from the specified fromIndex(inclusive) to the
380      * specified toIndex(exclusive) to <code>false</code>.
381      *
382      * @param     fromIndex   index of the first bit to be cleared.
383      * @param     toIndex index after the last bit to be cleared. 
384      * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
385      *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
386      *            larger than <tt>toIndex</tt>.
387      * @since     1.4
388      */
389     public void clear(int fromIndex, int toIndex) {
390     if (fromIndex < 0)
391         throw new IndexOutOfBoundsException  ("fromIndex < 0: " + fromIndex);
392         if (toIndex < 0)
393         throw new IndexOutOfBoundsException  ("toIndex < 0: " + toIndex);
394         if (fromIndex > toIndex)
395         throw new IndexOutOfBoundsException  ("fromIndex: " + fromIndex +
396                                                 " > toIndex: " + toIndex);
397 
398         int startUnitIndex = unitIndex(fromIndex);
399     if (startUnitIndex >= unitsInUse)
400         return;
401         int endUnitIndex = unitIndex(toIndex);
402 
403         long bitMask = 0;
404         if (startUnitIndex == endUnitIndex) {
405             // Case 1: One word
406             bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
407                       (1L << (fromIndex & BIT_INDEX_MASK));
408             bits[startUnitIndex] &= ~bitMask;
409             if (bits[unitsInUse-1] == 0)
410                 recalculateUnitsInUse();
411             return;
412         }
413 
414         // Case 2: Multiple words
415         // Handle first word
416         bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
417         bits[startUnitIndex] &= ~bitMask;
418 
419         // Handle intermediate words, if any
420         if (endUnitIndex - startUnitIndex > 1) {
421             for(int i=startUnitIndex+1; i<endUnitIndex; i++) {
422                 if (i < unitsInUse)
423                     bits[i] = 0;
424             }
425         }
426 
427         // Handle last word
428         if (endUnitIndex < unitsInUse) {
429             bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
430             bits[endUnitIndex] &= ~bitMask;
431         }
432 
433         if (bits[unitsInUse-1] == 0)
434             recalculateUnitsInUse();
435     }
436 
437     /**
438      * Sets all of the bits in this BitSet to <code>false</code>.
439      *
440      * @since   1.4
441      */
442     public void clear() {
443         while (unitsInUse > 0)
444             bits[--unitsInUse] = 0;
445     }
446 
447     /**
448      * Returns the value of the bit with the specified index. The value 
449      * is <code>true</code> if the bit with the index <code>bitIndex</code> 
450      * is currently set in this <code>BitSet</code>; otherwise, the result 
451      * is <code>false</code>.
452      *
453      * @param     bitIndex   the bit index.
454      * @return    the value of the bit with the specified index.
455      * @exception IndexOutOfBoundsException if the specified index is negative.
456      */
457     public boolean get(int bitIndex) {
458     if (bitIndex < 0)
459         throw new IndexOutOfBoundsException  ("bitIndex < 0: " + bitIndex);
460 
461     boolean result = false;
462     int unitIndex = unitIndex(bitIndex);
463     if (unitIndex < unitsInUse)
464         result = ((bits[unitIndex] & bit(bitIndex)) != 0);
465 
466     return result;
467     }
468 
469     /**
470      * Returns a new <tt>BitSet</tt> composed of bits from this <tt>BitSet</tt>
471      * from <tt>fromIndex</tt>(inclusive) to <tt>toIndex</tt>(exclusive).
472      *
473      * @param     fromIndex   index of the first bit to include.
474      * @param     toIndex     index after the last bit to include.
475      * @return    a new <tt>BitSet</tt> from a range of this <tt>BitSet</tt>.
476      * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
477      *            or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
478      *            larger than <tt>toIndex</tt>.
479      * @since   1.4
480      */
481     public BitSet   get(int fromIndex, int toIndex) {
482     if (fromIndex < 0)
483         throw new IndexOutOfBoundsException  ("fromIndex < 0: " + fromIndex);
484         if (toIndex < 0)
485         throw new IndexOutOfBoundsException  ("toIndex < 0: " + toIndex);
486         if (fromIndex > toIndex)
487         throw new IndexOutOfBoundsException  ("fromIndex: " + fromIndex +
488                                                 " > toIndex: " + toIndex);
489 
490         // If no set bits in range return empty bitset
491         if (length() <= fromIndex || fromIndex == toIndex)
492             return new BitSet  (0);
493 
494         // An optimization
495         if (length() < toIndex)
496             toIndex = length();
497 
498         BitSet   result = new BitSet  (toIndex - fromIndex);
499         int startBitIndex = fromIndex & BIT_INDEX_MASK;
500         int endBitIndex = toIndex & BIT_INDEX_MASK;
501         int targetWords = (toIndex - fromIndex + 63)/64;
502         int sourceWords = unitIndex(toIndex) - unitIndex(fromIndex) + 1;
503         int inverseIndex = 64 - startBitIndex;
504         int targetIndex = 0;
505         int sourceIndex = unitIndex(fromIndex);
506 
507         // Process all words but the last word
508         while (targetIndex < targetWords - 1)
509             result.bits[targetIndex++] =
510                (bits[sourceIndex++] >>> startBitIndex) |
511                ((inverseIndex==64) ? 0 : bits[sourceIndex] << inverseIndex);
512 
513         // Process the last word
514         result.bits[targetIndex] = (sourceWords == targetWords ?
515            (bits[sourceIndex] & bitsRightOf(endBitIndex)) >>> startBitIndex :
516            (bits[sourceIndex++] >>> startBitIndex) | ((inverseIndex==64) ? 0 :
517            (getBits(sourceIndex) & bitsRightOf(endBitIndex)) << inverseIndex));
518 
519         // Set unitsInUse correctly
520         result.unitsInUse = targetWords;
521         result.recalculateUnitsInUse();
522     return result;
523     }
524 
525     /**
526      * Returns the unit of this bitset at index j as if this bitset had an
527      * infinite amount of storage.
528      */
529     private long getBits(int j) {
530         return (j < unitsInUse) ? bits[j] : 0;
531     }
532 
533     /**
534      * Returns the index of the first bit that is set to <code>true</code>
535      * that occurs on or after the specified starting index. If no such
536      * bit exists then -1 is returned.
537      *
538      * To iterate over the <code>true</code> bits in a <code>BitSet</code>,
539      * use the following loop:
540      *
541      * for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) {
542      *     // operate on index i here
543      * }
544      * 
545      * @param   fromIndex the index to start checking from (inclusive).
546      * @return  the index of the next set bit.
547      * @throws  IndexOutOfBoundsException if the specified index is negative.
548      * @since   1.4
549      */
550     public int nextSetBit(int fromIndex) {
551     if (fromIndex < 0)
552         throw new IndexOutOfBoundsException  ("fromIndex < 0: " + fromIndex);
553         int u = unitIndex(fromIndex);
554         if (u >= unitsInUse)
555             return -1;
556         int testIndex = (fromIndex & BIT_INDEX_MASK);
557         long unit = bits[u] >> testIndex;
558 
559         if (unit == 0)
560             testIndex = 0;
561 
562         while((unit==0) && (u < unitsInUse-1))
563             unit = bits[++u];
564 
565         if (unit == 0)
566             return -1;
567 
568         testIndex  += trailingZeroCnt(unit);
569         return ((u * BITS_PER_UNIT) + testIndex);
570     }
571 
572     private static int trailingZeroCnt(long val) {
573         // Loop unrolled for performance
574         int byteVal = (int)val & 0xff;
575         if (byteVal != 0)
576             return trailingZeroTable[byteVal];
577 
578         byteVal = (int)(val >>> 8) & 0xff;
579         if (byteVal != 0)
580             return trailingZeroTable[byteVal] + 8;
581 
582         byteVal = (int)(val >>> 16) & 0xff;
583         if (byteVal != 0)
584             return trailingZeroTable[byteVal] + 16;
585 
586         byteVal = (int)(val >>> 24) & 0xff;
587         if (byteVal != 0)
588             return trailingZeroTable[byteVal] + 24;
589 
590         byteVal = (int)(val >>> 32) & 0xff;
591         if (byteVal != 0)
592             return trailingZeroTable[byteVal] + 32;
593 
594         byteVal = (int)(val >>> 40) & 0xff;
595         if (byteVal != 0)
596             return trailingZeroTable[byteVal] + 40;
597 
598         byteVal = (int)(val >>> 48) & 0xff;
599         if (byteVal != 0)
600             return trailingZeroTable[byteVal] + 48;
601 
602         byteVal = (int)(val >>> 56) & 0xff;
603         return trailingZeroTable[byteVal] + 56;
604     }
605 
606     /*
607      * trailingZeroTable[i] is the number of trailing zero bits in the binary
608      * representation of i.
609      */
610     private final static byte trailingZeroTable[] = {
611       -25, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
612     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
613     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
614     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
615     6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
616     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
617     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
618     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
619     7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
620     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
621     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
622     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
623     6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
624     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
625     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
626     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
627 
628     /**
629      * Returns the index of the first bit that is set to <code>false</code>
630      * that occurs on or after the specified starting index.
631      * 
632      * @param   fromIndex the index to start checking from (inclusive).
633      * @return  the index of the next clear bit.
634      * @throws  IndexOutOfBoundsException if the specified index is negative.
635      * @since   1.4
636      */
637     public int nextClearBit(int fromIndex) {
638     if (fromIndex < 0)
639         throw new IndexOutOfBoundsException  ("fromIndex < 0: " + fromIndex);
640 
641         int u = unitIndex(fromIndex);
642         if (u >= unitsInUse)
643             return fromIndex;
644         int testIndex = (fromIndex & BIT_INDEX_MASK);
645         long unit = bits[u] >> testIndex;
646 
647         if (unit == (WORD_MASK >> testIndex))
648             testIndex = 0;
649 
650         while((unit==WORD_MASK) && (u < unitsInUse-1))
651             unit = bits[++u];
652 
653         if (unit == WORD_MASK)
654             return length();
655         
656         if (unit == 0)
657             return u * BITS_PER_UNIT + testIndex;
658 
659         testIndex += trailingZeroCnt(~unit);
660         return ((u * BITS_PER_UNIT) + testIndex);
661     }
662 
663     /**
664      * Returns the "logical size" of this <code>BitSet</code>: the index of
665      * the highest set bit in the <code>BitSet</code> plus one. Returns zero
666      * if the <code>BitSet</code> contains no set bits.
667      *
668      * @return  the logical size of this <code>BitSet</code>.
669      * @since   1.2
670      */
671     public int length() {
672         if (unitsInUse == 0)
673             return 0;
674 
675     long highestUnit = bits[unitsInUse - 1];
676     int highPart = (int)(highestUnit >>> 32);
677         return 64 * (unitsInUse - 1) +
678                (highPart == 0 ? bitLen((int)highestUnit)
679                               : 32 + bitLen((int)highPart));
680     }
681 
682     /**
683      * bitLen(val) is the number of bits in val.
684      */
685     private static int bitLen(int w) {
686         // Binary search - decision tree (5 tests, rarely 6)
687         return
688          (w < 1<<15 ?
689           (w < 1<<7 ?
690            (w < 1<<3 ?
691             (w < 1<<1 ? (w < 1<<0 ? (w<0 ? 32 : 0) : 1) : (w < 1<<2 ? 2 : 3)) :
692             (w < 1<<5 ? (w < 1<<4 ? 4 : 5) : (w < 1<<6 ? 6 : 7))) :
693            (w < 1<<11 ?
694             (w < 1<<9 ? (w < 1<<8 ? 8 : 9) : (w < 1<<10 ? 10 : 11)) :
695             (w < 1<<13 ? (w < 1<<12 ? 12 : 13) : (w < 1<<14 ? 14 : 15)))) :
696           (w < 1<<23 ?
697            (w < 1<<19 ?
698             (w < 1<<17 ? (w < 1<<16 ? 16 : 17) : (w < 1<<18 ? 18 : 19)) :
699             (w < 1<<21 ? (w < 1<<20 ? 20 : 21) : (w < 1<<22 ? 22 : 23))) :
700            (w < 1<<27 ?
701             (w < 1<<25 ? (w < 1<<24 ? 24 : 25) : (w < 1<<26 ? 26 : 27)) :
702             (w < 1<<29 ? (w < 1<<28 ? 28 : 29) : (w < 1<<30 ? 30 : 31)))));
703     }
704 
705     /**
706      * Returns true if this <code>BitSet</code> contains no bits that are set
707      * to <code>true</code>.
708      *
709      * @return    boolean indicating whether this <code>BitSet</code> is empty.
710      * @since     1.4
711      */
712     public boolean isEmpty() {
713         return (unitsInUse == 0);
714     }
715 
716     /**
717      * Returns true if the specified <code>BitSet</code> has any bits set to
718      * <code>true</code> that are also set to <code>true</code> in this
719      * <code>BitSet</code>.
720      *
721      * @param   set <code>BitSet</code> to intersect with
722      * @return  boolean indicating whether this <code>BitSet</code> intersects
723      *          the specified <code>BitSet</code>.
724      * @since   1.4
725      */
726     public boolean intersects(BitSet   set) {
727         for(int i = Math.min(unitsInUse, set.unitsInUse)-1; i>=0; i--)
728             if ((bits[i] & set.bits[i]) != 0)
729                 return true;
730         return false;
731     }
732 
733     /**
734      * Returns the number of bits set to <tt>true</tt> in this
735      * <code>BitSet</code>.
736      *
737      * @return  the number of bits set to <tt>true</tt> in this
738      *          <code>BitSet</code>.
739      * @since   1.4
740      */
741     public int cardinality() {
742         int sum = 0;
743         for (int i=0; i<unitsInUse; i++)
744             sum += bitCount(bits[i]);
745         return sum;
746     }
747 
748     /**
749      * Returns the number of bits set in val.
750      * For a derivation of this algorithm, see
751      * "Algorithms and data structures with applications to 
752      *  graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs,
753      *  Prentice Hall, 1993.
754      */
755     private static int bitCount(long val) {
756         val -= (val & 0xaaaaaaaaaaaaaaaaL) >>> 1;
757         val =  (val & 0x3333333333333333L) + ((val >>> 2) & 0x3333333333333333L);
758         val =  (val + (val >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
759         val += val >>> 8;     
760         val += val >>> 16;    
761         return ((int)(val) + (int)(val >>> 32)) & 0xff;
762     }
763 
764     /**
765      * Performs a logical <b>AND</b> of this target bit set with the 
766      * argument bit set. This bit set is modified so that each bit in it 
767      * has the value <code>true</code> if and only if it both initially 
768      * had the value <code>true</code> and the corresponding bit in the 
769      * bit set argument also had the value <code>true</code>. 
770      *
771      * @param   set   a bit set. 
772      */
773     public void and(BitSet   set) {
774     if (this == set)
775         return;
776 
777     // Perform logical AND on bits in common
778     int oldUnitsInUse = unitsInUse;
779     unitsInUse = Math.min(unitsInUse, set.unitsInUse);
780         int i;
781     for(i=0; i<unitsInUse; i++)
782         bits[i] &= set.bits[i];
783 
784     // Clear out units no longer used
785     for( ; i < oldUnitsInUse; i++)
786         bits[i] = 0;
787 
788         // Recalculate units in use if necessary
789         if (unitsInUse > 0 && bits[unitsInUse - 1] == 0)
790             recalculateUnitsInUse();
791     }
792 
793     /**
794      * Performs a logical <b>OR</b> of this bit set with the bit set 
795      * argument. This bit set is modified so that a bit in it has the 
796      * value <code>true</code> if and only if it either already had the 
797      * value <code>true</code> or the corresponding bit in the bit set 
798      * argument has the value <code>true</code>.
799      *
800      * @param   set   a bit set.
801      */
802     public void or(BitSet   set) {
803     if (this == set)
804         return;
805 
806     ensureCapacity(set.unitsInUse);
807 
808     // Perform logical OR on bits in common
809     int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);
810         int i;
811     for(i=0; i<unitsInCommon; i++)
812         bits[i] |= set.bits[i];
813 
814     // Copy any remaining bits
815     for(; i<set.unitsInUse; i++)
816         bits[i] = set.bits[i];
817 
818         if (unitsInUse < set.unitsInUse)
819             unitsInUse = set.unitsInUse;
820     }
821 
822     /**
823      * Performs a logical <b>XOR</b> of this bit set with the bit set 
824      * argument. This bit set is modified so that a bit in it has the 
825      * value <code>true</code> if and only if one of the following 
826      * statements holds: 
827      * <ul>
828      * <li>The bit initially has the value <code>true</code>, and the 
829      *     corresponding bit in the argument has the value <code>false</code>.
830      * <li>The bit initially has the value <code>false</code>, and the 
831      *     corresponding bit in the argument has the value <code>true</code>. 
832      * </ul>
833      *
834      * @param   set   a bit set.
835      */
836     public void xor(BitSet   set) {
837         int unitsInCommon;
838 
839         if (unitsInUse >= set.unitsInUse) {
840             unitsInCommon = set.unitsInUse;
841         } else {
842             unitsInCommon = unitsInUse;
843             int newUnitsInUse = set.unitsInUse;
844             ensureCap