Re: representing a sequence of bits in Java?
nooneinparticular314159@yahoo.com wrote:
I want to represent a long sequence of bits indicating whether a long
sequence of things are true. ie. Something like,
1010011101010101010, means the first item is true, the second is
false, etc. I could use a hashmap, and say the key for the hashmap is
the same as the bit number in the bitmap I suppose that I could also
use an array, and fill it with 1s and 0s. But I'd really like to be
able to do this efficiently, to rapidly find elements containing a 0
(along with which element number they are), and to eliminate elements
with a 1 from future consideration. Any idea what the best object to
do this is?
Thanks!
BitSet looks like just the thing. HashMap seems overkill. How are you
looking for the bits? If it's always an index, then arrays (and
presumably BitSet) automatically provide a "perfect hash" for you.
You could roll your own, but I think BitSet would do the same thing as this:
class MyBitSet {
private ArrayList<Integer> bits = new ArrayList<Integer>();
public boolean getBit( int i ) {
int intBits = bits.get( i / 32 );
return !(intBits & (1<<(i%32)) = 0)
}
}
// Note: seriously not syntax checked.
And similarly for set... but BitSet might also provide a custom
implementation that is more efficient than ArrayList and Integer (raw
ints, for example.)
(Note: I just peeked at the implementation of BitSet. I does indeed
appear to use plain arrays of longs. This should be much more efficient
than trying to use a HashMap.)