java 。从不适合字节边界的字节数组中的位中提取整数

Question

我有以下字节数组:01010110 01110100 00100101 01001011

这些字节被分成两组来编码七个整数。我知道第一组由 3 个值组成，每个值 4 位(0101 0110 0111)，代表数字 5、6、7。第二组由 4 个值组成，每个值 5 位(01000 01001 01010 01011)，分别表示整数 8、9、10 和 11。

为了提取整数，我目前使用以下方法。将数组转换为二进制字符串:

public static String byteArrayToBinaryString(byte[] byteArray)
    {
    String[] arrayOfStrings = new String[byteArray.length];

    for(int i=0; i<byteArray.length; i++)
    {
        arrayOfStrings[i] = byteToBinaryString(byteArray[i]);
    }

    String bitsetString = "";
    for(String testArrayStringElement : arrayOfStrings)
    {
        bitsetString += testArrayStringElement;
    }

    return bitsetString;
}

// Taken from here: http://helpdesk.objects.com.au/java/converting-large-byte-array-to-binary-string
public static String byteToBinaryString(byte byteIn) 
{
    StringBuilder sb = new StringBuilder("00000000");

    for (int bit = 0; bit < 8; bit++) 
    {
        if (((byteIn >> bit) & 1) > 0) 
        {
            sb.setCharAt(7 - bit, '1');
        }
    }

    return sb.toString();
}

然后，我将二进制字符串拆分为 2 个子字符串:12 个字符和 20 个字符。然后我将每个子字符串拆分为新的子字符串，每个子字符串的长度都等于位数。然后我将每个子字符串转换为一个整数。

它可以工作，但代表数千个整数的字节数组需要 30 秒到 1 分钟才能提取。

我这里有点不知所措。如何使用按位运算符执行此操作？

非常感谢!

Answer 1

I assume you have an understanding of the basic bit operations and how to express them in Java.

---

用铅笔画出问题的合成图

 byte 0     byte 1     byte 2     byte 3
01010110   01110100   00100101   01001011
\__/\__/   \__/\______/\___/\______/\___/
 a   b      c     d      e     f      g

要提取a、b 和c，我们需要执行以下操作

   a          b          c

 byte 0     byte 0     byte 1
01010110   01010110   01110100
\.  \.     ||||||||   \.  \.  
  '\  '\   XXXX||||     '\  '\
0.. 0101   0.. 0110   0.. 0111

  Shift       And       Shift

在Java中

int a = byteArray[0] >>> 4, b = byteArray[0] & 0xf, c = byteArray[1] >>> 4;

其他值 d、e、f 和 g 的计算方式类似，但其中一些需要从数组中读取两个字节(实际上是 d 和 f)。

          d                      e

   byte 1    byte 2            byte 2
  01110100  00100101          00100101
  ||||\\\\  |                 |\\\\\
  XXXX \\\\ |                 X \\\\\
        \\\\|                    \\\\\
  0..   01000                    01001

要计算d，我们需要用byteArray[1] & 0xf 隔离字节1 的最少四位。然后用 (byteArray[1] & 0xf) << 1 为字节 2 中的位腾出空间, 用 byteArray[1] >>> 7 提取那个位最后将结果合并在一起。

int d = (byteArray[1] & 0xf) << 1 | byteArray[2] >>> 7;
int e = (byteArray[2] & 0x7c) >>> 2;
int f = (byteArray[2] & 0x3) << 3 | byteArray[3] >>> 5;
int g = byteArray[3] & 0x1f;

---

当您熟悉处理位操作时，您可以考虑泛化提取整数的函数。

我做了函数int extract(byte[] bits, int[] sizes, int[] res) ，给定一个字节数组 bits ，大小数组 sizes ，其中偶数索引保存要提取的整数的大小(以位为单位)，奇数索引保存要提取的整数的数量，输出数组 res大到足以容纳输出中的所有整数，摘自 bits sizes 表示的所有整数.
它返回提取的整数数。

例如原问题可以这样解决

int res[] = new int[8];
byte bits[] = new byte[]{0x56, 0x74, 0x25, 0x4b};

//Extract 3 integers of 4 bits and 4 integers of 5 bits
int ints = BitsExtractor.extract(bits, new int[]{4, 3,  5, 4}, res);

---

public class BitsExtractor
{
    public static int extract(byte[] bits, int[] sizes, int[] res)
    {

        int currentByte = 0;            //Index into the bits array
        int intProduced = 0;            //Number of ints produced so far
        int bitsLeftInByte = 8;         //How many bits left in the current byte
        int howManyInts = 0;            //Number of integers to extract 

        //Scan the sizes array two items at a time
        for (int currentSize = 0; currentSize < sizes.length - 1; currentSize += 2)
        {
            //Size, in bits, of the integers to extract
            int intSize = sizes[currentSize];

            howManyInts += sizes[currentSize+1];

            int temp = 0;                   //Temporary value of an integer
            int sizeLeft = intSize;         //How many bits left to extract 


            //Do until we have enough integer or we exhaust the bits array
            while (intProduced < howManyInts && currentByte <= bits.length)
            {
                //How many bit we can extract from the current byte
                int bitSize = Math.min(sizeLeft, bitsLeftInByte);               //sizeLeft <= bitsLeftInByte ? sizeLeft : bitsLeftInByte;
                //The value to mask out the number of bit extracted from
                //The current byte (e.g. for 3 it is 7)
                int byteMask = (1 << bitSize) - 1;
                //Extract the new bits (Note that we extract starting from the
                //RIGHT so we need to consider the bits left in the byte)
                int newBits = (bits[currentByte] >>> (bitsLeftInByte - bitSize)) & byteMask;

                //Create the new temporary value of the current integer by
                //inserting the bits in the lowest positions
                temp = temp << bitSize | newBits;

                //"Remove" the bits processed from the byte
                bitsLeftInByte -= bitSize;

                //Is the byte has been exhausted, move to the next
                if (bitsLeftInByte == 0)
                {
                    bitsLeftInByte = 8;
                    currentByte++;
                }

                //"Remove" the bits processed from the size
                sizeLeft -= bitSize;

                //If we have extracted all the bits, save the integer
                if (sizeLeft == 0)
                {
                    res[intProduced++] = temp;
                    temp = 0;
                    sizeLeft = intSize;
                }
            }
        }

        return intProduced;

    }
}