representing a sequence of bits in Java?

[nooneinparticular314159]

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!

 

[Patricia Shanahan]

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!

Take a look at java.util.BitSet

Patricia

 

[Roedy Green]

On Sun, 9 Mar 2008 21:01:55 -0700 (PDT),

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.

see http://mindprod.com/jgloss/bitset.html

 

[Ulf]

If there are <= 32 bits it fits into an int, and I would do like this:

public static int B1 = 1;
public static int B2 = 2;
public static int B3 = 4;
public static int B4 = 8;

public int bits;

bits = B1; // Set bit 1, all others 0
bits = B1 + B2; // Set bit 1 and 4, all others 0
bits = bits | B3 // Set bit 3, the rest of the bits are unchanged
if ((bits & B1) > 0 ) // Is bit 1 set?
if ((bits & (B1 + B4)) > 0 ) // Is bit 1 OR bit 4 set?

Please note that the syntax is not verified, it only shows the
principle.
I think that, since it's mostly low level operations without class
references, it should performe well.

/Ulf

 

[Mark Space]

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.)

 

[Lew]

bits = B1 + B2; // Set bit 1 and 4, all others 0

Use |, not +.