Creating a bitmask with a large number of options

Question

In my Android app I have a class containing only data (exposed with getters). This class needs to be serialized and sent across to other clients (done naively by iterating over all getters, and storing them in a ByteBuffer).

public class Data 
{
     public int getOption1() { }


     public int getOption2 { }

     // ...

     public int getOptionN { } 
}

Serialize:

public void serialize(Data data) {

    // write getOption1();
    // write getOption2();
    // ...
}

Deserialize:

public void deserialize() {
    // read Option1();
    // read Option2();
    // ...
}

I'd like to be able to define which fields actually get sent (instead of blindly sending all of them), and one potential solution for this would be to define another field which is a bitmask that defines which fields are actually sent.

The receiving side parses the bitmask, and can tell which of the fields should be deserialized from the received message.

The problem is - using an int (32-bit) for bitmask allows for only 32 unique options (by using the "standard" power of 2 enum values).

How can one define a bitmask that can support a larger number of items? is there any other encoding (other than storing each value as a power of 2) ?

The number of actual values may vary (depending on user input) and may be anything from ~ 50 up to 200.

I'd like to encode the different options in the most efficient encoding.

Answer 1

An int provides a bit for each of 32 options. You can use a long to get a bit for each of 64 options. For larger number of options, you can use an int or long array. Take the number of options, divide by 32 (for an int array) or 64 (for a long array) and round up.

A byte array will provide the least waste. Divide the number of options by 8 and round up. You can reserve the first byte to contain the length of the byte array (if you're passing other data as well). Since Byte.MAX_VALUE is 127 (but you can treat the value as the maximum valid index, not the byte count), this limits you to 128 * 8 - 1 = 1023 options (or 2047 options if you are willing to do a little extra work to deal with negative byte count values). The maximum waste will be less than one byte (plus an additional byte of overhead to store the count).

If each option can be independently there or not there, you cannot do much better. If options can be grouped such that all options in a group are always either all present or all absent, then some additional compression may be possible.