java - 检查部分已知的整数是否在某个范围内

Question

我有一个特殊的问题，正在寻找有效的解决方案。我有一个字节数组，其中包含无符号 4 字节整数的最高有效 n 个字节(首先是最高有效字节)。剩余字节(如果有)的值未知。我需要检查部分已知的整数值是否落在已知整数的某个范围(+或-x)内。对于被测试的字节数组表示的整数来说，环绕也是有效的。

我有一个可行的解决方案(如下)。问题是这个解决方案执行的比较比我认为必要的要多，并且在最小 sig 字节未知的情况下，整个比较负载将被重复。我很确定它可以更有效地完成，但不知道如何做。最低有效字节未知的情况是一种边缘情况，所以我可能能够忍受它，但它构成了需要低延迟的系统的一部分，所以如果有人可以帮助解决这个问题，那就太好了。

提前致谢。

static final int BYTES_IN_INT = 4;
static final int BYTE_SHIFT = 010;

// partial integer byte array length guaranteed to be 1-4 so no checking necessary
static boolean checkPartialIntegerInRange(byte[] partialIntegerBytes, int expectedValue, int range)
{
   boolean inRange = false;

   if(partialIntegerBytes.length == BYTES_IN_INT)
   {
      // normal scenario, all bytes known
      inRange = Math.abs(ByteBuffer.wrap(partialIntegerBytes).getInt() - expectedValue) <= range;
   }
   else
   {
      // we don't know least significant bytes, could have any value
      // need to check if partially known int could lie in the range
      int partialInteger = 0;
      int mask = 0;

      // build partial int and mask
      for (int i = 0; i < partialIntegerBytes.length; i++)
      {
         int shift = ((BYTES_IN_INT - 1) - i) * BYTE_SHIFT;
         // shift bytes to correct position
         partialInteger |= (partialIntegerBytes[i] << shift);

         // build up mask to mask off expected value for comparison
         mask |= (0xFF << shift);
      }

      // check partial int falls in range
      for (int i = -(range); i <= range; i++)
      {
         if (partialInteger == ((expectedValue + i) & mask))
         {
            inRange = true;
            break;
         }
      }
   }
   return inRange;
}

编辑:感谢以下贡献者。这是我的新解决方案。欢迎评论。

static final int  BYTES_IN_INT = 4;
static final int  BYTE_SHIFT = 010;
static final int  UBYTE_MASK = 0xFF;
static final long UINT_MASK = 0xFFFFFFFFl;

public static boolean checkPartialIntegerInRange(byte[] partialIntegerBytes, int expectedValue, int range)
{
  boolean inRange;

  if(partialIntegerBytes.length == BYTES_IN_INT)
  {
    inRange = Math.abs(ByteBuffer.wrap(partialIntegerBytes).getInt() - expectedValue) <= range;
  }
  else
  {
    int partialIntegerMin = 0;
    int partialIntegerMax = 0;

    for(int i=0; i < BYTES_IN_INT; i++)
    {
      int shift = ((BYTES_IN_INT - 1) - i) * BYTE_SHIFT;
      if(i < partialIntegerBytes.length)
      {
        partialIntegerMin |= (((partialIntegerBytes[i] & UBYTE_MASK) << shift));
        partialIntegerMax = partialIntegerMin;
      }
      else
      {
        partialIntegerMax |=(UBYTE_MASK << shift);
      }
    }

    long partialMinUnsigned = partialIntegerMin & UINT_MASK;
    long partialMaxUnsigned = partialIntegerMax & UINT_MASK;
    long rangeMinUnsigned = (expectedValue - range) & UINT_MASK;
    long rangeMaxUnsigned = (expectedValue + range) & UINT_MASK;

    if(rangeMinUnsigned <= rangeMaxUnsigned)
    {
      inRange = partialMinUnsigned <= rangeMaxUnsigned && partialMaxUnsigned >= rangeMinUnsigned;
    }
    else
    {
      inRange = partialMinUnsigned <= rangeMaxUnsigned || partialMaxUnsigned >= rangeMinUnsigned;
    }
  }
  return inRange;
}

Answer 1

假设你有一个顺时针区间(x，y)和一个正态区间(低，高)(每个区间都包括它们的端点)，确定它们是否相交可以这样完成(未测试):

if (x <= y) {
    // (x, y) is a normal interval, use normal interval intersect
    return low <= y && high >= x;
}
else {
    // (x, y) wraps
    return low <= y || high >= x;
}

要作为无符号整数进行比较，您可以使用 long(与 x & 0xffffffffL 进行转换以抵消符号扩展)或 Integer.compareUnsigned code>(在较新版本的 Java 中)，或者，如果您愿意，可以使用 Integer.MIN_VALUE 对两个操作数进行加/减/异或操作。