libcore/luni/src/main/java/java/util/BitSet.java

   1 /*
   2  *  Licensed to the Apache Software Foundation (ASF) under one or more
   3  *  contributor license agreements.  See the NOTICE file distributed with
   4  *  this work for additional information regarding copyright ownership.
   5  *  The ASF licenses this file to You under the Apache License, Version 2.0
   6  *  (the "License"); you may not use this file except in compliance with
   7  *  the License.  You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  *  Unless required by applicable law or agreed to in writing, software
  12  *  distributed under the License is distributed on an "AS IS" BASIS,
  13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  *  See the License for the specific language governing permissions and
  15  *  limitations under the License.
  16  */
  17
  18 package java.util;
  19
  20 import java.io.IOException;
  21 import java.io.ObjectInputStream;
  22 import java.io.Serializable;
  23
  24 /**
  25  * The {@code BitSet} class implements a bit field. Each element in a
  26  * {@code BitSet} can be on(1) or off(0). A {@code BitSet} is created with a
  27  * given size and grows if this size is exceeded. Growth is always rounded to a
  28  * 64 bit boundary.
  29  */
  30 public class BitSet implements Serializable, Cloneable {
  31     private static final long serialVersionUID = 7997698588986878753L;
  32
  33     private static final int OFFSET = 6;
  34
  35     private static final int ELM_SIZE = 1 << OFFSET;
  36
  37     private static final int RIGHT_BITS = ELM_SIZE - 1;
  38
  39     private static final long[] TWO_N_ARRAY = new long[] { 0x1L, 0x2L, 0x4L,
  40             0x8L, 0x10L, 0x20L, 0x40L, 0x80L, 0x100L, 0x200L, 0x400L, 0x800L,
  41             0x1000L, 0x2000L, 0x4000L, 0x8000L, 0x10000L, 0x20000L, 0x40000L,
  42             0x80000L, 0x100000L, 0x200000L, 0x400000L, 0x800000L, 0x1000000L,
  43             0x2000000L, 0x4000000L, 0x8000000L, 0x10000000L, 0x20000000L,
  44             0x40000000L, 0x80000000L, 0x100000000L, 0x200000000L, 0x400000000L,
  45             0x800000000L, 0x1000000000L, 0x2000000000L, 0x4000000000L,
  46             0x8000000000L, 0x10000000000L, 0x20000000000L, 0x40000000000L,
  47             0x80000000000L, 0x100000000000L, 0x200000000000L, 0x400000000000L,
  48             0x800000000000L, 0x1000000000000L, 0x2000000000000L,
  49             0x4000000000000L, 0x8000000000000L, 0x10000000000000L,
  50             0x20000000000000L, 0x40000000000000L, 0x80000000000000L,
  51             0x100000000000000L, 0x200000000000000L, 0x400000000000000L,
  52             0x800000000000000L, 0x1000000000000000L, 0x2000000000000000L,
  53             0x4000000000000000L, 0x8000000000000000L };
  54
  55     private long[] bits;
  56
  57     private transient boolean needClear;
  58
  59     private transient int actualArrayLength;
  60
  61     private transient boolean isLengthActual;
  62
  63     /**
  64      * Create a new {@code BitSet} with size equal to 64 bits.
  65      *
  66      * @see #clear(int)
  67      * @see #set(int)
  68      * @see #clear()
  69      * @see #clear(int, int)
  70      * @see #set(int, boolean)
  71      * @see #set(int, int)
  72      * @see #set(int, int, boolean)
  73      */
  74     public BitSet() {
  75         bits = new long[1];
  76         actualArrayLength = 0;
  77         isLengthActual = true;
  78     }
  79
  80     /**
  81      * Create a new {@code BitSet} with size equal to nbits. If nbits is not a
  82      * multiple of 64, then create a {@code BitSet} with size nbits rounded to
  83      * the next closest multiple of 64.
  84      *
  85      * @param nbits
  86      *            the size of the bit set.
  87      * @throws NegativeArraySizeException
  88      *             if {@code nbits} is negative.
  89      * @see #clear(int)
  90      * @see #set(int)
  91      * @see #clear()
  92      * @see #clear(int, int)
  93      * @see #set(int, boolean)
  94      * @see #set(int, int)
  95      * @see #set(int, int, boolean)
  96      */
  97     public BitSet(int nbits) {
  98         if (nbits < 0) {
  99             throw new NegativeArraySizeException();
 100         }
 101         bits = new long[(nbits >> OFFSET) + ((nbits & RIGHT_BITS) > 0 ? 1 : 0)];
 102         actualArrayLength = 0;
 103         isLengthActual = true;
 104     }
 105
 106     /**
 107      * Private constructor called from get(int, int) method
 108      *
 109      * @param bits
 110      *            the size of the bit set
 111      */
 112     private BitSet(long[] bits, boolean needClear, int actualArrayLength, boolean isLengthActual) {
 113         this.bits = bits;
 114         this.needClear = needClear;
 115         this.actualArrayLength = actualArrayLength;
 116         this.isLengthActual = isLengthActual;
 117     }
 118
 119     /**
 120      * Creates a copy of this {@code BitSet}.
 121      *
 122      * @return a copy of this {@code BitSet}.
 123      */
 124     @Override
 125     public Object clone() {
 126         try {
 127             BitSet clone = (BitSet) super.clone();
 128             clone.bits = bits.clone();
 129             return clone;
 130         } catch (CloneNotSupportedException e) {
 131             throw new AssertionError(e); // android-changed
 132         }
 133     }
 134
 135     /**
 136      * Compares the argument to this {@code BitSet} and returns whether they are
 137      * equal. The object must be an instance of {@code BitSet} with the same
 138      * bits set.
 139      *
 140      * @param obj
 141      *            the {@code BitSet} object to compare.
 142      * @return a {@code boolean} indicating whether or not this {@code BitSet} and
 143      *         {@code obj} are equal.
 144      * @see #hashCode
 145      */
 146     @Override
 147     public boolean equals(Object obj) {
 148         if (this == obj) {
 149             return true;
 150         }
 151         if (obj instanceof BitSet) {
 152             long[] bsBits = ((BitSet) obj).bits;
 153             int length1 = this.actualArrayLength, length2 = ((BitSet) obj).actualArrayLength;
 154             if (this.isLengthActual && ((BitSet) obj).isLengthActual
 155                     && length1 != length2) {
 156                 return false;
 157             }
 158             // If one of the BitSets is larger than the other, check to see if
 159             // any of its extra bits are set. If so return false.
 160             if (length1 <= length2) {
 161                 for (int i = 0; i < length1; i++) {
 162                     if (bits[i] != bsBits[i]) {
 163                         return false;
 164                     }
 165                 }
 166                 for (int i = length1; i < length2; i++) {
 167                     if (bsBits[i] != 0) {
 168                         return false;
 169                     }
 170                 }
 171             } else {
 172                 for (int i = 0; i < length2; i++) {
 173                     if (bits[i] != bsBits[i]) {
 174                         return false;
 175                     }
 176                 }
 177                 for (int i = length2; i < length1; i++) {
 178                     if (bits[i] != 0) {
 179                         return false;
 180                     }
 181                 }
 182             }
 183             return true;
 184         }
 185         return false;
 186     }
 187
 188     /**
 189      * Increase the size of the internal array to accommodate {@code len} bits.
 190      * The new array max index will be a multiple of 64.
 191      *
 192      * @param len
 193      *            the index the new array needs to be able to access.
 194      */
 195     private final void growLength(int len) {
 196         long[] tempBits = new long[Math.max(len, bits.length * 2)];
 197         System.arraycopy(bits, 0, tempBits, 0, this.actualArrayLength);
 198         bits = tempBits;
 199     }
 200
 201     /**
 202      * Computes the hash code for this {@code BitSet}. If two {@code BitSet}s are equal
 203      * the have to return the same result for {@code hashCode()}.
 204      *
 205      * @return the {@code int} representing the hash code for this bit
 206      *         set.
 207      * @see #equals
 208      * @see java.util.Hashtable
 209      */
 210     @Override
 211     public int hashCode() {
 212         long x = 1234;
 213         for (int i = 0, length = actualArrayLength; i < length; i++) {
 214             x ^= bits[i] * (i + 1);
 215         }
 216         return (int) ((x >> 32) ^ x);
 217     }
 218
 219     /**
 220      * Retrieves the bit at index {@code index}. Grows the {@code BitSet} if
 221      * {@code index > size}.
 222      *
 223      * @param index
 224      *            the index of the bit to be retrieved.
 225      * @return {@code true} if the bit at {@code index} is set,
 226      *         {@code false} otherwise.
 227      * @throws IndexOutOfBoundsException
 228      *             if {@code index} is negative.
 229      * @see #clear(int)
 230      * @see #set(int)
 231      * @see #clear()
 232      * @see #clear(int, int)
 233      * @see #set(int, boolean)
 234      * @see #set(int, int)
 235      * @see #set(int, int, boolean)
 236      */
 237     public boolean get(int index) {
 238         checkIndex(index);
 239         int arrayPos = index >> OFFSET;
 240         if (arrayPos < actualArrayLength) {
 241             return (bits[arrayPos] & TWO_N_ARRAY[index & RIGHT_BITS]) != 0;
 242         }
 243         return false;
 244     }
 245
 246     private void checkIndex(int index) {
 247         if (index < 0) {
 248             throw new IndexOutOfBoundsException("index < 0");
 249         }
 250     }
 251
 252     private void checkRange(int fromIndex, int toIndex) {
 253         if (fromIndex < 0 || toIndex < 0 || toIndex < fromIndex) {
 254             throw new IndexOutOfBoundsException("fromIndex=" + fromIndex + " toIndex=" + toIndex);
 255         }
 256     }
 257
 258     /**
 259      * Retrieves the bits starting from {@code fromIndex} to {@code toIndex} and returns
 260      * back a new bitset made of these bits. Grows the {@code BitSet} if {@code toIndex &gt; size}.
 261      *
 262      * @param fromIndex
 263      *            inclusive beginning position.
 264      * @param toIndex
 265      *            exclusive ending position.
 266      * @return new bitset of the range specified.
 267      * @throws IndexOutOfBoundsException
 268      *             if {@code fromIndex} or {@code toIndex} is negative, or if
 269      *             {@code toIndex} is smaller than {@code fromIndex}.
 270      * @see #get(int)
 271      */
 272     public BitSet get(int fromIndex, int toIndex) {
 273         checkRange(fromIndex, toIndex);
 274
 275         int last = actualArrayLength << OFFSET;
 276         if (fromIndex >= last || fromIndex == toIndex) {
 277             return new BitSet(0);
 278         }
 279         if (toIndex > last) {
 280             toIndex = last;
 281         }
 282
 283         int idx1 = fromIndex >> OFFSET;
 284         int idx2 = (toIndex - 1) >> OFFSET;
 285         long factor1 = (~0L) << (fromIndex & RIGHT_BITS);
 286         long factor2 = (~0L) >>> (ELM_SIZE - (toIndex & RIGHT_BITS));
 287
 288         if (idx1 == idx2) {
 289             long result = (bits[idx1] & (factor1 & factor2)) >>> (fromIndex % ELM_SIZE);
 290             if (result == 0) {
 291                 return new BitSet(0);
 292             }
 293             return new BitSet(new long[] { result }, needClear, 1, true);
 294         }
 295         long[] newbits = new long[idx2 - idx1 + 1];
 296         // first fill in the first and last indexes in the new bitset
 297         newbits[0] = bits[idx1] & factor1;
 298         newbits[newbits.length - 1] = bits[idx2] & factor2;
 299
 300         // fill in the in between elements of the new bitset
 301         for (int i = 1; i < idx2 - idx1; i++) {
 302             newbits[i] = bits[idx1 + i];
 303         }
 304
 305         // shift all the elements in the new bitset to the right by fromIndex % ELM_SIZE
 306         int numBitsToShift = fromIndex & RIGHT_BITS;
 307         int actualLen = newbits.length;
 308         if (numBitsToShift != 0) {
 309             for (int i = 0; i < newbits.length; i++) {
 310                 // shift the current element to the right regardless of
 311                 // sign
 312                 newbits[i] = newbits[i] >>> (numBitsToShift);
 313
 314                 // apply the last x bits of newbits[i+1] to the current
 315                 // element
 316                 if (i != newbits.length - 1) {
 317                     newbits[i] |= newbits[i + 1] << (ELM_SIZE - (numBitsToShift));
 318                 }
 319                 if (newbits[i] != 0) {
 320                     actualLen = i + 1;
 321                 }
 322             }
 323         }
 324         return new BitSet(newbits, needClear, actualLen,
 325                 newbits[actualLen - 1] != 0);
 326     }
 327
 328     /**
 329      * Sets the bit at index {@code index} to 1. Grows the {@code BitSet} if
 330      * {@code index > size}.
 331      *
 332      * @param index
 333      *            the index of the bit to set.
 334      * @throws IndexOutOfBoundsException
 335      *             if {@code index} is negative.
 336      * @see #clear(int)
 337      * @see #clear()
 338      * @see #clear(int, int)
 339      */
 340     public void set(int index) {
 341         checkIndex(index);
 342         int len = (index >> OFFSET) + 1;
 343         if (len > bits.length) {
 344             growLength(len);
 345         }
 346         bits[len - 1] |= TWO_N_ARRAY[index & RIGHT_BITS];
 347         if (len > actualArrayLength) {
 348             actualArrayLength = len;
 349             isLengthActual = true;
 350         }
 351         needClear();
 352     }
 353
 354     /**
 355      * Sets the bit at index {@code index} to {@code val}. Grows the
 356      * {@code BitSet} if {@code index > size}.
 357      *
 358      * @param index
 359      *            the index of the bit to set.
 360      * @param val
 361      *            value to set the bit.
 362      * @throws IndexOutOfBoundsException
 363      *             if {@code index} is negative.
 364      * @see #set(int)
 365      */
 366     public void set(int index, boolean val) {
 367         if (val) {
 368             set(index);
 369         } else {
 370             clear(index);
 371         }
 372     }
 373
 374     /**
 375      * Sets the bits starting from {@code fromIndex} to {@code toIndex}. Grows the
 376      * {@code BitSet} if {@code toIndex > size}.
 377      *
 378      * @param fromIndex
 379      *            inclusive beginning position.
 380      * @param toIndex
 381      *            exclusive ending position.
 382      * @throws IndexOutOfBoundsException
 383      *             if {@code fromIndex} or {@code toIndex} is negative, or if
 384      *             {@code toIndex} is smaller than {@code fromIndex}.
 385      * @see #set(int)
 386      */
 387     public void set(int fromIndex, int toIndex) {
 388         checkRange(fromIndex, toIndex);
 389
 390         if (fromIndex == toIndex) {
 391             return;
 392         }
 393         int len2 = ((toIndex - 1) >> OFFSET) + 1;
 394         if (len2 > bits.length) {
 395             growLength(len2);
 396         }
 397
 398         int idx1 = fromIndex >> OFFSET;
 399         int idx2 = (toIndex - 1) >> OFFSET;
 400         long factor1 = (~0L) << (fromIndex & RIGHT_BITS);
 401         long factor2 = (~0L) >>> (ELM_SIZE - (toIndex & RIGHT_BITS));
 402
 403         if (idx1 == idx2) {
 404             bits[idx1] |= (factor1 & factor2);
 405         } else {
 406             bits[idx1] |= factor1;
 407             bits[idx2] |= factor2;
 408             for (int i = idx1 + 1; i < idx2; i++) {
 409                 bits[i] |= (~0L);
 410             }
 411         }
 412         if (idx2 + 1 > actualArrayLength) {
 413             actualArrayLength = idx2 + 1;
 414             isLengthActual = true;
 415         }
 416         needClear();
 417     }
 418
 419     private void needClear() {
 420         this.needClear = true;
 421     }
 422
 423     /**
 424      * Sets the bits starting from {@code fromIndex} to {@code toIndex} to the given
 425      * {@code val}. Grows the {@code BitSet} if {@code toIndex > size}.
 426      *
 427      * @param fromIndex
 428      *            inclusive beginning position.
 429      * @param toIndex
 430      *            exclusive ending position.
 431      * @param val
 432      *            value to set these bits.
 433      * @throws IndexOutOfBoundsException
 434      *             if {@code fromIndex} or {@code toIndex} is negative, or if
 435      *             {@code toIndex} is smaller than {@code fromIndex}.
 436      * @see #set(int,int)
 437      */
 438     public void set(int fromIndex, int toIndex, boolean val) {
 439         if (val) {
 440             set(fromIndex, toIndex);
 441         } else {
 442             clear(fromIndex, toIndex);
 443         }
 444     }
 445
 446     /**
 447      * Clears all the bits in this {@code BitSet}.
 448      *
 449      * @see #clear(int)
 450      * @see #clear(int, int)
 451      */
 452     public void clear() {
 453         if (needClear) {
 454             for (int i = 0; i < bits.length; i++) {
 455                 bits[i] = 0L;
 456             }
 457             actualArrayLength = 0;
 458             isLengthActual = true;
 459             needClear = false;
 460         }
 461     }
 462
 463     /**
 464      * Clears the bit at index {@code index}. Grows the {@code BitSet} if
 465      * {@code index > size}.
 466      *
 467      * @param index
 468      *            the index of the bit to clear.
 469      * @throws IndexOutOfBoundsException
 470      *             if {@code index} is negative.
 471      * @see #clear(int, int)
 472      */
 473     public void clear(int index) {
 474         checkIndex(index);
 475         if (!needClear) {
 476             return;
 477         }
 478         int arrayPos = index >> OFFSET;
 479         if (arrayPos < actualArrayLength) {
 480             bits[arrayPos] &= ~(TWO_N_ARRAY[index & RIGHT_BITS]);
 481             if (bits[actualArrayLength - 1] == 0) {
 482                 isLengthActual = false;
 483             }
 484         }
 485     }
 486
 487     /**
 488      * Clears the bits starting from {@code fromIndex} to {@code toIndex}. Grows the
 489      * {@code BitSet} if {@code toIndex > size}.
 490      *
 491      * @param fromIndex
 492      *            inclusive beginning position.
 493      * @param toIndex
 494      *            exclusive ending position.
 495      * @throws IndexOutOfBoundsException
 496      *             if {@code fromIndex} or {@code toIndex} is negative, or if
 497      *             {@code toIndex} is smaller than {@code fromIndex}.
 498      * @see #clear(int)
 499      */
 500     public void clear(int fromIndex, int toIndex) {
 501         checkRange(fromIndex, toIndex);
 502
 503         if (!needClear) {
 504             return;
 505         }
 506         int last = (actualArrayLength << OFFSET);
 507         if (fromIndex >= last || fromIndex == toIndex) {
 508             return;
 509         }
 510         if (toIndex > last) {
 511             toIndex = last;
 512         }
 513
 514         int idx1 = fromIndex >> OFFSET;
 515         int idx2 = (toIndex - 1) >> OFFSET;
 516         long factor1 = (~0L) << (fromIndex & RIGHT_BITS);
 517         long factor2 = (~0L) >>> (ELM_SIZE - (toIndex & RIGHT_BITS));
 518
 519         if (idx1 == idx2) {
 520             bits[idx1] &= ~(factor1 & factor2);
 521         } else {
 522             bits[idx1] &= ~factor1;
 523             bits[idx2] &= ~factor2;
 524             for (int i = idx1 + 1; i < idx2; i++) {
 525                 bits[i] = 0L;
 526             }
 527         }
 528         if ((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0)) {
 529             isLengthActual = false;
 530         }
 531     }
 532
 533     /**
 534      * Flips the bit at index {@code index}. Grows the {@code BitSet} if
 535      * {@code index > size}.
 536      *
 537      * @param index
 538      *            the index of the bit to flip.
 539      * @throws IndexOutOfBoundsException
 540      *             if {@code index} is negative.
 541      * @see #flip(int, int)
 542      */
 543     public void flip(int index) {
 544         checkIndex(index);
 545         int len = (index >> OFFSET) + 1;
 546         if (len > bits.length) {
 547             growLength(len);
 548         }
 549         bits[len - 1] ^= TWO_N_ARRAY[index & RIGHT_BITS];
 550         if (len > actualArrayLength) {
 551             actualArrayLength = len;
 552         }
 553         isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
 554         needClear();
 555     }
 556
 557     /**
 558      * Flips the bits starting from {@code fromIndex} to {@code toIndex}. Grows the
 559      * {@code BitSet} if {@code toIndex > size}.
 560      *
 561      * @param fromIndex
 562      *            inclusive beginning position.
 563      * @param toIndex
 564      *            exclusive ending position.
 565      * @throws IndexOutOfBoundsException
 566      *             if {@code fromIndex} or {@code toIndex} is negative, or if
 567      *             {@code toIndex} is smaller than {@code fromIndex}.
 568      * @see #flip(int)
 569      */
 570     public void flip(int fromIndex, int toIndex) {
 571         checkRange(fromIndex, toIndex);
 572
 573         if (fromIndex == toIndex) {
 574             return;
 575         }
 576         int len2 = ((toIndex - 1) >> OFFSET) + 1;
 577         if (len2 > bits.length) {
 578             growLength(len2);
 579         }
 580
 581         int idx1 = fromIndex >> OFFSET;
 582         int idx2 = (toIndex - 1) >> OFFSET;
 583         long factor1 = (~0L) << (fromIndex & RIGHT_BITS);
 584         long factor2 = (~0L) >>> (ELM_SIZE - (toIndex & RIGHT_BITS));
 585
 586         if (idx1 == idx2) {
 587             bits[idx1] ^= (factor1 & factor2);
 588         } else {
 589             bits[idx1] ^= factor1;
 590             bits[idx2] ^= factor2;
 591             for (int i = idx1 + 1; i < idx2; i++) {
 592                 bits[i] ^= (~0L);
 593             }
 594         }
 595         if (len2 > actualArrayLength) {
 596             actualArrayLength = len2;
 597         }
 598         isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
 599         needClear();
 600     }
 601
 602     /**
 603      * Checks if these two {@code BitSet}s have at least one bit set to true in the same
 604      * position.
 605      *
 606      * @param bs
 607      *            {@code BitSet} used to calculate the intersection.
 608      * @return {@code true} if bs intersects with this {@code BitSet},
 609      *         {@code false} otherwise.
 610      */
 611     public boolean intersects(BitSet bs) {
 612         long[] bsBits = bs.bits;
 613         int length1 = actualArrayLength, length2 = bs.actualArrayLength;
 614
 615         if (length1 <= length2) {
 616             for (int i = 0; i < length1; i++) {
 617                 if ((bits[i] & bsBits[i]) != 0L) {
 618                     return true;
 619                 }
 620             }
 621         } else {
 622             for (int i = 0; i < length2; i++) {
 623                 if ((bits[i] & bsBits[i]) != 0L) {
 624                     return true;
 625                 }
 626             }
 627         }
 628
 629         return false;
 630     }
 631
 632     /**
 633      * Performs the logical AND of this {@code BitSet} with another
 634      * {@code BitSet}. The values of this {@code BitSet} are changed accordingly.
 635      *
 636      * @param bs
 637      *            {@code BitSet} to AND with.
 638      * @see #or
 639      * @see #xor
 640      */
 641     public void and(BitSet bs) {
 642         long[] bsBits = bs.bits;
 643         if (!needClear) {
 644             return;
 645         }
 646         int length1 = actualArrayLength, length2 = bs.actualArrayLength;
 647         if (length1 <= length2) {
 648             for (int i = 0; i < length1; i++) {
 649                 bits[i] &= bsBits[i];
 650             }
 651         } else {
 652             for (int i = 0; i < length2; i++) {
 653                 bits[i] &= bsBits[i];
 654             }
 655             for (int i = length2; i < length1; i++) {
 656                 bits[i] = 0;
 657             }
 658             actualArrayLength = length2;
 659         }
 660         isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
 661     }
 662
 663     /**
 664      * Clears all bits in the receiver which are also set in the parameter
 665      * {@code BitSet}. The values of this {@code BitSet} are changed accordingly.
 666      *
 667      * @param bs
 668      *            {@code BitSet} to ANDNOT with.
 669      */
 670     public void andNot(BitSet bs) {
 671         long[] bsBits = bs.bits;
 672         if (!needClear) {
 673             return;
 674         }
 675         int range = actualArrayLength < bs.actualArrayLength ? actualArrayLength
 676                 : bs.actualArrayLength;
 677         for (int i = 0; i < range; i++) {
 678             bits[i] &= ~bsBits[i];
 679         }
 680
 681         if (actualArrayLength < range) {
 682             actualArrayLength = range;
 683         }
 684         isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
 685     }
 686
 687     /**
 688      * Performs the logical OR of this {@code BitSet} with another {@code BitSet}.
 689      * The values of this {@code BitSet} are changed accordingly.
 690      *
 691      * @param bs
 692      *            {@code BitSet} to OR with.
 693      * @see #xor
 694      * @see #and
 695      */
 696     public void or(BitSet bs) {
 697         int bsActualLen = bs.getActualArrayLength();
 698         if (bsActualLen > bits.length) {
 699             long[] tempBits = new long[bsActualLen];
 700             System.arraycopy(bs.bits, 0, tempBits, 0, bs.actualArrayLength);
 701             for (int i = 0; i < actualArrayLength; i++) {
 702                 tempBits[i] |= bits[i];
 703             }
 704             bits = tempBits;
 705             actualArrayLength = bsActualLen;
 706             isLengthActual = true;
 707         } else {
 708             long[] bsBits = bs.bits;
 709             for (int i = 0; i < bsActualLen; i++) {
 710                 bits[i] |= bsBits[i];
 711             }
 712             if (bsActualLen > actualArrayLength) {
 713                 actualArrayLength = bsActualLen;
 714                 isLengthActual = true;
 715             }
 716         }
 717         needClear();
 718     }
 719
 720     /**
 721      * Performs the logical XOR of this {@code BitSet} with another {@code BitSet}.
 722      * The values of this {@code BitSet} are changed accordingly.
 723      *
 724      * @param bs
 725      *            {@code BitSet} to XOR with.
 726      * @see #or
 727      * @see #and
 728      */
 729     public void xor(BitSet bs) {
 730         int bsActualLen = bs.getActualArrayLength();
 731         if (bsActualLen > bits.length) {
 732             long[] tempBits = new long[bsActualLen];
 733             System.arraycopy(bs.bits, 0, tempBits, 0, bs.actualArrayLength);
 734             for (int i = 0; i < actualArrayLength; i++) {
 735                 tempBits[i] ^= bits[i];
 736             }
 737             bits = tempBits;
 738             actualArrayLength = bsActualLen;
 739             isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0));
 740         } else {
 741             long[] bsBits = bs.bits;
 742             for (int i = 0; i < bsActualLen; i++) {
 743                 bits[i] ^= bsBits[i];
 744             }
 745             if (bsActualLen > actualArrayLength) {
 746                 actualArrayLength = bsActualLen;
 747                 isLengthActual = true;
 748             }
 749         }
 750         needClear();
 751     }
 752
 753     /**
 754      * Returns the number of bits this {@code BitSet} has.
 755      *
 756      * @return the number of bits contained in this {@code BitSet}.
 757      * @see #length
 758      */
 759     public int size() {
 760         return bits.length << OFFSET;
 761     }
 762
 763     /**
 764      * Returns the number of bits up to and including the highest bit set.
 765      *
 766      * @return the length of the {@code BitSet}.
 767      */
 768     public int length() {
 769         int idx = actualArrayLength - 1;
 770         while (idx >= 0 && bits[idx] == 0) {
 771             --idx;
 772         }
 773         actualArrayLength = idx + 1;
 774         if (idx == -1) {
 775             return 0;
 776         }
 777         int i = ELM_SIZE - 1;
 778         long val = bits[idx];
 779         while ((val & (TWO_N_ARRAY[i])) == 0 && i > 0) {
 780             i--;
 781         }
 782         return (idx << OFFSET) + i + 1;
 783     }
 784
 785     private final int getActualArrayLength() {
 786         if (isLengthActual) {
 787             return actualArrayLength;
 788         }
 789         int idx = actualArrayLength - 1;
 790         while (idx >= 0 && bits[idx] == 0) {
 791             --idx;
 792         }
 793         actualArrayLength = idx + 1;
 794         isLengthActual = true;
 795         return actualArrayLength;
 796     }
 797
 798     /**
 799      * Returns a string containing a concise, human-readable description of the
 800      * receiver.
 801      *
 802      * @return a comma delimited list of the indices of all bits that are set.
 803      */
 804     @Override
 805     public String toString() {
 806         StringBuilder sb = new StringBuilder(bits.length / 2);
 807         int bitCount = 0;
 808         sb.append('{');
 809         boolean comma = false;
 810         for (int i = 0; i < bits.length; i++) {
 811             if (bits[i] == 0) {
 812                 bitCount += ELM_SIZE;
 813                 continue;
 814             }
 815             for (int j = 0; j < ELM_SIZE; j++) {
 816                 if (((bits[i] & (TWO_N_ARRAY[j])) != 0)) {
 817                     if (comma) {
 818                         sb.append(", ");
 819                     }
 820                     sb.append(bitCount);
 821                     comma = true;
 822                 }
 823                 bitCount++;
 824             }
 825         }
 826         sb.append('}');
 827         return sb.toString();
 828     }
 829
 830     /**
 831      * Returns the position of the first bit that is {@code true} on or after {@code index}.
 832      *
 833      * @param index
 834      *            the starting position (inclusive).
 835      * @return -1 if there is no bits that are set to {@code true} on or after {@code index}.
 836      */
 837     public int nextSetBit(int index) {
 838         checkIndex(index);
 839
 840         if (index >= actualArrayLength << OFFSET) {
 841             return -1;
 842         }
 843
 844         int idx = index >> OFFSET;
 845         // first check in the same bit set element
 846         if (bits[idx] != 0L) {
 847             for (int j = index & RIGHT_BITS; j < ELM_SIZE; j++) {
 848                 if (((bits[idx] & (TWO_N_ARRAY[j])) != 0)) {
 849                     return (idx << OFFSET) + j;
 850                 }
 851             }
 852
 853         }
 854         idx++;
 855         while (idx < actualArrayLength && bits[idx] == 0L) {
 856             idx++;
 857         }
 858         if (idx == actualArrayLength) {
 859             return -1;
 860         }
 861
 862         // we know for sure there is a bit set to true in this element
 863         // since the bitset value is not 0L
 864         for (int j = 0; j < ELM_SIZE; j++) {
 865             if (((bits[idx] & (TWO_N_ARRAY[j])) != 0)) {
 866                 return (idx << OFFSET) + j;
 867             }
 868         }
 869
 870         return -1;
 871     }
 872
 873     /**
 874      * Returns the position of the first bit that is {@code false} on or after {@code index}.
 875      *
 876      * @param index
 877      *            the starting position (inclusive).
 878      * @return the position of the next bit set to {@code false}, even if it is further
 879      *         than this {@code BitSet}'s size.
 880      */
 881     public int nextClearBit(int index) {
 882         checkIndex(index);
 883
 884         int length = actualArrayLength;
 885         int bssize = length << OFFSET;
 886         if (index >= bssize) {
 887             return index;
 888         }
 889
 890         int idx = index >> OFFSET;
 891         // first check in the same bit set element
 892         if (bits[idx] != (~0L)) {
 893             for (int j = index % ELM_SIZE; j < ELM_SIZE; j++) {
 894                 if (((bits[idx] & (TWO_N_ARRAY[j])) == 0)) {
 895                     return idx * ELM_SIZE + j;
 896                 }
 897             }
 898         }
 899         idx++;
 900         while (idx < length && bits[idx] == (~0L)) {
 901             idx++;
 902         }
 903         if (idx == length) {
 904             return bssize;
 905         }
 906
 907         // we know for sure there is a bit set to true in this element
 908         // since the bitset value is not 0L
 909         for (int j = 0; j < ELM_SIZE; j++) {
 910             if (((bits[idx] & (TWO_N_ARRAY[j])) == 0)) {
 911                 return (idx << OFFSET) + j;
 912             }
 913         }
 914
 915         return bssize;
 916     }
 917
 918     /**
 919      * Returns true if all the bits in this {@code BitSet} are set to false.
 920      *
 921      * @return {@code true} if the {@code BitSet} is empty,
 922      *         {@code false} otherwise.
 923      */
 924     public boolean isEmpty() {
 925         if (!needClear) {
 926             return true;
 927         }
 928         int length = bits.length;
 929         for (int idx = 0; idx < length; idx++) {
 930             if (bits[idx] != 0L) {
 931                 return false;
 932             }
 933         }
 934         return true;
 935     }
 936
 937     /**
 938      * Returns the number of bits that are {@code true} in this {@code BitSet}.
 939      *
 940      * @return the number of {@code true} bits in the set.
 941      */
 942     public int cardinality() {
 943         if (!needClear) {
 944             return 0;
 945         }
 946         int count = 0;
 947         int length = bits.length;
 948         // FIXME: need to test performance, if still not satisfied, change it to
 949         // 256-bits table based
 950         for (int idx = 0; idx < length; idx++) {
 951             count += pop(bits[idx] & 0xffffffffL);
 952             count += pop(bits[idx] >>> 32);
 953         }
 954         return count;
 955     }
 956
 957     private final int pop(long x) {
 958         // BEGIN android-note
 959         // delegate to Integer.bitCount(i); consider using native code
 960         // END android-note
 961         x = x - ((x >>> 1) & 0x55555555);
 962         x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
 963         x = (x + (x >>> 4)) & 0x0f0f0f0f;
 964         x = x + (x >>> 8);
 965         x = x + (x >>> 16);
 966         return (int) x & 0x0000003f;
 967     }
 968
 969     private void readObject(ObjectInputStream ois) throws IOException,
 970             ClassNotFoundException {
 971         ois.defaultReadObject();
 972         this.isLengthActual = false;
 973         this.actualArrayLength = bits.length;
 974         this.needClear = this.getActualArrayLength() != 0;
 975     }
 976 }