Extract bit sequences of arbitrary length from byte[] array efficiently

Answer 1

Just wondering why can't you use java.util.BitSet;

Basically what you can do, is to read the whole data as byte[], convert it to binary in string format and use string utilities like .substring() to do the work. This will also work bit sequences > 16.

Lets say you have 3 bytes: 1, 2, 3 and you want to extract bit sequence from 5th to 16th bit.

Number Binary

1      00000001
2      00000010
3      00000011

Code example:

public static String getRealBinary(byte[] input){
    StringBuilder sb = new StringBuilder();

    for (byte c : input) {
        for (int n =  128; n > 0; n >>= 1){
            if ((c & n) == 0)
                sb.append('0');
            else sb.append('1');
        }
    }

    return sb.toString();
}
public static void main(String[] args) {
    byte bytes[] = new byte[]{1,2,3};
    String sbytes = getRealBinary(bytes);
    System.out.println(sbytes);
    System.out.println(sbytes.substring(5,16));
}

Output:

000000010000001000000011
00100000010

Speed:

I did a testrun for 1m times and on my computer it took 0.995s, so its reasonably very fast:

Code to repeat the test yourself:

public static void main(String[] args) {
    Random r = new Random();
    byte bytes[] = new byte[4];
    long start, time, total=0;

    for (int i = 0; i < 1000000; i++) {
        r.nextBytes(bytes);
        start = System.currentTimeMillis();
        getRealBinary(bytes).substring(5,16);
        time = System.currentTimeMillis() - start;
        total+=time;
    }
    System.out.println("It took " +total + "ms");
}

Answer 2

If you just want the unsigned bit sequence as an int.

static final int[] lookup = {0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };

/*
 * bytes: byte array, with the bits indexed from 0 (MSB) to (bytes.length * 8 - 1) (LSB)
 * offset: index of the MSB of the bit sequence.
 * len: length of bit sequence, must from range [0,16].
 * Not checked for overflow
 */
static int getBitSeqAsInt(byte[] bytes, int offset, int len){

    int byteIndex = offset / 8;
    int bitIndex = offset % 8;
    int val;

    if ((bitIndex + len) > 16) {
        val = ((bytes[byteIndex] << 16 | bytes[byteIndex + 1] << 8 | bytes[byteIndex + 2]) >> (24 - bitIndex - len)) & lookup[len];
    } else if ((offset + len) > 8) {
        val = ((bytes[byteIndex] << 8 | bytes[byteIndex + 1]) >> (16 - bitIndex - len)) & lookup[len];
    } else {
        val = (bytes[byteIndex] >> (8 - offset - len)) & lookup[len];
    }

    return val;
}

If you want it as a String (modification of Margus' answer).

static String getBitSequence(byte[] bytes, int offset, int len){

    int byteIndex = offset / 8;
    int bitIndex = offset % 8;
    int count = 0;
    StringBuilder result = new StringBuilder();        

    outer:
    for(int i = byteIndex; i < bytes.length; ++i) {
        for(int j = (1 << (7 - bitIndex)); j > 0; j >>= 1) {
            if(count == len) {
                break outer;
            }                
            if((bytes[byteIndex] & j) == 0) {
                result.append('0');
            } else {
                result.append('1');
            }
            ++count;
        }
        bitIndex = 0;
    }
    return  result.toString();
}   

Answer 3

Well, depending on how far you want to go down the time vs. memory see-saw, you can allocate a side table of every 32-bits at every 16-bit offset and then do a mask and shift based on the 16-bit offset:

byte[] bytes = new byte[2048];   
int bitGet;   
unsigned int dwords[] = new unsigned int[2046];

public BitArray() {   
    for (int i=0; i<bytes.length; ++i) {   
        bytes[i] = (byte) i;   
    }   

    for (int i= 0; i<dwords.length; ++i) {
        dwords[i]= 
            (bytes[i    ] << 24) | 
            (bytes[i + 1] << 16) | 
            (bytes[i + 2] <<  8) | 
            (bytes[i + 3]);
    }
}   

int getBits(int len)
{
    int offset= bitGet;
    int offset_index= offset>>4;
    int offset_offset= offset & 15;

    return (dwords[offset_index] >> offset_offset) & ((1 << len) - 1);
}

You avoid the branching (at the cost of quadrupling your memory footprint). And is looking up the mask really that much faster than (1 << len) - 1?

Answer 4

You want at most 16 bits, taken from an array of bytes. 16 bits can span at most 3 bytes. Here's a possible solution:

    int GetBits(int bit_index, int bit_length) {
          int byte_offset = bit_index >> 3;
          return ((((((byte_array[byte_offset]<<8)
                    +byte_array[byte_offset+1])<<8)
                    +byte_array[byte_offset+2]))
                   >>(24-(bit_index&7)+bit_length))))
                  &((1<<bit_length)-1);
         }

[Untested]

If you call this a lot you should precompute the 24-bit values for the 3 concatenated bytes, and store those into an int array.

I'll observe that if you are coding this in C on an x86, you don't even need to precompute the 24 bit array; simply access the by te array at the desire offset as a 32 bit value. The x86 will do unaligned fetches just fine. [commenter noted that endianess mucks this up, so it isn't an answer, OK, do the 24 bit version.]