Retrieve range of bits from byte array

Question

I have a 16 byte byte array with various values populated inside of it. Those values can and do cross the byte boundary.

Here is the binary representation of my data

0011 | 0011 | 1110 | 1000 | 1100 | 1000 | 1100 | 1000 | 0100 | 1101 | 0010 | 1111 | 1010 | 0001 | 1111 | 1111 [ 0 - 63]

0000 | 0101 | 0000 | 0011 | 0000 | 0011 | 1110 | 1000 | 1100 | 1000 | 1100 | 1000 | 0000 | 0001 | 0010 | 1100 [64 -127]

The various values I need to retrieve are stored in the following bit positions

0-3 | 4-5 | 6-15 | 16-23 | 24-31 | 32 - 63 | 64-71 | 72-79 | 80-83 | 84-85 | 86-94 | 96-103 | 104-111 | 112-127

CODE:

Here's the code to populate the Byte Array:

protected byte[] createMessageHeader(byte[] content) {
    int[] set = new int[128];
    set = intToBinary(set, 3, 3);
    set = intToBinary(set, 0, 5);
    set = intToBinary(set, 1000, 15);
    set = intToBinary(set, 200, 23);
    set = intToBinary(set, 200, 31);
    set = intToBinary(set, 1294967295, 63);
    set = intToBinary(set, 5, 71);
    set = intToBinary(set, 3, 79);
    set = intToBinary(set, 0, 83);
    set = intToBinary(set, 0, 85);
    set = intToBinary(set, 1000, 95);
    set = intToBinary(set, 200, 103);
    set = intToBinary(set, 200, 111);
    set = intToBinary(set, 300, 127);

    BitSet bitSet = binArrayToBitset(set);
    byte[] b1 = bitSet.toByteArray();

    for(int i = 0; i < b1.length; i++) {
        b1[i] = (byte) (Integer.reverse(b1[i]) >>> 24);
    }

    return b1;
}

protected int[] intToBinary(int[] binary, int val, int start) {
        // Number should be positive
        while (val > 0) {
            binary[start--] = val % 2;
            val = val / 2;
        }
        return binary;
    }
protected BitSet binArrayToBitset(int[] binArray) {
        BitSet set = new BitSet(128);

        for(int i = 0; i < binArray.length; i++) {
            if(binArray[i] != 0)
                set.set(i);
        }
        return set;
    }
//Convenience method to print binary representation of values
protected void toBinString(int[] set) {
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < set.length; i++) {
            if(i % 4 == 0)
                stringBuilder.append("|");
            if(i % 64 == 0)
                stringBuilder.append("\n");
            stringBuilder.append(set[i]);
        }
    }


    

The above code should produce the Byte Array with the specified values at the specific bit index ranges.

---

I have tried numerous methods for retrieving these values, most recently:

private int extractBits2(byte[] header, int start, int end) {
    BitSet bitSet = BitSet.valueOf(header);
    return (int) bitSet.get(start, end + 1).toLongArray()[0];
}

Using the above method, if I call it with:

int extracted = extractBits2(header, 6, 15)

The value returned is '0b00000011_10100000' (IntelliJ Debugger window), but I thought it would return '0b0011 1110 1000' (int 1000).

What am I missing here? I need to be able to retrieve the range of bits so I can validate their values.

NOTE: all the values stored are integers except for one which is a timestamp value (long).

Answer 1

Others may be number and mathematical wizards, but what made it difficult for me personally to reason about this was that when your BitSet was printed bit by bit, it did not match your expected representation at all. It appeared to be inverted. This ties in with my remark about how complicated it appeared to be to construct the input in the first place, and as this is a largely symmetrical operation, extracting the information again would be just as intricate.

In the following approach I tried to use built-in methods for converting binary representations to decimal, as well as for operating on the array, thus avoiding mathematical errors and to be able to easily reason about debugger output:

This is a utility method to print out any BitSet in the binary byte-wise representation that you used:

/**
 * Print a bitset to stdout in binary notation, separating bytes with a pipe '|'.
 * @param bitSet
 */
