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
9 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 package org.apache.lucene.util;
20 import java.util.Arrays;
21 import java.io.Serializable;
23 import org.apache.lucene.search.DocIdSet;
24 import org.apache.lucene.search.DocIdSetIterator;
26 /** An "open" BitSet implementation that allows direct access to the array of words
29 * Unlike java.util.bitset, the fact that bits are packed into an array of longs
30 * is part of the interface. This allows efficient implementation of other algorithms
31 * by someone other than the author. It also allows one to efficiently implement
32 * alternate serialization or interchange formats.
34 * <code>OpenBitSet</code> is faster than <code>java.util.BitSet</code> in most operations
35 * and *much* faster at calculating cardinality of sets and results of set operations.
36 * It can also handle sets of larger cardinality (up to 64 * 2**32-1)
38 * The goals of <code>OpenBitSet</code> are the fastest implementation possible, and
39 * maximum code reuse. Extra safety and encapsulation
40 * may always be built on top, but if that's built in, the cost can never be removed (and
41 * hence people re-implement their own version in order to get better performance).
42 * If you want a "safe", totally encapsulated (and slower and limited) BitSet
43 * class, use <code>java.util.BitSet</code>.
45 * <h3>Performance Results</h3>
47 Test system: Pentium 4, Sun Java 1.5_06 -server -Xbatch -Xmx64M
48 <br/>BitSet size = 1,000,000
49 <br/>Results are java.util.BitSet time divided by OpenBitSet time.
52 <th></th> <th>cardinality</th> <th>intersect_count</th> <th>union</th> <th>nextSetBit</th> <th>get</th> <th>iterator</th>
55 <th>50% full</th> <td>3.36</td> <td>3.96</td> <td>1.44</td> <td>1.46</td> <td>1.99</td> <td>1.58</td>
58 <th>1% full</th> <td>3.31</td> <td>3.90</td> <td> </td> <td>1.04</td> <td> </td> <td>0.99</td>
62 Test system: AMD Opteron, 64 bit linux, Sun Java 1.5_06 -server -Xbatch -Xmx64M
63 <br/>BitSet size = 1,000,000
64 <br/>Results are java.util.BitSet time divided by OpenBitSet time.
67 <th></th> <th>cardinality</th> <th>intersect_count</th> <th>union</th> <th>nextSetBit</th> <th>get</th> <th>iterator</th>
70 <th>50% full</th> <td>2.50</td> <td>3.50</td> <td>1.00</td> <td>1.03</td> <td>1.12</td> <td>1.25</td>
73 <th>1% full</th> <td>2.51</td> <td>3.49</td> <td> </td> <td>1.00</td> <td> </td> <td>1.02</td>
78 public class OpenBitSet extends DocIdSet implements Cloneable, Serializable, Bits {
79 protected long[] bits;
80 protected int wlen; // number of words (elements) used in the array
82 // Used only for assert:
85 /** Constructs an OpenBitSet large enough to hold numBits.
89 public OpenBitSet(long numBits) {
90 this.numBits = numBits;
91 bits = new long[bits2words(numBits)];
99 /** Constructs an OpenBitSet from an existing long[].
101 * The first 64 bits are in long[0],
102 * with bit index 0 at the least significant bit, and bit index 63 at the most significant.
104 * the word containing it is long[index/64], and it is at bit number index%64 within that word.
106 * numWords are the number of elements in the array that contain
107 * set bits (non-zero longs).
108 * numWords should be <= bits.length, and
109 * any existing words in the array at position >= numWords should be zero.
112 public OpenBitSet(long[] bits, int numWords) {
114 this.wlen = numWords;
115 this.numBits = wlen * 64;
119 public DocIdSetIterator iterator() {
120 return new OpenBitSetIterator(bits, wlen);
123 /** This DocIdSet implementation is cacheable. */
125 public boolean isCacheable() {
129 /** Returns the current capacity in bits (1 greater than the index of the last bit) */
130 public long capacity() { return bits.length << 6; }
133 * Returns the current capacity of this set. Included for
134 * compatibility. This is *not* equal to {@link #cardinality}
140 public int length() {
141 return bits.length << 6;
144 /** Returns true if there are no set bits */
145 public boolean isEmpty() { return cardinality()==0; }
147 /** Expert: returns the long[] storing the bits */
148 public long[] getBits() { return bits; }
150 /** Expert: sets a new long[] to use as the bit storage */
151 public void setBits(long[] bits) { this.bits = bits; }
153 /** Expert: gets the number of longs in the array that are in use */
154 public int getNumWords() { return wlen; }
156 /** Expert: sets the number of longs in the array that are in use */
157 public void setNumWords(int nWords) { this.wlen=nWords; }
161 /** Returns true or false for the specified bit index. */
162 public boolean get(int index) {
163 int i = index >> 6; // div 64
164 // signed shift will keep a negative index and force an
165 // array-index-out-of-bounds-exception, removing the need for an explicit check.
166 if (i>=bits.length) return false;
168 int bit = index & 0x3f; // mod 64
169 long bitmask = 1L << bit;
170 return (bits[i] & bitmask) != 0;
174 /** Returns true or false for the specified bit index.
175 * The index should be less than the OpenBitSet size
177 public boolean fastGet(int index) {
178 assert index >= 0 && index < numBits;
179 int i = index >> 6; // div 64
180 // signed shift will keep a negative index and force an
181 // array-index-out-of-bounds-exception, removing the need for an explicit check.
182 int bit = index & 0x3f; // mod 64
183 long bitmask = 1L << bit;
184 return (bits[i] & bitmask) != 0;
189 /** Returns true or false for the specified bit index
191 public boolean get(long index) {
192 int i = (int)(index >> 6); // div 64
193 if (i>=bits.length) return false;
194 int bit = (int)index & 0x3f; // mod 64
195 long bitmask = 1L << bit;
196 return (bits[i] & bitmask) != 0;
199 /** Returns true or false for the specified bit index.
200 * The index should be less than the OpenBitSet size.
202 public boolean fastGet(long index) {
203 assert index >= 0 && index < numBits;
204 int i = (int)(index >> 6); // div 64
205 int bit = (int)index & 0x3f; // mod 64
206 long bitmask = 1L << bit;
207 return (bits[i] & bitmask) != 0;
211 // alternate implementation of get()
212 public boolean get1(int index) {
213 int i = index >> 6; // div 64
214 int bit = index & 0x3f; // mod 64
215 return ((bits[i]>>>bit) & 0x01) != 0;
216 // this does a long shift and a bittest (on x86) vs
217 // a long shift, and a long AND, (the test for zero is prob a no-op)
218 // testing on a P4 indicates this is slower than (bits[i] & bitmask) != 0;
223 /** returns 1 if the bit is set, 0 if not.
224 * The index should be less than the OpenBitSet size
226 public int getBit(int index) {
227 assert index >= 0 && index < numBits;
228 int i = index >> 6; // div 64
229 int bit = index & 0x3f; // mod 64
230 return ((int)(bits[i]>>>bit)) & 0x01;
235 public boolean get2(int index) {
236 int word = index >> 6; // div 64
237 int bit = index & 0x0000003f; // mod 64
238 return (bits[word] << bit) < 0; // hmmm, this would work if bit order were reversed
239 // we could right shift and check for parity bit, if it was available to us.
243 /** sets a bit, expanding the set size if necessary */
244 public void set(long index) {
245 int wordNum = expandingWordNum(index);
246 int bit = (int)index & 0x3f;
247 long bitmask = 1L << bit;
248 bits[wordNum] |= bitmask;
252 /** Sets the bit at the specified index.
253 * The index should be less than the OpenBitSet size.
255 public void fastSet(int index) {
256 assert index >= 0 && index < numBits;
257 int wordNum = index >> 6; // div 64
258 int bit = index & 0x3f; // mod 64
259 long bitmask = 1L << bit;
260 bits[wordNum] |= bitmask;
263 /** Sets the bit at the specified index.
264 * The index should be less than the OpenBitSet size.
266 public void fastSet(long index) {
267 assert index >= 0 && index < numBits;
268 int wordNum = (int)(index >> 6);
269 int bit = (int)index & 0x3f;
270 long bitmask = 1L << bit;
271 bits[wordNum] |= bitmask;
274 /** Sets a range of bits, expanding the set size if necessary
276 * @param startIndex lower index
277 * @param endIndex one-past the last bit to set
279 public void set(long startIndex, long endIndex) {
280 if (endIndex <= startIndex) return;
282 int startWord = (int)(startIndex>>6);
284 // since endIndex is one past the end, this is index of the last
285 // word to be changed.
286 int endWord = expandingWordNum(endIndex-1);
288 long startmask = -1L << startIndex;
289 long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
291 if (startWord == endWord) {
292 bits[startWord] |= (startmask & endmask);
296 bits[startWord] |= startmask;
297 Arrays.fill(bits, startWord+1, endWord, -1L);
298 bits[endWord] |= endmask;
303 protected int expandingWordNum(long index) {
304 int wordNum = (int)(index >> 6);
306 ensureCapacity(index+1);
309 assert (numBits = Math.max(numBits, index+1)) >= 0;
315 * The index should be less than the OpenBitSet size.
317 public void fastClear(int index) {
318 assert index >= 0 && index < numBits;
319 int wordNum = index >> 6;
320 int bit = index & 0x03f;
321 long bitmask = 1L << bit;
322 bits[wordNum] &= ~bitmask;
323 // hmmm, it takes one more instruction to clear than it does to set... any
324 // way to work around this? If there were only 63 bits per word, we could
325 // use a right shift of 10111111...111 in binary to position the 0 in the
326 // correct place (using sign extension).
327 // Could also use Long.rotateRight() or rotateLeft() *if* they were converted
328 // by the JVM into a native instruction.
329 // bits[word] &= Long.rotateLeft(0xfffffffe,bit);
333 * The index should be less than the OpenBitSet size.
335 public void fastClear(long index) {
336 assert index >= 0 && index < numBits;
337 int wordNum = (int)(index >> 6); // div 64
338 int bit = (int)index & 0x3f; // mod 64
339 long bitmask = 1L << bit;
340 bits[wordNum] &= ~bitmask;
343 /** clears a bit, allowing access beyond the current set size without changing the size.*/
344 public void clear(long index) {
345 int wordNum = (int)(index >> 6); // div 64
346 if (wordNum>=wlen) return;
347 int bit = (int)index & 0x3f; // mod 64
348 long bitmask = 1L << bit;
349 bits[wordNum] &= ~bitmask;
352 /** Clears a range of bits. Clearing past the end does not change the size of the set.
354 * @param startIndex lower index
355 * @param endIndex one-past the last bit to clear
357 public void clear(int startIndex, int endIndex) {
358 if (endIndex <= startIndex) return;
360 int startWord = (startIndex>>6);
361 if (startWord >= wlen) return;
363 // since endIndex is one past the end, this is index of the last
364 // word to be changed.
365 int endWord = ((endIndex-1)>>6);
367 long startmask = -1L << startIndex;
368 long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
370 // invert masks since we are clearing
371 startmask = ~startmask;
374 if (startWord == endWord) {
375 bits[startWord] &= (startmask | endmask);
379 bits[startWord] &= startmask;
381 int middle = Math.min(wlen, endWord);
382 Arrays.fill(bits, startWord+1, middle, 0L);
383 if (endWord < wlen) {
384 bits[endWord] &= endmask;
389 /** Clears a range of bits. Clearing past the end does not change the size of the set.
391 * @param startIndex lower index
392 * @param endIndex one-past the last bit to clear
394 public void clear(long startIndex, long endIndex) {
395 if (endIndex <= startIndex) return;
397 int startWord = (int)(startIndex>>6);
398 if (startWord >= wlen) return;
400 // since endIndex is one past the end, this is index of the last
401 // word to be changed.
402 int endWord = (int)((endIndex-1)>>6);
404 long startmask = -1L << startIndex;
405 long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
407 // invert masks since we are clearing
408 startmask = ~startmask;
411 if (startWord == endWord) {
412 bits[startWord] &= (startmask | endmask);
416 bits[startWord] &= startmask;
418 int middle = Math.min(wlen, endWord);
419 Arrays.fill(bits, startWord+1, middle, 0L);
420 if (endWord < wlen) {
421 bits[endWord] &= endmask;
427 /** Sets a bit and returns the previous value.
428 * The index should be less than the OpenBitSet size.
430 public boolean getAndSet(int index) {
431 assert index >= 0 && index < numBits;
432 int wordNum = index >> 6; // div 64
433 int bit = index & 0x3f; // mod 64
434 long bitmask = 1L << bit;
435 boolean val = (bits[wordNum] & bitmask) != 0;
436 bits[wordNum] |= bitmask;
440 /** Sets a bit and returns the previous value.
441 * The index should be less than the OpenBitSet size.
443 public boolean getAndSet(long index) {
444 assert index >= 0 && index < numBits;
445 int wordNum = (int)(index >> 6); // div 64
446 int bit = (int)index & 0x3f; // mod 64
447 long bitmask = 1L << bit;
448 boolean val = (bits[wordNum] & bitmask) != 0;
449 bits[wordNum] |= bitmask;
454 * The index should be less than the OpenBitSet size.
456 public void fastFlip(int index) {
457 assert index >= 0 && index < numBits;
458 int wordNum = index >> 6; // div 64
459 int bit = index & 0x3f; // mod 64
460 long bitmask = 1L << bit;
461 bits[wordNum] ^= bitmask;
465 * The index should be less than the OpenBitSet size.
467 public void fastFlip(long index) {
468 assert index >= 0 && index < numBits;
469 int wordNum = (int)(index >> 6); // div 64
470 int bit = (int)index & 0x3f; // mod 64
471 long bitmask = 1L << bit;
472 bits[wordNum] ^= bitmask;
475 /** flips a bit, expanding the set size if necessary */
476 public void flip(long index) {
477 int wordNum = expandingWordNum(index);
478 int bit = (int)index & 0x3f; // mod 64
479 long bitmask = 1L << bit;
480 bits[wordNum] ^= bitmask;
483 /** flips a bit and returns the resulting bit value.
484 * The index should be less than the OpenBitSet size.
486 public boolean flipAndGet(int index) {
487 assert index >= 0 && index < numBits;
488 int wordNum = index >> 6; // div 64
489 int bit = index & 0x3f; // mod 64
490 long bitmask = 1L << bit;
491 bits[wordNum] ^= bitmask;
492 return (bits[wordNum] & bitmask) != 0;
495 /** flips a bit and returns the resulting bit value.
496 * The index should be less than the OpenBitSet size.
498 public boolean flipAndGet(long index) {
499 assert index >= 0 && index < numBits;
500 int wordNum = (int)(index >> 6); // div 64
501 int bit = (int)index & 0x3f; // mod 64
502 long bitmask = 1L << bit;
503 bits[wordNum] ^= bitmask;
504 return (bits[wordNum] & bitmask) != 0;
507 /** Flips a range of bits, expanding the set size if necessary
509 * @param startIndex lower index
510 * @param endIndex one-past the last bit to flip
512 public void flip(long startIndex, long endIndex) {
513 if (endIndex <= startIndex) return;
514 int startWord = (int)(startIndex>>6);
516 // since endIndex is one past the end, this is index of the last
517 // word to be changed.
518 int endWord = expandingWordNum(endIndex-1);
520 /*** Grrr, java shifting wraps around so -1L>>>64 == -1
521 * for that reason, make sure not to use endmask if the bits to flip will
522 * be zero in the last word (redefine endWord to be the last changed...)
523 long startmask = -1L << (startIndex & 0x3f); // example: 11111...111000
524 long endmask = -1L >>> (64-(endIndex & 0x3f)); // example: 00111...111111
527 long startmask = -1L << startIndex;
528 long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
530 if (startWord == endWord) {
531 bits[startWord] ^= (startmask & endmask);
535 bits[startWord] ^= startmask;
537 for (int i=startWord+1; i<endWord; i++) {
541 bits[endWord] ^= endmask;
546 public static int pop(long v0, long v1, long v2, long v3) {
547 // derived from pop_array by setting last four elems to 0.
548 // exchanges one pop() call for 10 elementary operations
549 // saving about 7 instructions... is there a better way?
554 long twosB =(ones&v2)|(u2&v3);
557 long fours=(twosA&twosB);
558 long twos=twosA^twosB;
560 return (pop(fours)<<2)
568 /** @return the number of set bits */
569 public long cardinality() {
570 return BitUtil.pop_array(bits,0,wlen);
573 /** Returns the popcount or cardinality of the intersection of the two sets.
574 * Neither set is modified.
576 public static long intersectionCount(OpenBitSet a, OpenBitSet b) {
577 return BitUtil.pop_intersect(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
580 /** Returns the popcount or cardinality of the union of the two sets.
581 * Neither set is modified.
583 public static long unionCount(OpenBitSet a, OpenBitSet b) {
584 long tot = BitUtil.pop_union(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
585 if (a.wlen < b.wlen) {
586 tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen);
587 } else if (a.wlen > b.wlen) {
588 tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen);
593 /** Returns the popcount or cardinality of "a and not b"
594 * or "intersection(a, not(b))".
595 * Neither set is modified.
597 public static long andNotCount(OpenBitSet a, OpenBitSet b) {
598 long tot = BitUtil.pop_andnot(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
599 if (a.wlen > b.wlen) {
600 tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen);
605 /** Returns the popcount or cardinality of the exclusive-or of the two sets.
606 * Neither set is modified.
608 public static long xorCount(OpenBitSet a, OpenBitSet b) {
609 long tot = BitUtil.pop_xor(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
610 if (a.wlen < b.wlen) {
611 tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen);
612 } else if (a.wlen > b.wlen) {
613 tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen);
619 /** Returns the index of the first set bit starting at the index specified.
620 * -1 is returned if there are no more set bits.
622 public int nextSetBit(int index) {
624 if (i>=wlen) return -1;
625 int subIndex = index & 0x3f; // index within the word
626 long word = bits[i] >> subIndex; // skip all the bits to the right of index
629 return (i<<6) + subIndex + BitUtil.ntz(word);
634 if (word!=0) return (i<<6) + BitUtil.ntz(word);
640 /** Returns the index of the first set bit starting at the index specified.
641 * -1 is returned if there are no more set bits.
643 public long nextSetBit(long index) {
644 int i = (int)(index>>>6);
645 if (i>=wlen) return -1;
646 int subIndex = (int)index & 0x3f; // index within the word
647 long word = bits[i] >>> subIndex; // skip all the bits to the right of index
650 return (((long)i)<<6) + (subIndex + BitUtil.ntz(word));
655 if (word!=0) return (((long)i)<<6) + BitUtil.ntz(word);
662 /** Returns the index of the first set bit starting downwards at
663 * the index specified.
664 * -1 is returned if there are no more set bits.
666 public int prevSetBit(int index) {
672 if (i < 0) return -1;
673 subIndex = 63; // last possible bit
676 if (i < 0) return -1;
677 subIndex = index & 0x3f; // index within the word
678 word = (bits[i] << (63-subIndex)); // skip all the bits to the left of index
682 return (i << 6) + subIndex - Long.numberOfLeadingZeros(word); // See LUCENE-3197
688 return (i << 6) + 63 - Long.numberOfLeadingZeros(word);
695 /** Returns the index of the first set bit starting downwards at
696 * the index specified.
697 * -1 is returned if there are no more set bits.
699 public long prevSetBit(long index) {
700 int i = (int) (index >> 6);
705 if (i < 0) return -1;
706 subIndex = 63; // last possible bit
709 if (i < 0) return -1;
710 subIndex = (int)index & 0x3f; // index within the word
711 word = (bits[i] << (63-subIndex)); // skip all the bits to the left of index
715 return (((long)i)<<6) + subIndex - Long.numberOfLeadingZeros(word); // See LUCENE-3197
721 return (((long)i)<<6) + 63 - Long.numberOfLeadingZeros(word);
729 public Object clone() {
731 OpenBitSet obs = (OpenBitSet)super.clone();
732 obs.bits = obs.bits.clone(); // hopefully an array clone is as fast(er) than arraycopy
734 } catch (CloneNotSupportedException e) {
735 throw new RuntimeException(e);
739 /** this = this AND other */
740 public void intersect(OpenBitSet other) {
741 int newLen= Math.min(this.wlen,other.wlen);
742 long[] thisArr = this.bits;
743 long[] otherArr = other.bits;
744 // testing against zero can be more efficient
747 thisArr[pos] &= otherArr[pos];
749 if (this.wlen > newLen) {
750 // fill zeros from the new shorter length to the old length
751 Arrays.fill(bits,newLen,this.wlen,0);
756 /** this = this OR other */
757 public void union(OpenBitSet other) {
758 int newLen = Math.max(wlen,other.wlen);
759 ensureCapacityWords(newLen);
760 assert (numBits = Math.max(other.numBits, numBits)) >= 0;
762 long[] thisArr = this.bits;
763 long[] otherArr = other.bits;
764 int pos=Math.min(wlen,other.wlen);
766 thisArr[pos] |= otherArr[pos];
768 if (this.wlen < newLen) {
769 System.arraycopy(otherArr, this.wlen, thisArr, this.wlen, newLen-this.wlen);
775 /** Remove all elements set in other. this = this AND_NOT other */
776 public void remove(OpenBitSet other) {
777 int idx = Math.min(wlen,other.wlen);
778 long[] thisArr = this.bits;
779 long[] otherArr = other.bits;
781 thisArr[idx] &= ~otherArr[idx];
785 /** this = this XOR other */
786 public void xor(OpenBitSet other) {
787 int newLen = Math.max(wlen,other.wlen);
788 ensureCapacityWords(newLen);
789 assert (numBits = Math.max(other.numBits, numBits)) >= 0;
791 long[] thisArr = this.bits;
792 long[] otherArr = other.bits;
793 int pos=Math.min(wlen,other.wlen);
795 thisArr[pos] ^= otherArr[pos];
797 if (this.wlen < newLen) {
798 System.arraycopy(otherArr, this.wlen, thisArr, this.wlen, newLen-this.wlen);
804 // some BitSet compatability methods
806 //** see {@link intersect} */
807 public void and(OpenBitSet other) {
811 //** see {@link union} */
812 public void or(OpenBitSet other) {
816 //** see {@link andNot} */
817 public void andNot(OpenBitSet other) {
821 /** returns true if the sets have any elements in common */
822 public boolean intersects(OpenBitSet other) {
823 int pos = Math.min(this.wlen, other.wlen);
824 long[] thisArr = this.bits;
825 long[] otherArr = other.bits;
827 if ((thisArr[pos] & otherArr[pos])!=0) return true;
834 /** Expand the long[] with the size given as a number of words (64 bit longs).
835 * getNumWords() is unchanged by this call.
837 public void ensureCapacityWords(int numWords) {
838 if (bits.length < numWords) {
839 bits = ArrayUtil.grow(bits, numWords);
843 /** Ensure that the long[] is big enough to hold numBits, expanding it if necessary.
844 * getNumWords() is unchanged by this call.
846 public void ensureCapacity(long numBits) {
847 ensureCapacityWords(bits2words(numBits));
850 /** Lowers numWords, the number of words in use,
851 * by checking for trailing zero words.
853 public void trimTrailingZeros() {
855 while (idx>=0 && bits[idx]==0) idx--;
859 /** returns the number of 64 bit words it would take to hold numBits */
860 public static int bits2words(long numBits) {
861 return (int)(((numBits-1)>>>6)+1);
865 /** returns true if both sets have the same bits set */
867 public boolean equals(Object o) {
868 if (this == o) return true;
869 if (!(o instanceof OpenBitSet)) return false;
871 OpenBitSet b = (OpenBitSet)o;
872 // make a the larger set.
873 if (b.wlen > this.wlen) {
879 // check for any set bits out of the range of b
880 for (int i=a.wlen-1; i>=b.wlen; i--) {
881 if (a.bits[i]!=0) return false;
884 for (int i=b.wlen-1; i>=0; i--) {
885 if (a.bits[i] != b.bits[i]) return false;
893 public int hashCode() {
894 // Start with a zero hash and use a mix that results in zero if the input is zero.
895 // This effectively truncates trailing zeros without an explicit check.
897 for (int i = bits.length; --i>=0;) {
899 h = (h << 1) | (h >>> 63); // rotate left
901 // fold leftmost bits into right and add a constant to prevent
902 // empty sets from returning 0, which is too common.
903 return (int)((h>>32) ^ h) + 0x98761234;