representing a sequence of bits in Java?

Discussion in 'Java' started by nooneinparticular314159@yahoo.com, Mar 10, 2008.

  1. Guest

    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!
    , Mar 10, 2008
    #1
    1. Advertising

  2. 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!


    Take a look at java.util.BitSet

    Patricia
    Patricia Shanahan, Mar 10, 2008
    #2
    1. Advertising

  3. Roedy Green Guest

    On Sun, 9 Mar 2008 21:01:55 -0700 (PDT),
    ""
    <> wrote, quoted or indirectly quoted
    someone who said :

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

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Mar 10, 2008
    #3
  4. Ulf Guest

    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
    Ulf, Mar 10, 2008
    #4
  5. Mark Space Guest

    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.)
    Mark Space, Mar 10, 2008
    #5
  6. Lew Guest

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


    Use |, not +.

    > bits = bits | B3 // Set bit 3, the rest of the bits are unchanged


    --
    Lew
    Lew, Mar 11, 2008
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. GGG
    Replies:
    10
    Views:
    12,552
    Donar
    Jul 6, 2006
  2. sarmin kho
    Replies:
    2
    Views:
    825
    A. Lloyd Flanagan
    Jun 15, 2004
  3. Miki Tebeka
    Replies:
    1
    Views:
    443
    Marcin 'Qrczak' Kowalczyk
    Jun 14, 2004
  4. sergey

    "casting" bits to bits?

    sergey, Nov 8, 2006, in forum: VHDL
    Replies:
    1
    Views:
    705
    sergey
    Nov 8, 2006
  5. Hahnemann

    Representing a Sequence of Shorts in Bits

    Hahnemann, Jun 25, 2008, in forum: C Programming
    Replies:
    9
    Views:
    304
Loading...

Share This Page