private static void printBitSetByteWise(BitSet bitSet) {
    for(int i = 0; i< bitSet.size(); i++) {
        if(i>0 && i%4==0) System.out.print('|');
        System.out.print(bitSet.get(i) ? 1 : 0);
    }
    System.out.println();
}

Modified extraction method, which converts the byte array into a BitSet, turns that back into an unsigned binary String, then parses it using Integer.parseInt with a radix of 2 for binary:

/**
 * Extracts an integer formed from the given indices in an array of bytes.
 */
private int extractBits2(byte[] header, int start, int endInclusive) {
    BitSet bitSet = BitSet.valueOf(header);
    final BitSet subset = bitSet.get(start, endInclusive + 1);
    //create a String representation
    final int length = endInclusive - start + 1;
    StringBuilder b = new StringBuilder(length);
    for(int i = 0; i < length; i++) {
        b.append(subset.get(i)?'1':'0');
    }
    //parse using radix 2
    return Integer.parseInt(b.toString(), 2);
}

When creating the input array, there is no need to pass an argument, and since you're operating directly on the array itself, there's no point re-assigning it to itself in each step either. Finally, I've removed the inversion part at the bottom:

protected byte[] createMessageHeader() {
    int[] set = new int[128];
    integrate(set, 3, 3);
    integrate(set, 0, 5);
    integrate(set, 1000, 15);
    integrate(set, 200, 23);
    integrate(set, 200, 31);
    integrate(set, 1294967295, 63);
    integrate(set, 5, 71);
    integrate(set, 3, 79);
    integrate(set, 0, 83);
    integrate(set, 0, 85);
    integrate(set, 1000, 94);
    integrate(set, 200, 103);
    integrate(set, 200, 111);
    integrate(set, 300, 127);
    
    BitSet bitSet = binArrayToBitset(set);
    
    return bitSet.toByteArray();
}

Here, instead of dividing, inserting backwards, then inverting, I simply use the binary String representation (kindly provided by the built-in JDK method Integer.toBinaryString), convert it to its digits 1s and 0s, and arraycopy them into the correct position:

/**
 * Inserts the given value into the given int array, right-aligning its
 * binary representation to the given index within the array.
 */
protected void integrate(int[] binary, int value, int alignEndToIndex) {
    String binaryRepresentation = Integer.toBinaryString(value);
    int[] digits = numberStringToArrayOfDigits(binaryRepresentation);
    System.arraycopy(digits,0,binary, alignEndToIndex+1-digits.length, digits.length);
}

/**
 * Convert a String, which is assumed to represent a number, to
 * an integer array containing its individual digits.
 */
protected int[] numberStringToArrayOfDigits(String binaryRepresentation) {
    int[] digits = new int[binaryRepresentation.length()];
    for (int i = 0; i < binaryRepresentation.length(); i++) {
        digits[i] = binaryRepresentation.charAt(i) - '0';
    }
    return digits;
}

And this is the same as yours:

protected BitSet binArrayToBitset(int[] binArray) {
    BitSet set = new BitSet(128);
    
    for(int i = 0; i < binArray.length; i++) {
        if(binArray[i] != 0)
            set.set(i);
    }
    return set;
} 

Putting it all together:

    final byte[] header = createMessageHeader();
    BitSet bitSet = BitSet.valueOf(header);
    printBitSetByteWise(bitSet); //just to verify contents are as expected
    //0011|0011|1110|1000|1100|1000|1100|1000|0100|1101|0010|1111|1010|0001|1111|1111|0000|0101|0000|0011|0000|0111|1101|0000|1100|1000|1100|1000|0000|0001|0010|1100

    System.out.println(extractBits2(header, 6, 15)); //1000
    System.out.println(extractBits2(header, 32, 63)); //1294967295
    System.out.println(extractBits2(header, 104, 111)); //200

Answer 2

IIrc Bitset.get only takes the range of bits from the byte which the start index is in. what you could maybe do is iterate over the header array and extract the bits that you want from each byte. For example, you could do something like this:

private int extractBits(byte[] header, int start, int end) {
// First, figure out which byte in the header array the start and end indices are in
int startByte = start / 8;
int endByte = end / 8;

// Next, calculate the indices of the start and end bits within the start and end bytes
int startBit = start % 8;
int endBit = end % 8;

// Initialize a result variable to 0
int result = 0;

// If the start and end indices are in the same byte, we can just use the BitSet.get()
// method to extract the bits that we want
if (startByte == endByte) {
    BitSet bitSet = BitSet.valueOf(new byte[]{header[startByte]});
    result = (int) bitSet.get(startBit, endBit + 1).toLongArray()[0];
} else {
    // If the start and end indices are in different bytes, we need to do some additional
    // processing to extract the bits that we want.

    // First, create a new array that contains only the bytes that we need to extract bits from
    byte[] bytes = Arrays.copyOfRange(header, startByte, endByte + 1);

    // Next, create a BitSet from the bytes array
    BitSet bitSet = BitSet.valueOf(bytes);

    // Then, get the bits from the start index to the end of the start byte and add them to the result
    BitSet startBits = bitSet.get(startBit, 8);
    result = (int) startBits.toLongArray()[0];

    // Next, shift the bits in the result variable to the left by the number of bits that we've already extracted
    result <<= 8 - startBit;

    // Then, get the bits from the beginning of the end byte to the end index and add them to the result
    BitSet endBits = bitSet.get(0, endBit + 1);
    result |= (int) endBits.toLongArray()[0];
}

// Finally, return the result
return result;  }

Answer 3

I don't know if this will help. It allows, at least, for your requirements to be easily changed and parameterised. I'm not quite sure how your data comes in the first place, but it should be pretty easy to get it into a 'binary string'. I've used a tuple class here (which the JRE sadly lacks) but there's no great need to go 3rd party if you don't want:

package com.technojeeves.tuples;

import org.javatuples.Pair;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class App {
    public static void main(String[] args) {

        String data = """
                0011 | 0011 | 1110 | 1000 | 1100 | 1000 | 1100 | 1000 | 0100 | 1101 | 0010 | 1111 | 1010 | 0001 | 1111 | 1111
                0000 | 0101 | 0000 | 0011 | 0000 | 0011 | 1110 | 1000 | 1100 | 1000 | 1100 | 1000 | 0000 | 0001 | 0010 | 1100
                """;

        String bitsWanted = "0-3, 4-5, 6-15, 16-23, 24-31, 32-63, 64-71, 72-79, 80-83, 84-85, 86-94, 96-103, 104-111, 112-127";

        List<Pair<Integer, Integer>> tuples = App.getTuples(bitsWanted);
        List<Integer> values = App.bitsStringToIntegersList(data, tuples);

        int ix = 0;
        for (Integer b : values) {
            System.out.printf("Bits %s = 0x%02X%n", tuples.get(ix).getValue0() + "-" + tuples.get(ix++).getValue1(), b);
        }
    }


    private static List<Pair<Integer, Integer>> getTuples(String tupleString) {
        List<Pair<Integer, Integer>> result = new ArrayList<>();
        String[] tuples = tupleString.split("\\s*,\\s*");
        for(String tuple : tuples) {
            String[] startEnd = tuple.split("-");
            result.add(new Pair(Integer.valueOf(startEnd[0]), Integer.valueOf(startEnd[1])));
        }
        return result;
    }




    private static List<Integer> bitsStringToIntegersList(String bits, List<Pair<Integer, Integer>> tuples) {
        List<Integer> result = new ArrayList<>();
        bits = bits.replaceAll("[^01]", "");
        for (Pair<Integer, Integer> startEnd : tuples) {
            int start = startEnd.getValue0();
            int end = startEnd.getValue1();
            result.add(Integer.valueOf(bits.substring(start, end), 2));
        }
        return result;
    }
}

Output is:

Bits 0-3 = 0x01
Bits 4-5 = 0x00
Bits 6-15 = 0x1F4
Bits 16-23 = 0x64
Bits 24-31 = 0x64
Bits 32-63 = 0x2697D0FF
Bits 64-71 = 0x02
Bits 72-79 = 0x01
Bits 80-83 = 0x00
Bits 84-85 = 0x00
Bits 86-94 = 0xFA
Bits 96-103 = 0x64
Bits 104-111 = 0x64
Bits 112-127 = 0x96